Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
Authors: Joel A. Tropp, Alp Yurtsever, Madeleine Udell, Volkan Cevher
NeurIPS 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Theoretical analysis establishes that the proposed method can achieve any prescribed relative error in the Schatten 1-norm and that it exploits the spectral decay of the input matrix. Computer experiments show that the proposed method dominates alternative techniques for fixed-rank psd matrix approximation across a wide range of examples. |
| Researcher Affiliation | Academia | Joel A. Tropp Caltech jtropp@caltech.edu Alp Yurtsever EPFL alp.yurtsever@epfl.ch Madeleine Udell Cornell mru8@cornell.edu Volkan Cevher EPFL volkan.cevher@epfl.ch |
| Pseudocode | Yes | Algorithm 1 Sketch Initialization. Implements (2.2) (2.3) with a random orthonormal test matrix. Algorithm 2 Linear Update. Implements (2.4). Algorithm 3 Fixed-Rank PSD Approximation. Implements (2.7). |
| Open Source Code | No | The paper provides pseudocode (Algorithms 1-3) and mentions developing an 'SSFT implementation for empirical testing,' but it does not include an explicit statement about releasing the source code or a link to a code repository for the described methodology. |
| Open Datasets | Yes | Max Cut: ... The matrix is an approximate solution to the MAXCUT SDP [20] for the sparse graph G40 [10]. [10] T. A. Davis and Hu. The University of Florida sparse matrix collection. |
| Dataset Splits | No | The paper describes how input matrices are generated for synthetic examples and mentions specific application examples (Max Cut, Phase Retrieval) and their properties, but it does not specify explicit training, validation, or test splits (e.g., percentages or sample counts) for these datasets. It only describes the input matrix (A) and how approximations are computed. |
| Hardware Specification | No | The paper does not provide specific hardware details (e.g., CPU/GPU models, memory specifications, or cloud computing instance types) used for running its experiments. |
| Software Dependencies | Yes | The pseudocode uses both mathematical notation and MATLAB 2017A functions. |
| Experiment Setup | Yes | For the numerical experiments, the field F = C except when noted explicitly. Choose a psd input matrix A Fn n and a target rank r. Then fix a sketch size parameter k with r k n. For each trial, draw the test matrix Ωfrom the orthonormal or the SSFT distribution, and form the sketch Y = AΩof the input matrix. Using Algorithm 3, compute the rank-r psd approximation ˆ Ar defined in (2.7). We evaluate the performance using the relative error metric: Schatten p-norm relative error = A ˆ Ar p A JAKr p 1. (5.1) We perform 20 independent trials and report the average error. |