Information Theoretic Limits for Phase Retrieval With Subsampled Haar Sensing Matrices

Rishabh Dudeja, Junjie Ma, Arian Maleki

TL;DR

This paper proves that for phase retrieval using subsampled Haar sensing matrices, it is information-theoretically impossible to recover any part of the signal if the number of measurements $m$ is less than twice the signal dimension $n$ (i.e., $m/n < 2$). This establishes a sharp "weak recovery threshold" at $\delta = 2$, showing that the structural requirement of column orthogonality in sensing matrices—common in practical imaging—actually makes the recovery problem harder than in the standard Gaussian case.

What Problem Does This Paper Address?

Phase retrieval is the challenge of recovering a complex-valued signal vector $\mathbf{x_\star}$ from the magnitudes of its linear measurements: $y_i = |(\mathbf{Ax_\star})_i|^2$. This is a classic problem in physical sciences like X-ray crystallography and astronomy, where sensors can record the intensity of light but not its phase.

While much of the existing theory assumes the sensing matrix $\mathbf{A}$ has independent and identically distributed (i.i.d.) Gaussian entries, real-world imaging systems often use structured matrices, such as Coded Diffraction Patterns (CDPs). These practical matrices typically have orthogonal columns. To bridge the gap between theory and practice, the authors model the sensing matrix as a subsampled Haar matrix (formed by picking $n$ columns of a random $m \times m$ unitary matrix).

The core question is: What is the minimum oversampling ratio $\delta = m/n$ required to achieve any non-trivial correlation with the original signal?

Methods

The authors employ a rigorous high-dimensional asymptotic analysis ($m, n \to \infty$ with $m/n \to \delta$). Their proof strategy involves several sophisticated mathematical steps:

  1. Mutual Information and Bayes Risk: They relate the ability to recover the signal (Bayes risk) to the Mutual Information between the measurements and the signal. If Mutual Information grows slower than the signal dimension, recovery is impossible.
  2. $\chi^2$-Divergence Upper Bound: They bound the Mutual Information using $\chi^2$-divergence, which requires evaluating complex high-dimensional integrals.
  3. Large Deviation Techniques: Unlike Gaussian matrices, Haar matrices have dependent entries. To handle this, the authors use Large Deviation theory and a "Stochastic Laplace Method" to analyze how these integrals concentrate around deterministic values.
  4. Tilted Distributions: They introduce "Tilted Exponential" and "Tilted Wishart" distributions to apply local Central Limit Theorems (CLTs) to the dependent structures inherent in unitary matrices.

Datasets

This is a theoretical paper focused on mathematical proofs; therefore, no empirical datasets were used for training or evaluation. The "data" consists of synthetic measurements generated via the subsampled Haar model described in the text.

Key Insights and Ideas

  • The "Harder" Threshold: For standard Gaussian sensing matrices, the weak recovery threshold is $\delta = 1$. This paper proves that for subsampled Haar matrices, the threshold is $\delta = 2$. This confirms empirical observations that structured, orthogonal sensing matrices require more data than i.i.d. matrices for successful phase retrieval.
  • Asymptotic Orthogonality: The paper shows that below the threshold ($\delta < 2$), any estimator—no matter how computationally powerful—will produce a result that is asymptotically orthogonal to the true signal. In other words, the estimate will be completely uncorrelated with the truth.
  • Sharpness: This lower bound is "sharp" because previous research has already demonstrated that specific algorithms (like spectral methods) can achieve non-trivial recovery as soon as $\delta > 2$.
  • Least Favorable Prior: The authors assume a uniform prior on the signal (the signal is a random unit vector). They argue this is the "least favorable" case; if you can't recover a signal with this prior, you likely can't recover an arbitrary signal without additional structure (like sparsity).

Key Results

  • Theorem 1: For any oversampling ratio $\delta < 2$ and any noise level $\sigma > 0$, the Bayes risk converges to 1. This means the best possible estimate is no better than a random guess or a zero vector.
  • Information-Theoretic Impossibility: The result is not about a specific algorithm failing, but about the information simply not being present in the measurements to distinguish the signal from noise when $\delta < 2$.
  • Validation of Spectral Methods: The result provides a theoretical explanation for why spectral estimators for CDP matrices have been observed to fail specifically when $\delta < 2$.

Limitations and Future Work

  • Beyond the Threshold: The current proof techniques provide an "all-or-nothing" result below the threshold but do not characterize the exact Bayes risk or the minimum mean square error (MMSE) when $\delta > 2$.
  • General Unitarily Invariant Ensembles: The authors suggest that their techniques could be generalized to other types of unitarily invariant matrices (where $A = U\Lambda V^H$), which would cover an even broader range of practical sensing hardware.
  • Signal Structure: The study assumes a generic unit-norm signal. Future work could investigate how signal structures, such as sparsity or generative model priors, lower the $\delta = 2$ threshold.

Summary updated

Abstract

We study information theoretic limits of recovering an unknown n dimensional, complex signal vector x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sub> with unit norm from m magnitude-only measurements of the form y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> = |(Ax <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sub> ) <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> | <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> , 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 X 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 - o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> (1)) · n, then any estimator is asymptotically orthogonal to the true signal vector x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">*</sub> . This lower bound is sharp since when m > (2 + o <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> (1)) · n, estimators that achieve a non trivial asymptotic correlation with the signal vector are known from previous works.
BibTeX
@article{dudeja2020information,
  author = {Rishabh Dudeja and Junjie Ma and Arian Maleki},
  title = {{Information Theoretic Limits for Phase Retrieval With Subsampled Haar Sensing Matrices}},
  journal = {IEEE Trans. Information Theory},
  year = {2020},
  doi = {10.1109/tit.2020.3015173},
}

Loading related content...

Figure