Sample-Efficient Algorithms for Recovering Structured Signals From Magnitude-Only Measurements

Gauri Jagatap, Chinmay HegdeIEEE Trans. Information Theory 2019 · OpenReview

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:

  1. Initialization: A spectral technique is used to obtain a good initial estimate of the signal.
  2. 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

Abstract

We consider the problem of recovering a signal x* ∈ R <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> , from magnitude-only measurements, y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> = |〈a <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , x*〉| for i = {1, 2, ... , m}. This is a stylized version of the classical phase retrieval problem, and is a fundamental challenge in nanoand bio-imaging systems, astronomical imaging, and speech processing. It is well-known that the above problem is ill-posed, and therefore some additional assumptions on the signal and/or the measurements are necessary. In this paper, we consider the case where the underlying signal x* is s-sparse. For this case, we develop a novel recovery algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple and is obtained via a natural combination of the classical alternating minimization approach for phase retrieval with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that our algorithm achieves a sample complexity of O (s <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log n) with Gaussian measurements ai, which matches the best known existing results; moreover, it also demonstrates linear convergence in theory and practice. An appealing feature of our algorithm is that it requires no extra tuning parameters other than the signal sparsity level s. Moreover, we show that our algorithm is robust to noise. The quadratic dependence of sample complexity on the sparsity level is suboptimal, and we demonstrate how to alleviate this via additional assumptions beyond sparsity. First, we study the (practically) relevant case where the sorted coefficients of the underlying sparse signal exhibit a power law decay. In this scenario, we show that the CoPRAM algorithm achieves a sample complexity of O (s log n), which is close to the information-theoretic limit. We then consider the case where the underlying signal x* arises from structured sparsity models. We specifically examine the case of block-sparse signals with uniform block size of b and block sparsity k = s/b. For this problem, we design a recovery algorithm that we call Block CoPRAM that further reduces the sample complexity to O (ks logn). For sufficiently large block lengths of b = O(s), this bound equates to O (slogn). To our knowledge, our approach constitutes the first family of linearly convergent algorithms for signal recovery from magnitude-only Gaussian measurements that exhibit a sub-quadratic dependence on the signal sparsity level.
BibTeX
@article{jagatap2019sample,
  author = {Gauri Jagatap and Chinmay Hegde},
  title = {{Sample-Efficient Algorithms for Recovering Structured Signals From Magnitude-Only Measurements}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=GbvAFhTE1lQ},
}
Figure