2025/10/26 by Xia, Yu, Xu, Zhiqiang · 1 citation
#46C05 #49N45 #94A12 #94A15 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2510.22578
Compressed sensing has demonstrated that a general signal \boldsymbolx ∈ \mathbbFn (\mathbbF∈ \ℝ,ℂ\) can be estimated from few linear measurements with an error proportional to the best k-term approximation error, a property known as instance optimality. In this paper, we investigate instance optimality in the context of phaseless measurements using the ℓp-minimization decoder, where p ∈ (0, 1], for both real and complex cases. More specifically, we prove that (2,1) and (1,1)-instance optimality of order k can be achieved with m =O(k log(n/k)) phaseless measurements, paralleling results from linear measurements. These results imply that one can stably recover approximately k-sparse signals from m = O(k log(n/k)) phaseless measurements. Our approach leverages the phaseless bi-Lipschitz condition. Additionally, we present a non-uniform version of (2,2)-instance optimality result in probability applicable to any fixed vector \boldsymbolx ∈ \mathbbFn. These findings reveal striking parallels between compressive phase retrieval and classical compressed sensing, enhancing our understanding of both phase retrieval and instance optimality.