2019/10/25 by Dudeja, Rishabh, Ma, Junjie, Maleki, Arian
#FOS: Mathematics #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1910.11849
We study information theoretic limits of recovering an unknown n dimensional, complex signal vector x_⋆ with unit norm from m magnitude-only measurements of the form yi = |(A x_⋆)i|2, i = 1,2 … , m, where A is the sensing matrix. This is known as the Phase Retrieval problem and models practical imaging systems where measuring the phase of the observations is difficult. Since in a number of applications, the sensing matrix has orthogonal columns, we model the sensing matrix as a subsampled Haar matrix formed by picking n columns of a uniformly random m × m unitary matrix. We study this problem in the high dimensional asymptotic regime, where m,n → ∞, while m/n → δ with δ being a fixed number, and show that if m < (2-on(1))⋅ n, then any estimator is asymptotically orthogonal to the true signal vector x_⋆. This lower bound is sharp since when m > (2+on(1)) ⋅ n , estimators that achieve a non trivial asymptotic correlation with the signal vector are known from previous works.