PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonconvex Matrix Factorization from Rank-One Measurements

Yuanxin Li, Cong Ma, Yuxin Chen, Yuejie Chi

arXiv:1802.06286v2cs.ITcs.LGmath.ITstat.ML

TL;DR

The paper asks how to recover low-rank matrices from random rank-one measurements with both statistical and computational efficiency. It minimizes a nonconvex quadratic loss over the low-rank factor using spectral initialization and vanilla gradient descent, and proves near-optimal guarantees when the rank is small. The key mechanism is implicit regularization, which keeps the iterates incoherent with the measurement vectors and permits aggressive step sizes without sample splitting.

  • Problem

    Recovering low-rank positive semidefinite matrices from limited rank-one measurements is a nonconvex problem spanning applications such as covariance sketching, phase retrieval, quantum state tomography, and neural-network learning.

    Source: §1 · p. 1, §1.1 · p. 2

  • Method

    The method directly estimates the low-rank factor by minimizing a nonconvex squared loss with vanilla gradient descent after tailored spectral initialization.

    Source: §2.1 · p. 4, §2 · p. 4

  • Results

    The algorithm converges to the true factor up to global ambiguity with near-optimal sample and computational complexity when the rank is small.

    Source: §1.1 · p. 2, §2.2 · p. 6, §5 · p. 11

  • Takeaways & Limitations

    Implicit regularization keeps initialization and iterates in an incoherent region, enabling larger step sizes and avoiding resampling while retaining near-optimal guarantees.

    Source: §4.2 · p. 9, §5 · p. 11

    The guarantees assume i.i.d. Gaussian sensing vectors and a full-column-rank ground-truth factor, with the stated near-optimality applying when rank is fixed or small.

    Source: §1.2 · p. 3, §2 · p. 4

Abstract

from arXiv · show

We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex quadratic loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is small, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample complexity and computational complexity. To the best of our knowledge, this is the first guarantee that achieves near-optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.

1 Introduction

The paper studies recovery of low-rank positive semidefinite matrices from limited random rank-one measurements using spectral initialization and vanilla gradient descent. It establishes near-optimal statistical and computational guarantees by showing that iterates remain in an incoherent region with favorable curvature.

1 Introduction

  • The recovery problem estimates a low-rank positive semidefinite matrix from a few rank-one measurements, or equivalently recovers its low-rank factor, and includes phase retrieval.Source: §1 · pp. 1–2

1.1 Main Contributions

  • Under i.i.d. Gaussian designs, vanilla gradient descent with spectral initialization exactly recovers the true factor up to global ambiguity using m=O(nr4 log n) measurements.For fixed rank, this sample complexity is near-optimal up to logarithmic factors.Source: §1.1 · p. 2
  • For ϵ-accuracy, gradient descent requires O(r2 log(1/ϵ)) iterations up to logarithmic factors and O(mnr) work per iteration.For fixed r, total computational complexity scales linearly with mn, proportional to reading all data.Source: §1.1 · pp. 2–3
  • Compared with prior guarantees, the method improves sample complexity from O(nr6 log2 n) to O(nr4 log n) and iteration complexity from O(n4r2 log(1/ϵ)) to O(r2 log(1/ϵ)).The paper identifies this as the first nonconvex method without resampling to achieve both near-optimal statistical and computational guarantees with respect to n.Source: §1.1 · p. 3

1.2 Surprising Effectiveness of Gradient Descent

  • The paper's implicit regularization result shows that spectral initialization and gradient descent remain in a Region of Incoherence and Contraction, where the loss has smoothness O(max{r, log n}).This smaller smoothness parameter permits more aggressive gradient steps than the O(n2)-scale bound associated with prior analysis.Source: §1.2 · pp. 3–4
  • Leave-one-out sequences establish that dependent gradient iterates remain incoherent with sensing vectors and contract in entry-wise prediction error.This addresses the difficulty that standard optimization theory controls Euclidean error but does not ensure the trajectory stays in the RIC.Source: §1.2 · p. 4

1.3 Notations

  • The paper uses standard matrix and vector notation, including spectral and Frobenius norms, inner products, vectorization, and asymptotic O(·) notation.These conventions support the stated recovery and complexity bounds.Source: §1.3 · p. 4

2 Algorithms and Main Results

The paper studies recovery of low-rank positive semidefinite matrices from Gaussian rank-one measurements using spectral initialization followed by vanilla gradient descent, with guarantees on sample and computational efficiency.

2 Algorithms and Main Results

  • Under Gaussian sensing, spectral initialization followed by vanilla gradient descent targets recovery of a full-column-rank factor with bounded condition number, up to orthonormal transformation.The sensing vectors are i.i.d. standard Gaussian, and the ground-truth factor need not have orthogonal columns.Source: §2 · p. 4, §2.1 · p. 4, §2.2 · p. 5

2.1 Vanilla Gradient Descent

  • The algorithm initializes with the top-r scaled eigenvectors of a data matrix and then updates the factor by gradient descent on a nonconvex squared loss.The update is Xt+1 = Xt − µt∇f(Xt).Source: §2.1 · pp. 4–5

2.2 Performance Guarantees

  • m = O(nr4 log n) measurements suffice for convergence, which is near-optimal up to logarithmic factors when r is fixed.After spectral initialization, m = O(nr3 log n) measurements can guarantee linear convergence to the global optimum.Source: §2.2 · p. 6
  • O(r2 log(1/ǫ)) iterations with per-iteration cost O(mnr) yield computational complexity linear in mn when r is fixed.This matches the time scale proportional to reading all measurements.Source: §2.2 · p. 6
  • The analysis shows implicit regularization: spectral initialization and gradient updates keep entry-wise errors controlled and iterates incoherent with the sensing vectors.The entry-wise error also decreases linearly, a property not characterized in [14].Source: §2.2 · p. 6
  • After an initial phase, incoherence permits a larger fixed step size, improving convergence without resampling at every iteration.The paper attributes the aggressive step size to incoherence becoming independent of log n after sufficiently many iterations.Source: §2.2 · p. 6

3 Related Work

The paper situates its factorization approach among convex, nonconvex, and related neural-network methods for rank-one measurement recovery, emphasizing simultaneous statistical and computational guarantees without resampling.

  • Nuclear norm minimization can achieve exact recovery with O(nr) measurements but is generally computationally expensive at large scale.Source: §3 · p. 7
  • The model also connects to phase retrieval, Kaczmarz methods, approximate message passing, and shallow neural networks with quadratic activation.Source: §3 · pp. 7–8
  • Prior gradient-descent analysis requires nr6 log2 n samples and O(n4r2 log(1/ǫ)) iterations, whereas this work improves both guarantees.Source: §3 · p. 7

3 Related Work

  • The paper claims the only guarantee achieving simultaneous near-optimal sample and computational complexity, while avoiding resampling.Table 1 compares methods reaching ǫ-accuracy, separating algorithms with and without resampling.Source: §3 · p. 7, Table 1 · p. 7
  • Alternating-minimization and noisy-power methods require fresh samples at every iteration, causing unbounded sample complexity for exact recovery.Source: §3 · p. 7

4 Outline of Theoretical Analysis

The proof establishes a region with favorable local geometry, then uses leave-one-out sequences and induction to keep gradient iterates there, with spectral initialization supplying the base case.

4 Outline of Theoretical Analysis

  • The analysis first identifies a region where the loss has strong convexity and smoothness along relevant directions, then proves iterates remain there.Source: §4 · p. 8, §4.1 · pp. 8–9

4.1 Local Geometry and Error Contraction

  • Within the RIC, restricted geometry yields contraction of the estimation error under a suitable step size.Source: §4.1 · pp. 8–9

4.2 Introducing Leave-One-Out Sequences

  • Leave-one-out sequences remove one measurement so their iterates are independent of the corresponding sensing vector, enabling incoherence analysis.Source: §4.2 · p. 9

4.3 Establishing Incoherence via Induction

  • An induction argument transfers proximity and incoherence from leave-one-out iterates to the original iterates while respecting the step-size condition.Source: §4.3 · pp. 10–11

4.4 Spectral Initialization

  • The tailored spectral initialization satisfies the induction hypotheses with high probability, completing the base case.Source: §4.4 · p. 11

5 Conclusions

The paper concludes that spectral initialization followed by vanilla gradient descent recovers low-rank positive semidefinite matrices from near-minimal random rank-one measurements without per-iteration resampling.

5 Conclusions

  • Vanilla gradient descent after spectral initialization recovers low-rank positive semidefinite matrices from a near-minimal number of random rank-one measurements.Source: §5 · p. 11
  • Implicit regularization keeps iterates incoherent with sensing vectors, enabling aggressive step sizes and lower computational cost without explicit regularization.Source: §5 · p. 11
  • The theory characterizes noiseless fitting error as a benchmark for future methods handling sparse outliers.Source: §5 · p. 11
  • Future work includes testing whether implicit regularization extends to shallow neural networks with nonquadratic activations.Source: §5 · p. 11

Appendices

The appendices collect technical lemmas supporting concentration, covering, Gaussian-design, and low-rank-matrix arguments used throughout the proof.

A Technical Lemmas

  • The appendices provide technical lemmas used throughout the proof, including Gaussian concentration and distributional facts.Source: A Technical Lemmas · pp. 12–13
  • Several lemmas establish high-probability bounds for Gaussian sensing vectors and matrix expressions involving fixed low-rank factors.Source: A Technical Lemmas · pp. 12, 14
  • The appendix also supplies covering-number and concentration tools for controlling classes of low-rank matrices.Source: A Technical Lemmas · pp. 12, 15
  • Proofs use matrix decompositions, independent Gaussian coordinates, union bounds, and norm inequalities to derive the stated controls.Source: A Technical Lemmas · pp. 13–14

B Proof of Lemma 1

The section proves Lemma 1 by establishing lower and upper bounds, with Lemma 14 supplying the key uniform control needed for the lower bound. The argument handles fixed quantities first, extends them through covering arguments, and then combines the resulting bounds.

B Proof of Lemma 1

  • Lemma 1’s lower bound follows by combining the bounds on B1, B2, and B3 with Lemma 14.The proof introduces V under Lemma 1’s assumptions and uses the resulting inequalities to establish lower bound (18).Source: B Proof of Lemma 1 · pp. 15–17
  • The Hessian identity and the operator-norm relation ∥I ⊗ A∥ = ∥A∥ yield the upper bound in Lemma 1.The argument invokes Lemma 13 after bounding the Hessian in (17).Source: B Proof of Lemma 1 · p. 16

C Proof of Lemma 14

  • Lemma 14 controls p(V, H, t) uniformly over ∥H∥F = ∥V∥F = 1 and t ≤ 1/24.The proof separates the second term from the first term q(V, H, t), then treats q through fixed-parameter bounds and uniformization.Source: C Proof of Lemma 14 · pp. 17–18

C.1 Bound with Fixed Matrices and Scalar

  • For fixed X and V independent of the measurement vectors, concentration and norm inequalities provide a lower bound for q(V, H, t).The proof defines centered variables Ti and applies Cauchy–Schwarz, Hölder’s inequality, Lemma 12, and Lemma 8.Source: §C.1 · pp. 18–20

C.2 Covering Arguments

  • ε-net coverings over V, H, and t extend the fixed-parameter bound to all admissible quantities with high probability.The resulting probability and sample-size conditions are stated in the covering argument, after which (42) and (50) are combined.Source: §C.2 · pp. 20–22

C.3 Finishing the Proof

  • The cited passage states that combining (42) and (50) can prove the result.Source: §C.3 · p. 22

D Proof of Lemma 2

The proof proceeds by comparing iterates along an interpolating path and applying Lemma 1 to control the resulting gradient expression. Orthogonal invariance and the fundamental theorem of calculus connect the intermediate identities.

D Proof of Lemma 2

  • The proof uses the identity ∇f(Xt)Qt = ∇f(XtQt) for Qt ∈ Or×r to rewrite the gradient term.This identity is used in deriving equations (51)–(53).Source: D Proof of Lemma 2 · p. 23
  • An interpolating path Xt(τ) with τ ∈ [0, 1] enables application of the fundamental theorem of calculus for vector-valued functions.The path is verified to satisfy condition (20) throughout the interval.Source: D Proof of Lemma 2 · p. 23
  • Applying Lemma 1 to the path and substituting the resulting inequalities yields the claimed conclusion.The final deduction follows after combining equations (53) and (55).Source: D Proof of Lemma 2 · p. 24

E Proof of Lemma 3

The proof of Lemma 3 bounds the relevant terms using induction hypotheses, norm inequalities, and path interpolation. Independence assumptions and a sample-size condition support the resulting bounds.

E Proof of Lemma 3

  • The first and second terms in (56) are bounded using the triangle inequality, Lemma 10, and induction hypotheses (28b) and (28c).Substitution into (56) produces the combined bound used later in the proof.Source: E Proof of Lemma 3 · p. 25
  • The proof applies the fundamental theorem of calculus along a path with τ ∈ [0, 1] to control a further gradient-related term.The resulting algebra follows the same bounding strategy used elsewhere in the appendix.Source: E Proof of Lemma 3 · p. 26
  • The induction argument closes when its constant inequalities hold, including C1 + C3 ≤ 1 and a sample-size condition of the form m ≥ cκ∥X♮∥.These conditions are invoked when applying the induction hypotheses.Source: E Proof of Lemma 3 · pp. 26–27

F Proof of Lemma 4

The proof of Lemma 4 uses independence, auxiliary lemmas, and a union bound, while the base-case proof of Lemma 5 verifies induction hypotheses through spectral perturbation bounds. Weyl’s inequality and Davis–Kahan control the relevant eigenspaces.

F Proof of Lemma 4

  • For each measurement index l, statistical independence permits application of Lemma 37 in [14], after which triangle and auxiliary lemma bounds are combined.The proof concludes with a union bound over all 1 ≤ l ≤ m.Source: F Proof of Lemma 4 · pp. 27–28

G Proof of Lemma 5

  • The base case t = 0 is handled by decomposing Z0 and Z0^(l) into orthonormal matrices and verifying the induction hypotheses one by one.The decomposition introduces complement matrices for the relevant subspaces.Source: G Proof of Lemma 5 · p. 28

G.1 Proof of (28a)

  • The proof of (28a) combines Lemma 6 with bounds from Lemmas 13 and 9, using Weyl’s inequality to control spectral quantities.The resulting estimates are obtained by substituting the intermediate bounds into (67).Source: §G.1 · pp. 28–29

G.2 Proof of (28b)

  • The proof of (28b) bounds each term in (69) using Lemmas 10 and 11, Weyl’s inequality, and the Davis–Kahan sin Θ theorem [45].The bounds are combined to obtain the desired induction estimate under an additional constant condition.Source: §G.2 · pp. 29–31

G.3 Proof of (28c)

The proof of (28c) combines earlier bounds and cited lemmas, yielding the stated order estimate before completing Lemma 5 by adjusting constants.

G.3 Proof of (28c)

  • r log n = O(nr3 log n) is obtained in the proof of (28c).Source: §G.3 · p. 31
  • The argument invokes Lemma 37 in [14] with appropriate constants.Source: §G.3 · p. 31
  • The intermediate relations are attributed to Lemmas 10 and 11 and to (28b).Source: §G.3 · p. 32

G.4 Finishing the Proof

  • The proof of Lemma 5 is completed by appropriately adjusting the constants.Source: §G.4 · p. 32

Related papers

Loading 1802.06286v2…