Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
Authors: Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, Ben Recht
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained by a thresholding scheme followed by gradient descent on a non-convex objective. We show that as long as the measurements obey a standard restricted isometry property, our algorithm converges to the unknown matrix at a geometric rate. In the case of Gaussian measurements, such convergence occurs for a n1 n2 matrix of rank r when the number of measurements exceeds a constant times (n1 + n2)r. |
| Researcher Affiliation | Academia | Stephen Tu, Ross Boczar, Max Simchowitz {STEPHENT,BOCZAR,MSIMCHOW}@BERKELEY.EDU EECS Department, UC Berkeley, Berkeley, CA. Mahdi Soltanolkotabi SOLTANOL@USC.EDU Ming Hsieh Department of Electrical Engineering, USC, Los Angeles, CA. Benjamin Recht BRECHT@BERKELEY.EDU EECS Department, UC Berkeley, Berkeley, CA. |
| Pseudocode | Yes | Algorithm 1 Procrustes Flow (PF) Require: {Ak}m k=1, {bk}m k=1, {ατ} τ=1, {µτ} τ=1, T0 N. // Initialization phase. f M0 := 0n n. for τ = 0, 1, ..., T0 1 do // Projection onto rank r PSD matrices. f Mτ+1 Pr( f Mτ ατ+1 Pm k=1( Ak, f Mτ bk)Ak). end for // SVD of f MT0, with Q Rn r, Σ Rr r. QΣQT := f MT0. U0 := QΣ1/2. // Gradient descent phase. repeat Uτ+1 Uτ µτ+1 U0 2 f(Uτ). until convergence |
| Open Source Code | No | The paper does not contain any explicit statement about open-source code release or a link to a code repository. |
| Open Datasets | No | The paper discusses theoretical models like "Gaussian measurements" but does not refer to any specific publicly available dataset for training. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with data, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running experiments, as it is primarily theoretical. |
| Software Dependencies | No | The paper does not list specific software dependencies with version numbers, as it is a theoretical work without reported experimental implementations. |
| Experiment Setup | No | The paper is theoretical and does not detail any experimental setup, hyperparameters, or training configurations. |