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

DOI10.1109/TIT.2019.2902924MaRDI QIDQ5224084zbMATH OpenOpenAlexWikidataFDO

Authors Gauri Jagatap, Chinmay Hegde

Publication date 19 July 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.06412

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: We consider the problem of recovering a signal $mathbf{x}^{\ast }inmathbf{R}^n$, from magnitude-only measurements $y_i=|leftlanglemathbf{a}_i,mathbf{x}^{\ast }ightangle|$ for $i=[m]$. Also called the phase retrieval, this is a fundamental challenge in bio-,astronomical imaging and speech processing. The problem above is ill-posed; additional assumptions on the signal and/or the measurements are necessary. In this paper we first study the case where the signal $mathbf{x}^{\ast }$ is $s$-sparse. We develop a novel algorithm that we call Compressive Phase Retrieval with Alternating Minimization, or CoPRAM. Our algorithm is simple; it combines the classical alternating minimization approach for phase retrieval with the CoSaMP algorithm for sparse recovery. Despite its simplicity, we prove that CoPRAM achieves a sample complexity of $O(s^{2}logn)$ with Gaussian measurements $mathbf{a}_i$, matching the best known existing results; moreover, it demonstrates linear convergence in theory and practice. Additionally, it requires no extra tuning parameters other than signal sparsity $s$ and is robust to noise. When the sorted coefficients of the sparse signal exhibit a power law decay, we show that CoPRAM achieves a sample complexity of $O(slogn)$, which is close to the information-theoretic limit. We also consider the case where the signal $mathbf{x}^{\ast }$ 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 Block CoPRAM that further reduces the sample complexity to $O(kslogn)$. For sufficiently large block lengths of $b=Theta(s)$, this bound equates to $O(slogn)$. To our knowledge, this constitutes the first end-to-end algorithm for phase retrieval where the Gaussian sample complexity has a sub-quadratic dependence on the signal sparsity level.

Cited in

(7)

• Sparse signal recovery from phaseless measurements via hard thresholding pursuit
• A Generative Variational Model for Inverse Problems in Imaging
• On the Trade-Off Between Bit Depth and Number of Samples for a Basic Approach to Structured Signal Recovery From <inline-formula> <tex-math notation="LaTeX">$b$ </tex-math> </inline-formula>-Bit Quantized Linear Measurements
• The sampling complexity on nonconvex sparse phase retrieval problem
• Compressive phase retrieval: Optimal sample complexity with deep generative priors
• Provable sample-efficient sparse phase retrieval initialized by truncated power method
• Optimal sparse phase retrieval via a quasi-Bayesian approach

This page was built for publication: Sample-Efficient Algorithms for Recovering Structured Signals From Magnitude-Only Measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224084)