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

In the phase retrieval problem one seeks to recover an unknown n dimensional signal vector \mathbf {x} from m measurements of the form y_{i} = |(\mathbf {A} \mathbf {x})_{i}| , where \mathbf {A} denotes the sensing matrix. Many algorithms for this problem are based on approximate message pa...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2022-11, Vol.68 (11), p.7545-7574
Main Authors: Dudeja, Rishabh, Bakhshizadeh, Milad
Format: Article
Language:English
Subjects:
Algorithms
Approximation algorithms
Columns (structural)
Discrete Fourier transforms
Evolution
Extraterrestrial measurements
Fourier matrix
Hadamard-Walsh matrix
Heuristic algorithms
Linearization
Message passing
message passing algorithms
Phase measurement
Phase retrieval
Sampling
Sensors
universality
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the phase retrieval problem one seeks to recover an unknown n dimensional signal vector \mathbf {x} from m measurements of the form y_{i} = |(\mathbf {A} \mathbf {x})_{i}| , where \mathbf {A} denotes the sensing matrix. Many algorithms for this problem are based on approximate message passing. For these algorithms, it is known that if the sensing matrix \mathbf {A} 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 \rightarrow \infty, n/m \rightarrow \kappa ), the dynamics of the algorithm are given by a deterministic recursion known as the state evolution. For a special class of linearized message-passing algorithms, we show that the state evolution is universal: it continues to hold even when \mathbf {A} is generated by randomly sub-sampling columns of the Hadamard-Walsh matrix, if the signal is drawn from a Gaussian prior.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2022.3182018