Recovery Guarantees of the Matrix Lasso Problem: On Equivalence of Convex and Non-Convex Formulations

Abstract

We study matrix sensing through the convex matrix-lasso relaxation, where the nuclear norm replaces rank. We show that the relaxation can certifiably recover a low-rank ground-truth matrix and establish a connection to its Burer–Monteiro factorization. The guarantees extend to finite-variance noise and clarify the relationship between convex and non-convex formulations.