Müntz--Szász Geometric Separation and Computational Complexity of Sparse Recovery in Ultra Coherent Dictionaries

We study sparse recovery in an ultra-coherent dictionary formed by one algebraic singular atom and an orthonormal polynomial block. The key geometric quantity is a separation margin $\kappa(\alpha,K)$ defined as the $L^{2}(\mu)$ distance between the normalized singular atom and the polynomial subspace, together with its uniform version $K_{pop}$. We show that the population support-block minimum eigenvalue is lower bounded at the $k_{pap}^{2}$ scale through the Friedrichs-angle geometry. For finite samples, entry-wise concentration gives a sufficient sample size with quadratic dependence on sparsity $s$, logarithmic dependence on dictionary size $D$, and inverse quartic dependence on $K_{Pop}$. Under a support-block small-ball condition with constants $(p_{0},u_{0})$, the dependence on $s$ improves to linear up to logarithmic factors. This improvement is conditional, and uniform analytic lower bounds for Jacobi ensembles with $K\sim s$ are currently unavailable. Numerical diagnostics report $p_{0}\approx0.781$ at $u_{0}=0.1$ for $s=20$, and fourth-moment growth $||B||_{op}\sim s^{1.809}$ which supports anti-concentration as the relevant mechanism in this regime.