TL;DR
This paper introduces CoPRAM and Block CoPRAM, novel algorithms for recovering signals from magnitude-only measurements (phase retrieval). These algorithms achieve state-of-the-art sample efficiency, especially for structured sparse signals, by combining sparse recovery techniques with alternating minimization, and offer robust performance with fewer parameters than existing methods.
What Problem Does This Paper Address?
The paper tackles the challenging problem of phase retrieval, where we aim to reconstruct a signal from measurements of its magnitude only. This is crucial in fields like imaging (X-ray, microscopy) and signal processing, where sensors can only capture intensity, not phase information. The standard phase retrieval problem is notoriously ill-posed and computationally hard (NP-hard). While previous work has made progress by assuming signals are s-sparse (meaning most of their coefficients are zero in some basis), existing algorithms still require a significant number of measurements, often quadratically dependent on the sparsity level ($O(s^2 \log n)$), which is suboptimal. This paper aims to develop more sample-efficient algorithms that require fewer measurements, particularly by leveraging more refined signal structures beyond simple sparsity.
Methods
The authors propose two main algorithms:
- CoPRAM (Compressive Phase Retrieval with Alternating Minimization): This algorithm combines the classical alternating minimization approach for phase retrieval with the CoSaMP algorithm for sparse recovery. It's designed for s-sparse signals. A key innovation is a robust initialization procedure that doesn't require prior knowledge of the signal's exact support or minimum coefficient value, unlike some prior methods. It also requires fewer tuning parameters.
- Block CoPRAM: This is an extension of CoPRAM designed for structured sparsity, specifically block-sparse signals. In block sparsity, non-zero elements are constrained to appear in contiguous blocks. This algorithm leverages this block structure to further reduce sample complexity.
Both algorithms follow a two-stage process:
- Initialization: A spectral technique is used to obtain a good initial estimate of the signal.
- Descent: An alternating minimization procedure refines the estimate by iteratively updating the signal and its phase.
Datasets
Not discussed in the paper. The experiments use synthetic data generated according to specific signal models (sparse, block-sparse, power-law decay) and sensing matrices (Gaussian). Real image data is also used for demonstration.
Key Insights and Ideas
- Structured Sparsity is Key: The paper strongly emphasizes that moving beyond simple sparsity to structured sparsity (like block sparsity or power-law decay) is crucial for achieving significant improvements in sample efficiency.
- CoPRAM's Simplicity and Robustness: The proposed CoPRAM algorithm is notable for its simplicity, combining existing powerful tools (alternating minimization and CoSaMP) in a novel way. Its robustness to noise and requirement for fewer tuning parameters make it practically appealing.
- Bridging Theory and Practice: The algorithms are designed to be theoretically sound (achieving near-optimal sample complexities) while also being practically implementable and efficient.
- Power-Law Decay Advantage: The insight that signals with coefficients following a power-law decay can be recovered with significantly fewer samples ($O(s \log n)$) than general sparse signals ($O(s^2 \log n)$) is a key theoretical finding.
Key Results
- CoPRAM for s-sparse signals: Achieves a sample complexity of $O(s^2 \log n)$ with Gaussian measurements, matching the best known results, and demonstrates linear convergence. It's robust to noise and requires no extra tuning parameters beyond the sparsity level $s$.
- CoPRAM for power-law decaying signals: Achieves a sample complexity of $O(s \log n)$, which is close to the information-theoretic limit, by leveraging the specific decay structure of signal coefficients.
- Block CoPRAM for block-sparse signals: Achieves a sample complexity of $O(ks \log n)$, where $k$ is the block sparsity. For large block sizes, this further reduces to $O(s \log n)$, again approaching the information-theoretic limit.
- Comparative Performance: Numerical experiments show that Block CoPRAM outperforms other state-of-the-art algorithms in terms of sample complexity, especially as sparsity increases. CoPRAM and Block CoPRAM also demonstrate competitive running times.
Limitations and Future Work
- Gaussian Measurements: The theoretical analysis primarily applies to Gaussian random measurements. Extending the results to more realistic measurement schemes like Fourier samples or coded diffraction patterns is an open research direction.
- Initialization-Free Algorithms: The current algorithms rely on a specific initialization stage. Developing initialization-free algorithms for sparse phase retrieval is mentioned as a future work.
- More Sophisticated Sparsity Models: The paper focuses on block sparsity and power-law decay. Expanding the analysis to other structured sparsity models like clusters, trees, groups, and graphical models is suggested.
- Non-uniform Block Sizes: While the paper briefly discusses extending to non-uniform block sizes for 1D signals, a more general treatment for higher-dimensional data is left for future work.
Summary updated