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

Abstract

We show that solutions to the popular convex matrix LASSO problem (nuclear-norm--penalized linear least-squares) have low rank under similar assumptions as required by classical low-rank matrix sensing error bounds. Although the purpose of the nuclear norm penalty is to promote low solution rank, a proof has not yet (to our knowledge) been provided outside very specific circumstances. Furthermore, we show that this result has significant theoretical consequences for nonconvex rank-constrained optimization approaches. Specifically, we show that if (a) the ground truth matrix has low rank, (b) the (linear) measurement operator has the matrix restricted isometry property (RIP), and (c) the measurement error is small enough relative to the nuclear norm penalty, then the (unique) LASSO solution has rank (approximately) bounded by that of the ground truth. From this, we show (a) that a low-rank--projected proximal gradient descent algorithm will converge linearly to the LASSO solution from any initialization, and (b) that the nonconvex landscape of the low-rank Burer-Monteiro--factored problem formulation is benign in the sense that all second-order critical points are globally optimal and yield the LASSO solution.

References in corpus (12)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• An overview of low-rank matrix recovery from incomplete observations
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Estimation of high-dimensional low-rank matrices
• A Geometric Analysis of Phase Retrieval
• Optimal selection of reduced rank estimators of high-dimensional matrices
• Global Optimality in Low-rank Matrix Optimization
• The Non-convex Geometry of Low-rank Matrix Optimization
• ROP: Matrix recovery via rank-one projections
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• A Deterministic Theory for Exact Non-Convex Phase Retrieval
• Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization