Source-linked AI summary
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
Stephen Tu, Ross Boczar, Max Simchowitz, Mahdi Soltanolkotabi, Benjamin Recht
TL;DR
The paper studies efficient recovery of low-rank matrices from linear measurements. It introduces Procrustes Flow, combining careful initialization with non-convex gradient descent, and proves geometric convergence under RIP, including Gaussian recovery with nearly linear-in-parameters measurements.
Problem
The paper studies how to efficiently recover a low-rank matrix from partial linear measurements.
Method
Procrustes Flow combines projected-gradient initialization with successive gradient-descent refinements on non-convex factored objectives.
Results
Ω((n1+n2)r) equations suffice for standard ensembles, and the algorithm converges geometrically under standard RIP assumptions.
Takeaways & Limitations
The method recovers low-rank matrices with a measurement count only a constant factor above the number of parameters needed to specify them.
Takeaways & Limitations
The theoretical results focus on affine maps A satisfying the matrix Restricted Isometry Property.
Abstract
from arXiv · showhide
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 $n_1 \times n_2$ matrix of rank $r$ when the number of measurements exceeds a constant times $(n_1+n_2)r$.
1 Introduction
The paper addresses low-rank matrix recovery from linear equations using local-search heuristics, whose practical success has lacked guarantees comparable to convex methods. Under RIP assumptions, Procrustes Flow achieves recovery with nearly the number of measurements needed to specify the matrix.
- Low-rank recovery asks how to find a matrix satisfying linear equations and what computational complexity such an algorithm requires.
- Factorizing M as UV^T converts the problem into matrix bilinear equations addressed by local-search heuristics.
- These local-search procedures work well empirically but lack strong guarantees associated with convex programming heuristics.
- Procrustes Flow solves the bilinear equations under standard RIP assumptions on the measurement map A.
- Ω((n1+n2)r) equations suffice for standard ensembles, only a constant factor above the parameters needed to specify an n1 × n2 rank-r matrix.
2 Algorithms
Procrustes Flow combines projected-gradient initialization with non-convex gradient-descent refinement for positive semidefinite and arbitrary low-rank matrices. Its initialization uses low-rank projections, while rectangular factorizations include regularization to address factorization redundancy.
- Procrustes Flow has two components: projected-gradient initialization followed by successive gradient-descent refinements.
- The algorithm provides separate variants for positive semidefinite matrices and arbitrary matrices.
- Initialization via low-rank projected gradients: Initialization starts from the zero matrix and repeatedly applies projected updates on rank-r or rank-r positive semidefinite matrices.
- Initialization via low-rank projected gradients: The resulting estimate is converted into factors using an eigendecomposition in the PSD case and an SVD for rectangular matrices.
- Successive refinement via gradient descent – positive semidefinite case: For PSD matrices, refinement minimizes squared measurement misfit through gradient descent starting from the initialized factor U0.
- Successive refinement via gradient descent – arbitrary matrices: For arbitrary matrices, refinement factors M as UV^T and adds a regularizer that places U and V on equal footing despite invertible-factor redundancy.
3 Main Results
Procrustes Flow uses projected-gradient initialization followed by non-convex gradient refinement to recover low-rank matrices under restricted isometry assumptions. The method achieves geometric convergence for both positive semidefinite and rectangular matrices, including Gaussian measurements with near-parameter-count sample complexity.
- Quadratic measurements: Under rank-6r RIP assumptions, Procrustes Flow recovers positive semidefinite factors up to an orthogonal rotation.The PSD formulation targets M = XX^T, where X is identifiable only up to rotational ambiguity.
- Bilinear measurements: Under rank-6r RIP with δ6r ≤1/25, the rectangular variant provides a corresponding guarantee for factors of arbitrary rank-r matrices.Theorem 3.3 uses the SVD-based factorization X = AΣ^1/2 and Y = BΣ^1/2, with initialization requiring T0 ≥3 log(√rκ) + 5 iterations.
- Bilinear measurements: Ω(nr) Gaussian measurements suffice for relative error at most ǫ in O(κ log(1/ǫ)) iterations.With more measurements, m = Ω(nr^2κ^2) allows the initialization condition to hold after one projected-gradient iteration.
- Initialization: The initialization length depends on the unknown condition number κ, but an iterate-based test can detect entry into the convergence region.The paper establishes this sufficient test in the symmetric case and states that extension to general matrices is straightforward.
- Initialization: Projected-gradient initialization trades singular-vector computations against gradient updates, while few projected steps can suffice for geometric convergence.The paper notes that projected steps may be preferable for small dense matrices, whereas gradient updates can be advantageous when dimensions are large or matrix-vector multiplication is fast.
4 Related work
The paper situates Procrustes Flow among convex and non-convex approaches to low-rank recovery, emphasizing RIP-based guarantees and favorable sample complexity. Prior work includes nuclear-norm recovery, alternating or manifold optimization, Gaussian analyses, stochastic gradients, and related Procrustes Flow schemes.
- Nuclear-norm recovery under RIP established equivalence between minimum trace and minimum rank, requiring Ω(nr) Gaussian measurements.
- Non-convex matrix recovery guarantees have used manifold optimization and alternating minimization, with some methods requiring fresh samples at each iteration.
- Procrustes Flow extends a regularity-condition analysis from phase retrieval to ranks higher than one.
- The paper contrasts its convergence with a slower rate reported by Zheng and Lafferty and emphasizes that RIP simplifies the analysis.
- Stochastic-gradient results require Ω((nr log n)/ε) samples for relative error ε, whereas this paper's sample complexity is independent of ε.
5 Proofs
The proofs establish geometric convergence by relating the empirical non-convex objective to a reference function and verifying a regularity condition under RIP. The analysis handles rotational ambiguity through the orthogonal Procrustes distance and transfers results between update variants.
- The PSD proof analyzes an update equivalent to Procrustes Flow up to step-size rescaling.
- RIP lemmas control the relevant gradient and function discrepancies through rank-2r, rank-4r, and rank-6r restrictions.
- The reference function F is not generally strongly convex because factorized solutions have rotational degrees of freedom.
- Gradient descent converges geometrically when the objective satisfies RC(α, β, δ) and starts within the neighborhood B(δ).
- The proof verifies regularity by combining a stronger condition for F, gradient closeness between f and F, and local Lipschitz control of ∇f.
- Equation (5.7) yields the regularity parameters, after which Lemma 5.6 gives the convergence result.
- The Procrustes distance aligns U and X using the orthogonal rotation solving the classic orthogonal Procrustes problem.
5.3 Proof of initialization (Equation (3.3))
The initialization proof bounds the projected-gradient initialization error by controlling its contraction under RIP. Starting from the zero matrix, the iterates enter the neighborhood required for subsequent Procrustes Flow convergence.
- The initialization analysis bounds the contraction factor by ρ(A) ≤ 2δ4r ≤ 1/5.
- Initialization starts from M0 = 0n×n and applies the projected-gradient initialization iterates.
- The proof chooses the iteration conditions so that the initialization error is eventually bounded by the target neighborhood.
5.4 Proof for rectangular matrices (Theorem 3.3)
For rectangular matrices, the proof lifts the factorized problem into a larger symmetric space and transfers the PSD convergence argument through augmented measurement operators. RIP controls the lifted regularity and gradient bounds needed for geometric convergence.
- A rank-r rectangular matrix is factorized as M = XY^T using X = AΣ^1/2 and Y = BΣ^1/2.
- The pairs of rectangular factors and their sign variants are aggregated into lifted matrices W and Z.
- The lifted objective g is related to a reference function F whose gradient is ∇F(W) = (WW^T − ZZT)W.
- The Procrustes Flow factor updates admit a compact lifted-space representation involving Pdiag and Poff.
- The rectangular proof establishes regularity for g and a Lipschitz property for its gradient under 4r-RIP and 6r-RIP assumptions.
- Applying these lemmas with δ4r ≤ 1/25 completes the proof of the rectangular convergence theorem.
- The rectangular initialization proof follows the PSD argument using projected-gradient contraction and factorization of the resulting rank-r estimate.
A Proof of Lemma 5.4
The proof simplifies the matrices through a without-loss-of-generality transformation and then establishes the target inequality using positivity and symmetry conditions.
- The proof assumes R = I, U^T X ⪰ 0, and H^T X = X^T H without loss of generality.
- The resulting right-hand side satisfies the required condition, completing the lemma.
- Using H^T X = U^T X − X^T X and U^T X ⪰ 0, the proof derives the needed bound.
B Proof of Lemma 3.4
The proof bounds the relevant right-hand side through inequalities, invokes Weyl’s inequalities, and concludes one condition from an earlier bound.
- Weyl’s inequalities are used to obtain the relevant intermediate implication.
- The proof upper bounds the right-hand side through a chain of inequalities.
- Condition (c) follows from equation (B.1), completing this part of the argument.
C Proof of Lemma 5.14
The proof combines a dilation trick, algebraic and Weyl-based inequalities, singular-value decomposition, and an orthogonal Procrustes solution to establish the target relation.
- The dilation trick is applied for ℓ = 1, 2 as the proof begins its matrix comparison.
- The proof uses algebraic manipulations and Weyl’s inequality to derive successive norm bounds.
- A singular value decomposition of X^T is introduced before applying Lemma 5.4 and equations (C.1) and (C.3).
- The orthogonal Procrustes problem is identified with the optimal rotation between the relevant factors.
- Substituting the resulting solution into equation (C.4) concludes the proof.
D Proof of the first inequality in Equation (3.8)
The proof establishes the first inequality in equation (3.8) using Lemma D.1 and concludes with a distance bound.
- The first inequality is obtained directly from Lemma D.1 under its stated matrix assumptions.
- The argument proceeds through an intermediate bound involving F before reaching the final statement.
- The resulting estimate is 2∥Z∥dist(W, Z), after which the proof concludes.