Achieving Optimal Sample Complexity for a Broader Class of Signals in Sparse Phase Retrieval
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910077200367616 |
|---|---|
| author | Xu, Mengchu Zhang, Yuxuan Wang, Jian |
| author_facet | Xu, Mengchu Zhang, Yuxuan Wang, Jian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_01335 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Achieving Optimal Sample Complexity for a Broader Class of Signals in Sparse Phase Retrieval Xu, Mengchu Zhang, Yuxuan Wang, Jian Information Theory 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. |
| title | Achieving Optimal Sample Complexity for a Broader Class of Signals in Sparse Phase Retrieval |
| topic | Information Theory |
| url | https://arxiv.org/abs/2503.01335 |