Achieving Optimal Sample Complexity for a Broader Class of Signals in Sparse Phase Retrieval
This work addresses a gap between theory and practice in signal processing for researchers, though it is incremental as it builds on prior methods to expand applicability.
The paper tackles the problem of sparse phase retrieval, where existing algorithms fail to achieve optimal sample complexity for a broad class of signals, and introduces gESP to extend optimal recovery to more signal types, with simulations showing it outperforms state-of-the-art methods.
Sparse phase retrieval aims to recover a $k$-sparse signal from $m$ phaseless measurements. While the theoretically optimal sample complexity for successful recovery is $Ω(k \log n)$, existing algorithms can only achieve this bound for signals with specific structural assumptions, leading to a notable gap between theory and practice. To bridge this gap, we introduce an efficient initialization algorithm, termed generalized Exponential Spectral Pursuit (gESP). We prove that gESP can significantly expand the family of signals that are guaranteed to be recovered with the optimal sample complexity, thereby extending the scope of theoretical optimality to a much broader class of signals. Extensive simulations validate our theoretical findings and demonstrate that gESP consistently outperforms the state-of-the-art methods across diverse signal types.