Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Phase Retrieval Without Small-Ball Probability Assumptions: Recovery Guarantees for PhaseLift

Published

Author(s)

Yi-Kai Liu, Felix Krahmer

Abstract

We study the problem of recovering an unknown vector x in R^n from measurements of the form y_i = |a_i^T x|^2 (for i=1,...,m), where the vectors a_i in R^n are chosen independently at random, with each coordinate a_{ij} being chosen independently from a fixed sub-Gaussian distribution D. However, without making additional assumptions on the random variables a_{ij} --- for example on the behavior of their small ball probabilities --- it may happen some vectors x cannot be uniquely recovered. We show that for any sub-Gaussian distribution D, with no additional assumptions, it is still possible to recover most vectors x. More precisely, one can recover those vectors x that are "not too peaky" in the sense that at most a constant fraction of their mass is concentrated on any one coordinate. The recovery guarantees in this paper are for the PhaseLift algorithm, a tractable convex program based on a matrix formulation of the problem. We prove uniform recovery of all "not too peaky" vectors from m = O(n) measurements, in the presence of noise. This extends previous work on PhaseLift by Candes and Li.
Citation
Arxiv preprint server
Volume
64
Issue
1

Keywords

Phase retrieval, low-rank matrix recovery, convex relaxation, crystallography, optical imaging

Citation

Liu, Y. and Krahmer, F. (2017), Phase Retrieval Without Small-Ball Probability Assumptions: Recovery Guarantees for PhaseLift, Arxiv preprint server, [online], https://doi.org/10.1109/TIT.2017.2757520, http://arxiv.org/ (Accessed May 19, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created September 28, 2017, Updated November 10, 2018