CaltechAUTHORS
  A Caltech Library Service

Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms

Jaganathan, Kishore and Oymak, Samet and Hassibi, Babak (2017) Sparse Phase Retrieval: Uniqueness Guarantees and Recovery Algorithms. IEEE Transactions on Signal Processing, 65 (9). pp. 2402-2410. ISSN 1053-587X. http://resolver.caltech.edu/CaltechAUTHORS:20150121-073440098

[img] PDF - Submitted Version
See Usage Policy.

562Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150121-073440098

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, then almost all signals with 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 provably recover most O(n^(1/2-ϵ)-sparse signals (up to a timeshift, conjugate-flip and global phase). We also show that, for most O(n^(1/4-ϵ)-sparse signals, the recovery is robust in the presence of measurement noise. These recovery guarantees are asymptotic in nature. Numerical experiments complement our theoretical analysis and verify the effectiveness of TSPR.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/TSP.2017.2656844DOIArticle
http://ieeexplore.ieee.org/document/7829400/PublisherArticle
http://arxiv.org/abs/1311.2745arXivDiscussion Paper
Additional Information:© 2016 IEEE. This work was supported in part by the National Science Foundation under grants CCF-0729203, CNS-0932428 and CIF-1018927, by the Office of Naval Research under the MURI grant N00014-08-1-0747, and by a grant from Qualcomm Inc.
Funders:
Funding AgencyGrant Number
NSFCCF-0729203
NSFCNS-0932428
NSFCIF-1018927
Office of Naval Research (ONR)N00014-08-1-0747
Qualcomm Inc.UNSPECIFIED
Record Number:CaltechAUTHORS:20150121-073440098
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150121-073440098
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53912
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:23 Jan 2015 00:44
Last Modified:23 Mar 2017 16:18

Repository Staff Only: item control page