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 𝜅(𝛼, 𝐾), defined as the 𝐿 2 (𝜇) distance between the normalized singular atom and the polynomial subspace, together with its uniform version 𝜅 pop. We show that the population support-block minimum eigenvalue is lower bounded at the 𝜅 2 pop scale through the Friedrichs-angle geometry. For finite samples, entry-wise concentration gives a sufficient sample size with quadratic dependence on sparsity 𝑠, logarithmic dependence on dictionary size 𝐷, and inverse quartic dependence on 𝜅 pop. Under a support-block small-ball condition with constants (𝑝 0 , 𝑢 0), the dependence on 𝑠 improves to linear up to logarithmic factors. This improvement is conditional, and uniform analytic lower bounds for Jacobi ensembles with 𝐾 ∼ 𝑠 are currently unavailable. Numerical diagnostics report 𝑝 0 ≈ 0.781 at 𝑢 0 = 0.1 for 𝑠 = 20, and fourth-moment growth ‖𝐁‖ op ∼ 𝑠 1.809 , which supports anti-concentration as the relevant mechanism in this regime.