Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
Information TheoryMachine Learning
Summary
The authors find the exact condition under which a version of the matrix LASSO method can accurately recover a low-rank matrix from noisy data. They show that if a certain property of the measurement operator (called the restricted isometry property or RIP) is below a specific threshold depending on the rank ratio, then all best solutions are close to the true matrix. Their results apply even if the search allows higher rank matrices, and also extend to the usual (non-rank-restricted) matrix LASSO and to vector LASSO with sparsity. They further prove that this threshold is the best possible by providing counterexamples when it is exceeded.
Authors
Richard Y. Zhang
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 $δ<δ_{\mathrm{sharp}}(k/r_{\star})$, where $δ_{\mathrm{sharp}}(t)=t/(4-t)$ for $0<t<4/3$ and $δ_{\mathrm{sharp}}(t)=\sqrt{(t-1)/t}$ for $t\ge4/3$, then every global minimizer has Frobenius error $\lesssim\sqrt{r_{\star}}λ$ for all $λ\gtrsim\|\mathcal{A}^{*}(ξ)\|_{\mathrm{op}}$ and at every search rank $r\ge 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 $δ<δ_{\mathrm{sharp}}(k/r_{\star})$ cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.