Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

DOI10.1109/TSP.2017.2656844zbMATH Open1414.94273arXiv1311.2745MaRDI QIDQ4620767FDOQ4620767

Kishore Jaganathan, B. Hassibi, Samet Oymak

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: The problem of signal recovery from its Fourier transform magnitude is of paramount importance in various fields of engineering and has been around for over 100 years. Due to the absence of phase information, some form of additional information is required in order to be able to uniquely identify the signal of interest. In this work, we focus our attention on discrete-time sparse signals (of length $n$). We first show that, if the DFT dimension is greater than or equal to $2n$, almost all signals with {em aperiodic} support can be uniquely identified by their Fourier transform magnitude (up to time-shift, conjugate-flip and global phase). Then, we develop an efficient Two-stage Sparse Phase Retrieval algorithm (TSPR), which involves: (i) identifying the support, i.e., the locations of the non-zero components, of the signal using a combinatorial algorithm (ii) identifying the signal values in the support using a convex algorithm. We show that TSPR can {em provably} recover most $O(n^{1/2-eps})$-sparse signals (up to a time-shift, conjugate-flip and global phase). We also show that, for most $O(n^{1/4-eps})$-sparse signals, the recovery is {em robust} in the presence of measurement noise. Numerical experiments complement our theoretical analysis and verify the effectiveness of TSPR.

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

Mathematics Subject Classification ID

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

Cited In (25)

• Polarimetric Fourier phase retrieval
• Total Variation--Based Phase Retrieval for Poisson Noise Removal
• The numerics of phase retrieval
• Smoothing composite proximal gradient algorithm for sparse group Lasso problems with nonsmooth loss functions
• Recovery under side constraints
• Inertial proximal ADMM for separable multi-block convex optimizations and compressive affine phase retrieval
• One-dimensional phase retrieval: regularization, box relaxation and uniqueness
• Fundamental limits of weak recovery with applications to phase retrieval
• Constructing confidence intervals for the signals in sparse phase retrieval
• Uniqueness of STFT Phase Retrieval for Bandlimited Vector Functions
• Sparse phase retrieval via ℓp (0 < p ≤ 1) minimization
• Title not available (Why is that?)
• Phase retrieval for sparse binary signal: uniqueness and algorithm
• A Single-Phase, Proximal Path-Following Framework
• Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limit
• Signal Reconstruction from Phase-Only Measurements: Uniqueness Condition, Minimal Measurement Number and Beyond
• Sparse multi-reference alignment: phase retrieval, uniform uncertainty principles and the beltway problem
• Absolute uniqueness of phase retrieval with random illumination
• Phase Retrieval: Uniqueness and Stability
• The sampling complexity on nonconvex sparse phase retrieval problem
• Numerical solution of an inverse random source problem for the time fractional diffusion equation via PhaseLift
• No existence of a linear algorithm for the one-dimensional Fourier phase retrieval
• Phase Retrieval Using Feasible Point Pursuit: Algorithms and Cramér–Rao Bound
• Single-shot phase retrieval via gradient-sparse non-convex regularization integrating physical constraints
• Toward a Mathematical Theory of the Crystallographic Phase Retrieval Problem

This page was built for publication: Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

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