Escape-Through-a-Mesh Null-Space Phase Transition Thresholds for Nuclear Norm and PSD Trace Minimization

A high-dimensional random-matrix and Grassmannian escape-through-a-mesh phase-transition methodology (introduced by Samet Oymak and Babak Hassibi in 2010) that derives explicit asymptotic sampling thresholds $\mu = m / n^2$ (and $\mu = m / (n(n+1)/2)$ for symmetric positive semidefinite matrices) as a function of normalized rank $\beta = r / n \in (0, 1)$ for exact recovery of rank-$r$ matrices $X_0 \in \mathbb{R}^{n \times n}$ from i.i.d. Gaussian linear measurements $y_0 = \mathcal{A}(X_0) \in \mathbb{R}^m$ via convex nuclear norm minimization $\min_X \|X\|_\star \text{ s.t. } \mathcal{A}(X) = \mathcal{A}(X_0)$ (Equation 2) and positive semidefinite (PSD) trace minimization $\min_X \operatorname{trace}(X) \text{ s.t. } \mathcal{A}(X) = \mathcal{A}(X_0),\, X \succeq 0$ (Equation 113). Combining exact Strong ($2\|W\|_r < \|W\|_\star$, Lemma 6), Sectional ($\|(I - P)W(I - Q^\top)\|_\star > \|PWQ^\top\|_\star$, Lemma 10), and Weak ($\operatorname{trace}(U^\top WV) + \|\bar{U}^\top W\bar{V}\|_\star > 0$, Lemma 13) null-space characterizations with Gordon's Escape-Through-a-Mesh theorem (Theorem 1), Stojnic's tail-thresholding variational bound (Lemmas 7, 11, 14), and the incomplete moments $\gamma(\beta) = \int_{F^{-1}(1 - \beta)}^2 x\phi(x)\,dx$ and $\gamma_2(\beta) = \int_{F^{-1}(1 - \beta)}^2 x^2\phi(x)\,dx$ of the Marchenko–Pastur quarter-circle singular-value law $\phi(x) = \frac{\sqrt{4 - x^2}}{\pi}$ (and Wigner semicircle law $\phi_s(x) = \frac{\sqrt{4 - x^2}}{2\pi}$ for the Gaussian Orthogonal/Unitary Ensemble $\mathcal{D}(n)$), Theorems 2–6 yield closed-form fixed-point curves $\mu_{\mathrm{strong}}(\beta)$, $\mu_{\mathrm{sec}}(\beta)$, $\mu_{\mathrm{weak}}(\beta)$, $\mu_{\mathrm{PSD,weak}}(\beta)$, and $\mu_{\mathrm{PSD,strong}}(\beta)$ that overcome the $\beta \to 0$ floor $1 - \frac{64}{9\pi^2} \approx 0.2795$ of earlier null-space bounds and demonstrate that weak recovery requires at most $3\times$ the degrees-of-freedom complexity $\theta(\beta) = \beta(2 - \beta)$.