Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO

arXiv:2608.29018v1 Announce Type: cross Abstract: We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank r_{star}, if the rank-k RIP constant satisfies elta<elta_{sharp}(k/r_{star}), where elta_{sharp}(t)=t/(4-t) for 0<t<4/3 and elta_{sharp}(t)=sqrt{(t-1)/t} for tge4/3, then every global minimizer has Frobenius error lesssimsqrt{r_{star}}lambda for all lambdagtrsim|A^{*}(xi)|{op} and at every search rank rge r{star}. The constants depend only on the RIP constant and t=k/r_{star}, and in particular are independent of the search rank. When the rank restriction is inactive, the result specializes to the ordinary convex matrix LASSO. We also obtain the analogous results for sparsity-restricted vector LASSO. Conversely, we show that the threshold elta<elta_{sharp}(k/r_{star}) cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.

Related

• The Sharp Phase Transition of Tyler's M-Estimator for Robust Subspace Recovery
• Matrix Completion with Hypergraphs:Sharp Thresholds and Efficient Algorithms
• Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression

Source: arXiv cs.LG | 2026-09-01