Universality of Linearized Message Passing for Phase Retrieval with Structured Sensing Matrices

08/24/2020
∙
by   Rishabh Dudeja, et al.
∙
0
∙

In the phase retrieval problem one seeks to recover an unknown n dimensional signal vector đ± from m measurements of the form y_i = |(đ€đ±)_i| where 𝐀 denotes the sensing matrix. A popular class of algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix 𝐀 is generated by sub-sampling n columns of a uniformly random (i.e. Haar distributed) orthogonal matrix, in the high dimensional asymptotic regime (m,n →∞, n/m →Îș), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For the special class of linearized message passing algorithms, we show that the state evolution is universal: it continues to hold even when 𝐀 is generated by randomly sub-sampling columns of certain deterministic orthogonal matrices such as the Hadamard-Walsh matrix, provided the signal is drawn from a Gaussian prior.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset