Nonconvex Matrix Factorization from Rank-One Measurements

Yuanxin Li, Cong Ma, Yuxin Chen, Yuejie Chi

Abstract

We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including phase retrieval, quantum state tomography, and learning shallow neural networks. We demonstrate that a simple, "vanilla" gradient descent algorithm can perfectly recover low-rank matrices from rank-one measurements with near-optimal efficiency. By uncovering a phenomenon called implicit regularization, we show that the algorithm naturally stays within a well-behaved geometric region, eliminating the need for complex algorithmic "hacks" like data resampling or explicit regularization.

1. Introduction

Reconstructing high-dimensional matrices from limited "rank-one" quadratic measurements is a fundamental challenge in several domains, including X-ray crystallography (phase retrieval), quantum state tomography, and the theoretical understanding of neural networks with quadratic activations. The primary difficulty stems from the nonconvexity of the least-squares loss function, which typically features numerous local minima and saddle points that can trap standard optimization algorithms.

Historically, researchers circumvented these issues using either computationally expensive convex relaxations (e.g., nuclear norm minimization) or nonconvex methods requiring "resampling"—using fresh data at every iteration to maintain independence. However, in practice, data is finite. This work investigates whether standard gradient descent, utilizing the same data throughout, can achieve reliable recovery.

2. Methodology

The proposed approach follows a two-stage pipeline:

  1. Spectral Initialization: A starting point is found by calculating the top eigenvectors of a weighted sum of the measurement matrices, placing the initial guess within the basin of attraction of the global optimum.
  2. Vanilla Gradient Descent: From the initial guess, the algorithm follows the negative gradient of the loss function. Crucially, this is a "vanilla" implementation: it lacks explicit regularization terms, projection steps, or data resampling. A constant step size is maintained throughout.

3. Implicit Regularization and Convergence

The core theoretical contribution is the identification of implicit regularization. Standard theory suggests that without explicit constraints, gradient descent might enter regions where the loss landscape is poorly behaved. We prove that the iterates naturally remain "incoherent" with respect to the measurement vectors, a property analyzed via a "leave-one-out" proof technique.

Convergence of relative estimation error and the relative incoherence condition across iterations.

As shown in Figure 3, both the estimation error and the incoherence condition decrease linearly. The algorithm stays within a "Region of Incoherence and Contraction" (RIC) where the loss function behaves as if it were locally strongly convex and smooth. This allows for significantly larger step sizes than previously theorized, leading to much faster convergence.

4. Sample Complexity and Numerical Results

The theoretical analysis establishes near-optimal guarantees for both data and computation. For an $n \times n$ matrix of rank $r$, the required sample complexity is $O(nr^4 \log n)$. Computationally, the algorithm achieves linear convergence, requiring only $O(r^2 \log(1/\epsilon))$ iterations to reach an accuracy of $\epsilon$.

Success rate of matrix recovery vs. the normalized number of measurements m/(nr).

Empirical results (Figure 4) validate these findings, showing a sharp phase transition in the success rate. The algorithm consistently recovers the ground truth once the number of measurements $m$ exceeds approximately 4 times the degrees of freedom ($nr$).

5. Conclusion and Future Work

This work provides the first theoretical guarantee for the near-optimal recovery of low-rank matrices from rank-one measurements using vanilla gradient descent. While the current proof assumes Gaussian measurements, simulations suggest robustness to other distributions and additive noise. Future research will focus on extending these implicit regularization insights to deeper network architectures and non-Gaussian measurement models.

Summary updated

Abstract

We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including phase retrieval, quantum state tomography, and learning shallo...
BibTeX
@inproceedings{li2019nonconvex,
  author = {Yuanxin Li and Cong Ma and Yuxin Chen and Yuejie Chi},
  title = {{Nonconvex Matrix Factorization from Rank-One Measurements}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=WtP_yCMYpdO},
}
Figure