Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 42 min ago
PreprintarXiv licencearXiv

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

  • Richard Y. Zhang
Open at sourcePDFDOICite

Abstract

We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank r⋆, if the rank-k RIP constant satisfies δ<δsharp(k/r⋆), where δsharp(t)=t/(4−t) for 0<t<4/3 and δsharp(t)=√((t−1)/t) for t≥4/3, then every global minimizer has Frobenius error ≲√(r⋆)λ for all λ≳|𝒜*(ξ)|op and at every search rank r≥ r⋆. The constants depend only on the RIP constant and t=k/r⋆, 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 δ<δsharp(k/r⋆) cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.

Related

  1. Rank-one Factored Gradient Descent without Restricted Isometry: Application to Quantum Pure State Tomography on Multi-Qubits
    Takahiro Kajisa
    arXivPreprintCC BY 4.0Full textOptimisation & controlQuantum physics & quantum informationarXiv
  2. Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
    Xunmeng Wu, Jian-Feng Cai, Zongben Xu +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  3. Fourier Ratio and Restricted Isometry via Entropic Descent
    Will Burstein, Alex Iosevich, Ben Krause
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  4. Restricted Coprime Representations Modulo 6P: Exact CRT Formulas and Positivity Thresholds
    Andres M. Salazar
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv
  5. Multiplicator freeness for restricted-ramification Galois groups over global function fields
    Qi Liu, Zugan Xing
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{zhang2026sharp,
  title = {{Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO}},
  author = {Richard Y. Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.29018},
  eprint = {2608.29018},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.29018},
}
RIS
TY  - UNPB
TI  - Sharp Restricted Isometry Thresholds for Global Minima of Rank-Restricted Matrix LASSO
AU  - Richard Y. Zhang
PY  - 2026
DA  - 2026/08/29
PB  - arXiv
DO  - 10.48550/arxiv.2608.29018
UR  - https://arxiv.org/abs/2608.29018
AB  - We determine the sharp restricted isometry threshold for recovery at global minima of the rank-restricted matrix LASSO. For target rank r_⋆, if the rank-k RIP constant satisfies δ<δ_sharp(k/r_⋆), where δ_sharp(t)=t/(4−t) for 0<t<4/3 and δ_sharp(t)=√((t−1)/t) for t≥4/3, then every global minimizer has Frobenius error ≲√(r_⋆)λ for all λ≳|𝒜^*(ξ)|_op and at every search rank r≥ r_⋆. The constants depend only on the RIP constant and t=k/r_⋆, 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 δ<δ_sharp(k/r_⋆) cannot be improved, due to the existence of counterexamples whose global minimizers fail to recover the ground truth.
ER  -