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:
- 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.
- 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.
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