2025/06/27 by Peng, Haiyang, Han, Deren, Huang, Meng
#65F35 #65H10 #94A12 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2506.22053
This paper investigates the stability of phase retrieval by analyzing the condition number of the nonlinear map Ψ_\boldsymbolA(\boldsymbolx) = (| ⟨ \boldsymbolaj, \boldsymbolx ⟩ |2 )1 ≤ j ≤ m, where \boldsymbolaj ∈ ℍn are known sensing vectors with ℍ ∈ \ℝ, ℂ\. For each p ≥ 1, we define the condition number β_Ψ_\boldsymbolAℓp as the ratio of optimal upper and lower Lipschitz constants of Ψ_\boldsymbolA measured in the ℓp norm, with respect to the metric \mathrm dist_ℍ(\boldsymbolx, \boldsymboly) = ‖\boldsymbolx \boldsymbolx^∗ - \boldsymboly \boldsymboly^∗‖_*. We establish universal lower bounds on β_Ψ_\boldsymbolAℓp for any sensing matrix \boldsymbolA ∈ ℍm × d, proving that β_Ψ_\boldsymbolAℓ1 ≥ π/2 and β_Ψ_\boldsymbolAℓ2 ≥ √(3) in the real case (ℍ = ℝ), and β_Ψ_\boldsymbolAℓp ≥ 2 for p=1,2 in the complex case (ℍ = ℂ). These bounds are shown to be asymptotically tight: both a deterministic harmonic frame \boldsymbolEm ∈ ℝm × 2 and Gaussian random matrices \boldsymbolA ∈ ℍm × d asymptotically attain them. Notably, the harmonic frame \boldsymbolEm ∈ ℝm × 2 achieves the optimal lower bound √(3) for all m ≥ 3 when p=2, thus serving as an optimal sensing matrix within \boldsymbolA ∈ ℝm × 2. Our results provide the first explicit uniform lower bounds on β_Ψ_\boldsymbolAℓp and offer insights into the fundamental stability limits of phase retrieval.