Abstract
We study the information-theoretic limits of recovering an unknown $n$-dimensional complex signal vector $\mathbf{x}_*$ with unit norm from $m$ magnitude-only measurements of the form $y_i = |(\mathbf{Ax}_*)_i|^2$, where $\mathbf{A}$ is the sensing matrix. This "Phase Retrieval" problem models practical imaging systems where measuring the phase of observations is physically difficult. In many applications, sensing matrices possess orthogonal columns; thus, we model $\mathbf{A}$ as a subsampled Haar matrix formed by picking $n$ columns of a uniformly random $m \times m$ unitary matrix. We analyze this problem in the high-dimensional asymptotic regime ($m, n \to \infty$, $m/n \to \delta$) and demonstrate that if $m < (2 - o_n(1)) \cdot n$, any estimator is asymptotically orthogonal to the true signal vector $\mathbf{x}_*$. This lower bound is sharp, as estimators achieving non-trivial correlation are known to exist when $m > (2 + o_n(1)) \cdot n$.
Introduction
Phase retrieval is a cornerstone challenge in the physical sciences, particularly in fields like X-ray crystallography, diffraction imaging, and astronomy. In these contexts, sensors typically record the intensity (magnitude) of light or electromagnetic waves but fail to capture the phase information. Mathematically, the goal is to reconstruct a complex-valued signal $\mathbf{x}_* \in \mathbb{C}^n$ from measurements $y_i = |(\mathbf{Ax}_*)_i|^2$.
While theoretical analysis often assumes the sensing matrix $\mathbf{A}$ consists of independent and identically distributed (i.i.d.) Gaussian entries, real-world systems frequently utilize structured matrices. For instance, Coded Diffraction Patterns (CDPs) often involve matrices with orthogonal columns. This paper bridges the gap between idealized Gaussian theory and practical application by investigating the subsampled Haar sensing matrix model.
The Recovery Threshold: $\delta = 2$
The central question in this research is determining the minimum oversampling ratio $\delta = m/n$ required to achieve "weak recovery"—defined as obtaining an estimate that has a non-trivial (non-zero) correlation with the original signal in the high-dimensional limit.
The "Harder" Threshold
One of the most significant findings is that the structural requirement of column orthogonality actually makes the phase retrieval problem harder. For standard i.i.d. Gaussian sensing matrices, the weak recovery threshold is known to be $\delta = 1$. However, this work proves that for subsampled Haar matrices, the threshold shifts to $\delta = 2$.
Below this threshold (when $\delta < 2$), the paper proves a state of asymptotic orthogonality. This means that regardless of the computational power or the specific algorithm used, any estimator will produce a result that is completely uncorrelated with the true signal $\mathbf{x}_*$. The information necessary to distinguish the signal from noise is simply not present in the measurements.
Methodological Framework
To establish this impossibility result, the authors employ a rigorous high-dimensional asymptotic analysis. The proof strategy relies on several sophisticated mathematical pillars:
- Mutual Information and Bayes Risk: The authors relate the ability to recover the signal (the minimum mean square error or Bayes risk) to the Mutual Information between the measurements and the signal. If the Mutual Information grows slower than the signal dimension, recovery is impossible.
- $\chi^2$-Divergence Upper Bound: They bound the Mutual Information using $\chi^2$-divergence. This requires evaluating complex high-dimensional integrals over the space of unitary matrices.
- Large Deviation Theory: Because Haar matrices have dependent entries (unlike Gaussian matrices), the authors utilize Large Deviation techniques and a "Stochastic Laplace Method" to determine how these integrals concentrate around deterministic values as $n$ grows.
- Tilted Distributions: To handle the inherent dependencies in unitary structures, the authors introduce "Tilted Exponential" and "Tilted Wishart" distributions, allowing for the application of local Central Limit Theorems (CLTs) to the problem.
Significance and Sharpness
This result is considered "sharp" because it completes the theoretical picture for Haar sensing. Previous research into spectral methods had already shown that specific algorithms could achieve non-trivial recovery once $\delta > 2$. By proving that recovery is impossible for $\delta < 2$, this paper establishes $\delta = 2$ as the definitive information-theoretic phase transition for this class of matrices.
Furthermore, the study assumes a uniform prior on the signal (a random unit vector). This represents the "least favorable" case; if recovery is impossible under these conditions, it suggests that without additional signal structure (such as sparsity), the $\delta = 2$ limit is an absolute barrier for generic signals in orthogonal sensing systems.
Conclusion and Future Directions
This work provides a theoretical foundation for understanding why certain practical imaging setups require more measurements than Gaussian models would suggest. While it establishes the "all-or-nothing" threshold for $\delta < 2$, future work remains to be done in characterizing the exact Bayes risk or Minimum Mean Square Error (MMSE) when $\delta > 2$. Additionally, the techniques developed here could potentially be extended to other unitarily invariant ensembles, further narrowing the gap between theoretical signal processing and the realities of optical physics.
Summary updated