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

Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing

  • Mingxuan Sun
  • Zhiqiang Xu
Open at sourcePDFDOICite

Abstract

In this paper we focus on the stability of positive semidefinite matrix sensing maps Φ𝒜=(⟨ Ai,X⟩)i=1m where Ai⪰ 0, X⪰0 and rank(X)≤ r. We introduce the bi-Lipschitz constants of Φ𝒜 and define the global condition numbers as the ratio of upper and lower Lipschitz constants. We give deterministic universal lower bounds for these condition numbers that depend only on the rank r and on the underlying field. We then show that rank-one Gaussian measurements asymptotically attain these bounds, except for the operator-norm condition number over ℝ when r=1. For this exceptional case, we establish a sharper universal lower bound and prove its asymptotic sharpness. As an application, we derive stability guarantees for an ℓ1-residual PhaseLift-type estimator at the optimal sampling scale. These results identify the intrinsic limits of conditioning in positive semidefinite matrix sensing and connect these limits to stable low-rank recovery.

Related

  1. On Completely Positive and Semidefinite Programs for Moment Bounds on Maximum of Random Quadratics
    Buse Unluturk, Divya Padmanabhan, Karthik Natarajan
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. Comparison theorems for the minimum eigenvalue of a random positive-semidefinite matrix
    Joel A. Tropp
    Communications of the American Mathematical SocietyPeer-reviewedCC BY-NC-ND20 citedStatisticsOpenAlex
  3. Optimal solution ranks in the Max-Cut semidefinite relaxation
    Avinash Bhardwaj, Vishnu Narayanan
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  4. Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
    Avinash Bhardwaj, Chen Chen, Vishnu Narayanan
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Sharp Edge-Edit Bounds at Every Level for Leaky Positive Semidefinite Forcing
    Domenico Frijio
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{sun2026optimal,
  title = {{Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing}},
  author = {Mingxuan Sun and Zhiqiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2608.22418},
  eprint = {2608.22418},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.22418},
}
RIS
TY  - UNPB
TI  - Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing
AU  - Mingxuan Sun
AU  - Zhiqiang Xu
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2608.22418
UR  - https://arxiv.org/abs/2608.22418
AB  - In this paper we focus on the stability of positive semidefinite matrix sensing maps Φ_𝒜=(⟨ A_i,X⟩)_i=1^m where A_i⪰ 0, X⪰0 and rank(X)≤ r. We introduce the bi-Lipschitz constants of Φ_𝒜 and define the global condition numbers as the ratio of upper and lower Lipschitz constants. We give deterministic universal lower bounds for these condition numbers that depend only on the rank r and on the underlying field. We then show that rank-one Gaussian measurements asymptotically attain these bounds, except for the operator-norm condition number over ℝ when r=1. For this exceptional case, we establish a sharper universal lower bound and prove its asymptotic sharpness. As an application, we derive stability guarantees for an ℓ_1-residual PhaseLift-type estimator at the optimal sampling scale. These results identify the intrinsic limits of conditioning in positive semidefinite matrix sensing and connect these limits to stable low-rank recovery.
ER  -