Nonconvex Matrix Factorization From Rank-One Measurements

Yuanxin Li, Cong Ma, Yuxin Chen, Yuejie Chi

Introduction

Recovering low-rank matrices from limited measurements is a fundamental problem in signal processing, machine learning, and quantum mechanics. While convex relaxation methods offer strong theoretical guarantees, they often suffer from high computational costs. Nonconvex approaches, particularly gradient descent, are more efficient in practice but have historically been difficult to analyze without artificial constraints like "sample splitting" or explicit regularization.

This paper provides a breakthrough theoretical guarantee: a simple, "vanilla" gradient descent algorithm can recover low-rank matrices from rank-one measurements with near-optimal efficiency. The success of this approach is attributed to an implicit regularization phenomenon, where the algorithm naturally remains within a well-behaved geometric region throughout its execution.

The Problem: Rank-One Measurements

The authors address the challenge of recovering a hidden low-rank matrix $M^\natural$ from quadratic sketches of the form: $$y_i = a_i^\top M^\natural a_i$$ This mathematical structure is central to several high-impact applications:

  • Phase Retrieval: Reconstructing signals from intensity measurements in X-ray crystallography.
  • Covariance Sketching: Estimating data statistics under memory constraints.
  • Quantum State Tomography: Reconstructing quantum system states.
  • Neural Networks: Learning shallow networks with quadratic activation functions.

The objective function—a least-squares empirical risk—is a degree-4 polynomial, making the problem highly nonconvex. Previous theoretical solutions often relied on "sample splitting" (using fresh data for every iteration) to maintain statistical independence, which is highly data-inefficient.

The Vanilla Gradient Descent Approach

The proposed method utilizes a two-stage approach without any explicit regularization, projections, or truncations:

  1. Spectral Initialization: The algorithm begins with a "warm start" by computing the top eigenvectors of a weighted sum of the measurement vectors. This provides an initial estimate sufficiently close to the global optimum.
  2. Vanilla Gradient Descent: From this starting point, the algorithm follows the gradient of the loss function using the entire dataset at every step.

By avoiding sample splitting, the method achieves significantly better data efficiency than earlier theoretical models.

Theoretical Insights: Implicit Regularization

The core contribution of this work is the discovery of the Implicit Regularization phenomenon. The authors prove that gradient descent iterates automatically stay within a Region of Incoherence and Contraction (RIC).

In this region, the estimate remains "incoherent" (not overly aligned) with the measurement vectors. This is crucial because, within the RIC, the loss function is much "smoother" than it is globally. Specifically, the local smoothness parameter scales with $O(\max\{r, \log n\})$ rather than $O(n^2)$. This improved smoothness allows the algorithm to use much larger, more aggressive step sizes, leading to rapid convergence.

To prove this, the authors employ a "leave-one-out" trick, comparing the actual trajectory of the algorithm to auxiliary trajectories that omit one measurement at a time to exploit statistical independence.

Comparison with Prior Art

The theoretical analysis establishes that for a matrix of size $n \times n$ and rank $r$, the algorithm achieves near-optimal performance across several metrics.

Comparison of sample and computational complexities for various low-rank matrix recovery algorithms.

As shown in the table above, the proposed GD algorithm (Algorithm 1) significantly outperforms previous analyses of gradient descent (e.g., GD [11]). It achieves a sample complexity of $O(nr^4 \log n)$, which is nearly the information-theoretic limit when $r$ is small. Furthermore, the computational cost scales linearly with the size of the data ($mn$), making it as fast as reading the input data itself.

Conclusion and Future Work

This work demonstrates that simple nonconvex algorithms can be both theoretically robust and computationally efficient for matrix recovery. However, some challenges remain. The current proofs rely on i.i.d. Gaussian measurement designs, whereas real-world applications like optics often involve structured measurements (e.g., Coded Diffraction Patterns). Additionally, while this study focuses on positive semidefinite (PSD) matrices, extending these implicit regularization insights to general rectangular low-rank matrices and other neural network activation functions (like ReLU) represents a promising direction for future research.

Summary updated

Abstract

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 least-squares loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is bounded by a constant, 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.
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