arXiv:2608.22418 · v2

Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing

首次提交 2026-08-23 21:46

版本更新 2026-11-01 22:36

雷达观测 2026-11-04 23:43

摘要

In this paper we focus on the stability of positive semidefinite matrix sensing maps $Φ_{\mathcal{A}}=(\langle A_i,X\rangle)_{i=1}^m$ where $A_i\succeq 0$, $X\succeq0$ and $\operatorname{rank}(X)\le r$. We introduce the bi-Lipschitz constants of $Φ_{\mathcal{A}}$ 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 $\mathbb R$ 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 $\ell_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.