Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms

Andrew D. McRaeMath. Program 2026 · DOI

TL;DR

This paper proves that the standard matrix LASSO (nuclear-norm penalized linear least-squares) solution naturally yields a low-rank matrix, a property previously lacking rigorous proof. This finding has significant implications for developing efficient rank-constrained optimization algorithms, showing they can converge to the unique LASSO solution and that their optimization landscapes are well-behaved.

What Problem Does This Paper Address?

Estimating low-rank matrices from noisy linear measurements is a fundamental problem in many fields, from signal processing to machine learning. The matrix LASSO, a convex optimization problem, is a popular tool for this, as its nuclear norm penalty is known to encourage low-rank solutions. However, despite the penalty's intent, there was a theoretical gap: it wasn't rigorously proven that the solution itself would indeed be low-rank, especially in the presence of noise. This lack of proof hindered the development of specialized, more efficient algorithms that exploit this low-rank property. Furthermore, while nonconvex rank-constrained methods exist, they often require knowing the exact rank beforehand or suffer from complex optimization landscapes. This paper bridges this gap by proving the low-rank property of the LASSO solution and showing how this can be leveraged for better algorithms.

Methods

The paper's core contribution is a theoretical analysis that establishes the low-rank nature of the matrix LASSO solution under the Restricted Isometry Property (RIP) of the measurement operator. The authors first prove that under specific conditions (low-rank ground truth, RIP of the measurement operator, and appropriate regularization parameter), the LASSO solution is not only low-rank but also unique.

Building on this, they then analyze two classes of rank-constrained optimization algorithms:

  1. Projected Spectral Algorithm: This is an iterative algorithm that uses singular value thresholding. The authors show that under the same RIP conditions, this algorithm converges linearly to the unique LASSO solution.
  2. Burer-Monteiro Factorization: This approach reformulates the problem by factoring the matrix into two smaller matrices. The authors demonstrate that for this nonconvex formulation, all second-order critical points are globally optimal and yield the same unique LASSO solution.

The proofs rely on several technical tools, including subgradient analysis, properties of the nuclear norm, and the characterization of RIP.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The LASSO Solution is Inherently Low-Rank: The paper provides the first rigorous proof (to the authors' knowledge) that the matrix LASSO solution, under standard assumptions, is indeed low-rank, mirroring the rank of the underlying ground truth. This is a crucial theoretical underpinning for why LASSO works well for low-rank matrix recovery.
  • Uniqueness Under RIP: Beyond just low rank, the paper proves that the LASSO solution is unique under the stated conditions. This is a strong theoretical guarantee that simplifies algorithm design and analysis.
  • Bridging Convex and Nonconvex: The work elegantly connects the convex LASSO problem to nonconvex rank-constrained formulations. By showing that the LASSO solution is low-rank, it justifies using rank-constrained methods and proves that these methods can achieve the same optimal results as the convex LASSO, but potentially more efficiently.
  • Well-Behaved Nonconvex Landscapes: A significant finding is that the nonconvex optimization problems (both projected spectral and Burer-Monteiro) derived from the LASSO framework have benign global optimization landscapes. This means that algorithms are guaranteed to find the global optimum, avoiding the common pitfalls of getting stuck in poor local minima.

Key Results

  • Theorem 1: Under conditions of low-rank ground truth, RIP of the measurement operator, and appropriate regularization, the matrix LASSO problem has a unique solution whose rank is bounded by that of the ground truth (plus a small factor related to the RIP constant and noise).
  • Theorem 2: A projected spectral algorithm (iterative singular value thresholding) converges linearly to the unique LASSO solution when applied to a rank-constrained version of the problem, provided the optimization rank is chosen appropriately.
  • Theorem 3: For the Burer-Monteiro factored problem, all second-order critical points are global optima and yield the unique LASSO solution.
  • Corollary 1: Combines these results to show that efficient rank-constrained algorithms can find the unique LASSO solution with guaranteed convergence and global optimality.

Limitations and Future Work

  • RIP Assumption: The paper relies on the Restricted Isometry Property (RIP), which is a strong assumption. While it can hold with high probability for randomly constructed measurement matrices, it can be computationally expensive. The authors note that weaker conditions exist for accurate recovery in Frobenius norm (e.g., $\ell_1$-RIP), but their proof techniques do not directly extend to these. They suggest that adapting their results to weaker measurement assumptions is an important direction for future work.
  • Rank Determination: While the paper shows the LASSO solution has a rank close to the ground truth, it doesn't explicitly address how to determine the optimal rank parameter for the rank-constrained algorithms in practice. The authors mention that knowing the measurement operator allows for estimating the range of ranks for which RIP holds, which can guide this choice.
  • Generalization to Other Models: The authors highlight that their results are specific to the linear model with Gaussian noise. Extending these findings to other noise models or measurement models (e.g., non-linear measurements) would be valuable.
  • Practical Implementation: While theoretical guarantees are provided, the practical performance and computational advantages of these algorithms on real-world, large-scale datasets would be an interesting area for further investigation.

Summary updated

BibTeX
@article{mcrae2026low,
  author = {Andrew D. McRae},
  title = {{Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms}},
  journal = {Math. Program.},
  year = {2026},
  doi = {10.1007/s10107-025-02236-x},
}
Figure