  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.
