Low-rank regularization and solution uniqueness in over-parameterized matrix sensing

Kelly Geyer, Anastasios Kyrillidis, Amir KalevAISTATS 2020 · OpenReview

Abstract

We consider the question whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit low-rank regularization. We focus on the noiseless matrix sensing scenario and demonstrate that the Positive Semi-Definite (PSD) constraint alone can be sufficient to guarantee solution uniqueness, effectively rendering the choice of optimization algorithm secondary to the problem's geometric constraints.

Introduction

In modern machine learning, we often use "over-parameterized" models—models with far more parameters than data points. Theoretically, these models should be able to fit the training data in infinitely many ways, most of which would generalize poorly. However, in practice, simple algorithms like gradient descent consistently find "simple" solutions (like low-rank matrices) that work well on new data.

This phenomenon is often called implicit regularization or algorithmic bias. The idea is that the way the algorithm moves through the parameter space somehow biases it toward better solutions. This paper asks a fundamental question: Is it really the algorithm doing the work, or is it the geometry of the problem itself? Specifically, the authors investigate if the requirement that a matrix be Positive Semi-Definite (PSD) is enough to guarantee a unique, low-rank solution without needing any extra "algorithmic magic."

Methods

The authors provide a theoretical proof and numerical evidence to support their claim. Their approach involves:

  1. Change of Variables: Introducing a mathematical transformation that maps the original sensing problem into a new space.
  2. Trace Constancy: Showing that after this transformation, every PSD matrix consistent with the observed data must have the exact same trace.
  3. RIP Analysis: By assuming the sensing mechanism satisfies a version of the Restricted Isometry Property (RIP), they prove that the set of consistent PSD matrices collapses into a singleton (a set containing only one element).
  4. Wishart Sensing Matrices: Specifically analyzing sensing maps comprised of Wishart matrices, proving they satisfy the necessary conditions for this uniqueness to occur.

Experimental Setup

The paper relies on controlled simulations to verify its theoretical claims:

  • Simulated Matrix Sensing: Generating synthetic ground-truth low-rank PSD matrices and sampling them using random Gaussian or Wishart sensing matrices.
  • Quantum State Tomography (QST): Applying findings to a real-world physics problem where researchers reconstruct the "density matrix" of a quantum system (which is naturally PSD and often low-rank) from experimental measurements.

Results and Discussion

The authors' numerical experiments strongly support their "singleton" theory. As seen in Figure 1, methods that enforce the PSD constraint (the blue and yellow lines) achieve near-zero error with significantly fewer measurements ($m \approx 72$) than unconstrained least squares (the red line), which requires the full $m=120$ measurements to succeed.

Error vs. number of measurements for different optimization methods. PSD-constrained methods find the solution much earlier.

Furthermore, the results demonstrate that if the feasible set (the collection of all matrices that fit the data and are PSD) is a singleton, then the choice of optimization objective doesn't actually matter for the final result. Whether minimizing the nuclear norm, the Frobenius norm, or using least squares, the algorithms all converge to essentially the same solution, as shown in Table 1.

Table 1 shows that different optimization objectives lead to the same distance from the ground truth $X^*$.

This suggests that the "implicit bias" of algorithms might sometimes just be the algorithm successfully finding the only valid solution that exists. Previous work suggested that factorizing a matrix as $X = UU^\top$ and running gradient descent on $U$ introduces a specific low-rank bias; this paper argues that if the solution is unique, this factorization is just one of many ways to reach the same inevitable destination.

Conclusion

This work highlights the "Power of Positivity," suggesting that just as non-negativity can guarantee uniqueness for sparse vectors, the PSD constraint can guarantee uniqueness for low-rank matrices.

However, the study notes limitations, such as the focus on the noiseless case. In the presence of noise, the "singleton" might expand into a small region, and the specific bias of an algorithm could become important again. Future research will explore less restrictive conditions than RIP to see how far this "uniqueness by constraint" principle extends.

Summary updated

Abstract

We consider the question whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit low-rank regularization.We focus on the noiseless matrix sensing scenario o...
BibTeX
@inproceedings{geyer2020low,
  author = {Kelly Geyer and Anastasios Kyrillidis and Amir Kalev},
  title = {{Low-rank regularization and solution uniqueness in over-parameterized matrix sensing}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=S-1-B1iQn8E},
}
Figure