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

Published

September 28, 2017

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

Pub Weblink

http://arxiv.org/

Pub Type

Websites

Download Paper

DOI Link

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 December 6, 2024)