Fundamental Limits of Weak Recovery with Applications to Phase Retrieval

1 Introduction

• The general model has an information-theoretic lower threshold δℓ and a spectral upper threshold δu, with weak recovery impossible below δℓ and achievable above δu.The two thresholds depend on the conditional measurement distribution and need not coincide in general.Source: §1 · pp. 2–3
• For phase retrieval with vanishing noise, the lower and upper thresholds coincide, and the optimal spectral method achieves weak recovery for δ > δu = 1.Near δ = 1, the admissible noise level scales as δ −1.Source: §1 · pp. 2–3
• For phase retrieval, no algorithm achieves non-trivial estimates when the complex measurement ratio δ is below 1, while a spectral algorithm succeeds for δ > 1 under sufficiently small noise.The theorem assumes Gaussian sensing vectors and high-dimensional limits; the upper-bound guarantee also extends beyond uniformly random signals.Source: §1 · pp. 2–3
• In the real setting, the weak-recovery threshold is 1/2 rather than 1, consistent with the real signal having half as many variables as the complex formulation.The paper relates this halving to the corresponding injectivity thresholds, δ = 4 and δ = 2.Source: §1 · p. 3
• The paper generalizes [LL17] by analyzing complex measurements and signed preprocessing, using free probability to characterize the principal eigenvalue of a non-PSD random matrix.This yields a preprocessing function that minimizes the weak-recovery threshold for spectral methods.Source: §1 · p. 3, §1.1 · p. 6
• On coded diffraction patterns, the proposed method recovers a digital photograph at δ = 4, whereas truncated spectral initialization from requires δ = 12 for similar results.The analysis is derived for Gaussian matrices, but the experiment uses realistic Fourier-based measurement matrices.Source: Figure 1 · p. 4, §1 · p. 5
• The optimal spectral initializer can serve as the first stage of a two-round pipeline followed by AMP or Wirtinger Flow, reducing the measurements needed for initialization.Using another truncation leaves performance limited by that truncation’s weak-recovery threshold.Source: §1 · pp. 2, 5

1.1 Related Work

• Earlier phase-retrieval spectral guarantees progressed from d log^3 d to d log d and then d samples, while concentration-based proofs generally lacked exact thresholds.The paper’s signed preprocessing also addresses a gap of non-negative spectral methods, which incur an unavoidable gap from the ideal threshold.Source: §1.1 · pp. 5–6

2.1 Notation and System Model

• The model uses a uniformly random complex-sphere signal, i.i.d. circularly symmetric complex Gaussian sensing vectors, and independent measurements generated conditionally on inner products.The asymptotic regime takes n,d to infinity with n/d approaching a fixed positive δ; phase retrieval adds squared-magnitude measurements with Gaussian noise.Source: §2.1 · pp. 6–7

2.2 Information-Theoretic Lower Bound

• The information-theoretic threshold is defined through a function whose maximum remains at zero overlap, reflecting indistinguishability from the trivial estimator.The conditional entropy and associated error metrics support this characterization of the lower bound.Source: §2.2 · pp. 7–8
• Below δℓ, even the optimal estimator performs like a measurement-free trivial estimator, establishing impossibility of weak recovery.For the general complex model, this result assumes the function ϕ is bounded; the boundedness requirement can be relaxed for sufficiently light-tailed measurements.Source: §2.2 · pp. 7–8

2.3 Upper Bound via Spectral Method

• The spectral construction forms a matrix from the measurements using a preprocessing function T and returns its principal eigenvector.The general optimal preprocessing function is specified through conditional measurement likelihoods and Gaussian averaging.Source: §2.3 · pp. 8–9
• Above δu, the principal eigenvector of a data-constructed matrix achieves weak recovery using a suitable preprocessing function T.The optimal preprocessing function achieves the smallest weak-recovery threshold among spectral methods of the specified matrix form, and no such function succeeds at δ≤δu.Source: §2.3 · p. 9
• For phase retrieval, the information-theoretic and spectral thresholds coincide at δℓ=δu=1, while vanishing-noise recovery remains positively correlated above the threshold.The spectral threshold satisfies δu(σ2)=1+σ2+o(σ2) as σ2 approaches zero.Source: §2.3 · p. 9
• For phase retrieval, the preprocessing function in the vanishing-noise result does not require estimating the noise variance while maintaining correlation bounded away from zero.This is stronger than merely showing convergence of the spectral threshold to one.Source: §2.3 · p. 9

Threshold definitions

• The information-theoretic threshold δℓ is defined as the largest sampling ratio for which the objective remains maximized at zero correlation.The associated lower bound compares optimal prediction with the estimator that has no measurements.Source: §3 · p. 10

Information-theoretic lower bound

• For real phase retrieval, the information-theoretic lower bound holds for any δ < 1/2, so measurements below this threshold cannot achieve informative recovery.The proof specializes the general lower bound to squared inner products with additive Gaussian noise.Source: §3 · p. 11

Spectral upper bound

• For δ > δu, the principal eigenvector of Dn with preprocessing T* provides an estimate positively correlated with the signal.No preprocessing function achieves the stated correlation guarantee when δ ≤ δu.Source: §3 · pp. 11–12

Real phase retrieval

• For real phase retrieval, the spectral upper bound matches the information-theoretic lower bound; for any δ > 1/2, the preprocessing function T is set to T∗.Source: §3 · p. 12

General sensing models

• In general sensing models, δℓ and δu can differ strictly: δu may be infinite while δℓ remains finite for nonconstant measurement channels.The example uses a bounded even function, while the lower-threshold argument applies broadly to channels not constant in G on a set of positive measure.Source: §3 · pp. 12–13

4.1 Complex Case

• For any δ < δℓ, Theorem 1 establishes the complex general-sensing information-theoretic lower bound.The entropy calculation underlying the result also gives an expression for mutual information below δℓ.Source: §4.1 · pp. 13, 16
• The lower bound does not require assumptions on the signal distribution or sensing-vector distribution for the entropy step beyond independence of the sensing vectors.This distributional robustness applies specifically to the proof of the conditional-entropy relation.Source: §4.1 · p. 13
• The complex proof’s threshold gap is not merely an artifact of a loose lower bound: prior results imply that the actual information-theoretic threshold is finite.The cited result [BKM+17] is used to support this qualification.Source: §4.1 · p. 13
• The complex-case proof first shows that the next observation is asymptotically independent of previous observations and sensing vectors in conditional entropy.Specifically, H(Yn+1 | Y1:n, A1:n+1) = H(Yn+1) + o_n(1).Source: §4.1 · p. 17
• The proof then converts vanishing conditional mutual information into equality between the measurement-based estimator and the no-measurement estimator for bounded test functions.The argument uses Kullback–Leibler divergence, Pinsker’s inequality, boundedness of ϕ, and total variation distance.Source: §4.1 · pp. 17–18

4.2 Real Case

• The same lower-bound strategy extends to the real general-sensing model, with Theorem 3 relying on analogous entropy and conditional-estimation arguments.The real proof repeats the complex structure while modifying the Gaussian overlap calculations.Source: §4.2 · pp. 18–19

Spectral regimes

• The generalized spectral lemma shows that weak recovery occurs exactly in the regime where the leading eigenvector has nonzero asymptotic correlation and the top two eigenvalues have a strictly positive gap.In the complementary regime, the correlation converges to zero and no positive eigenvalue gap exists, so the spectral method fails.Source: §5 · p. 21

Lemma generalization

• The proof extends [LL17] from real to complex vectors and from nonnegative weights to weights that may be negative, with the latter requiring a separate non-PSD random-matrix lemma.The complex extension follows by replacing Gaussian variables, transposes, and squares with their circularly symmetric complex, conjugate-transpose, and modulus-square analogues.Source: §5 · p. 21

Random-matrix characterization

• The matrix analysis reduces the principal eigenvalue problem to a rank-one perturbation characterized by monotone, convex functions and a unique fixed point, while spectral measures converge to the law of Z.Interlacing and the non-PSD extension handle dependence between the perturbation components and establish the limiting eigenvalue characterization.Source: §5 · pp. 23–24

Proof of Theorem 2

• The theorem proof uses scale invariance of the principal eigenvector to normalize the minimizer of ψδ, then selects the preprocessing function T*(y) to satisfy the lemma’s recovery inequalities.The proof verifies that T* is nonzero with positive probability and constructs the required support behavior for condition (82), including a point-mass regularization argument.Source: §5 · pp. 25–26
• A strictly positive eigenvalue gap for the regularized matrix enables control of the original principal eigenvector through the Davis–Kahan theorem [DK70].This transfers the spectral guarantee from the perturbed preprocessing function back to the target estimator.Source: §5 · p. 27

Complex case

• For any n, as ϵ1 tends to 0, the principal eigenvector of Dn(ϵ1) converges to that of Dn, allowing T = T*.This establishes the approximation step used to verify the spectral method’s upper-bound condition.Source: §5 · p. 27

Optimality of the threshold

• The threshold δu is optimal: for δ ≤ δu, no pre-processing function achieves weak recovery almost surely.The proof reduces the spectral condition to equivalent constraints, combines the resulting inequalities, and concludes that any successful method would require δ > δu.Source: §5 · pp. 27–28

Real case

• For the real case, Remark 7 states that the proof first establishes a result analogous to Lemma 2.Source: §5 · p. 28

6.2 Results

• Below δu, message passing converges to an un-informative fixed point even when initialized with positive correlation.Source: §6.1 · p. 28, §6.2 · pp. 30–31
• Above δu, linearized message passing becomes unstable at the un-informative fixed point and can escape it.Source: §6.1 · p. 29, §6.2 · p. 31

6.1 Motivation and Background

• The message passing comparison suggests that δu may be the fundamental limit for polynomial-time algorithms, although this remains a conjecture.Source: §6.1 · p. 29
• Message passing can further refine spectral estimates toward exact recovery, motivating combined threshold analyses as future work.Source: §6.1 · p. 29
• The analysis assumes real signals and sensing matrices in this section, with bounded twice-differentiable conditional densities.Source: §6.1 · p. 29
• The AMP analysis uses state evolution, which tracks iterates as noisy versions of the signal and governs empirical averages asymptotically.Source: §6.1 · p. 30

7.1 Gaussian Sensing Vectors for Synthetic Data

• In complex Gaussian sensing, weak recovery is possible for δ values very close to 1 with the proposed preprocessing.Source: §7.1 · p. 32
• Enforcing non-negativity on the preprocessing function degrades spectral-method performance.Source: §7.1 · p. 32
• The proposed preprocessing yields a remarkable performance gain over both the subset and trimming algorithms in synthetic experiments.The trimming algorithm is associated with and [LL17], while the subset algorithm is associated with [WGE16] and [LL17].Source: §7.1 · p. 32, Figure 2 · p. 34
• In real Gaussian sensing, weak recovery is possible for δ values very close to 1/2, and simulations closely follow theoretical predictions.Source: §7.1 · p. 32

7.2 Coded Diffraction Model for Natural Images

• The coded diffraction experiment averages squared normalized scalar products across the three RGB components of a digital photograph.Source: §7.2 · p. 33, Figure 3 · p. 35
• For coded diffraction measurements, weak recovery begins at δ ≥3 with the proposed method versus δ ≥6 for truncated spectral initialization.For every tested δ, the proposed preprocessing has better performance than.Source: §7.2 · p. 35, Figure 3 · p. 35

• The proof begins by deriving a less compact explicit form of expression (10), then uses it to compute the phase-retrieval lower threshold δℓ.Source: A Proof of Corollary 1 · pp. 35–37
• For the complex phase-retrieval model, Gaussian changes of variables and polar-coordinate calculations simplify the expectations defining the auxiliary function.Source: A Proof of Corollary 1 · pp. 36–37
• The calculation uses dominated convergence as the noise variance tends to zero to obtain the limiting expressions.Source: A Proof of Corollary 1 · pp. 37–38
• The final corollary proof applies the same initial information-theoretic step as Theorem 1 but modifies the second step for the different error metric.Source: A Proof of Corollary 1 · p. 38
• The modified argument bounds the error through matrix identities involving E{XX*}=I_d and Frobenius norms, completing the proof.Source: A Proof of Corollary 1 · pp. 38–40

• The proof evaluates the threshold asymptotically by computing expectations and integrals and using dominated convergence.Source: B Proof of Corollary 2 · pp. 40, 41, 43
• The preprocessing function is chosen to remain bounded, avoid excessive mass at zero, and satisfy the threshold condition.Source: B Proof of Corollary 2 · p. 41
• The proof normalizes the matrix scaling without changing its principal eigenvector and selects a function involving y+ = max(y, 0).Source: B Proof of Corollary 2 · p. 42
• For every δ > 1, the constructed spectral estimator satisfies the corollary for sufficiently small noise variance.Source: B Proof of Corollary 2 · p. 43
• Davis–Kahan perturbation bounds transfer the result from the ideal preprocessing function to the final estimator.Source: B Proof of Corollary 2 · p. 43

Scalar-product distributions

• For two independent unit complex vectors, the squared modulus of their scalar product follows a Beta(1/2, (d −1)/2) distribution.The argument decomposes independent Gamma variables associated with the first coordinate and the remaining coordinates.Source: C Auxiliary Lemmas · pp. 44–45
• For two independent unit real vectors, the scalar product is represented through Gamma variables, yielding a Beta distribution for its squared value.The proof fixes one vector to a canonical basis vector and normalizes independent Gaussian coordinates.Source: C Auxiliary Lemmas · p. 44
• The complex scalar-product distribution is obtained by a change of variables together with symmetry around zero and an explicit normalization constant.The supplied derivation states the change-of-variable and symmetry steps but does not include the resulting density formula.Source: C Auxiliary Lemmas · p. 44

Laplace’s method

• Laplace’s method bounds integrals of exp(n · F(x)) by separating a neighborhood of zero from the remainder when F(0)=0 and F(x)<0 elsewhere.The first part is controlled by an arbitrary epsilon, while the second vanishes as n tends to infinity.Source: C Auxiliary Lemmas · p. 45

Uniform complex-sphere moments

• A uniform complex-sphere vector can be generated by normalizing an i.i.d. complex Gaussian vector, enabling coordinate-moment calculations.The coordinate squared modulus is identified with a Beta(1, d −1) variable.Source: C Auxiliary Lemmas · p. 45

Limiting spectral distributions

• The empirical spectral distribution converges weakly to Fδ,H, whose support is linked to the generating measure H through the function ψFδ,H.Outside the limiting support, the inverse Stieltjes transform satisfies the stated conditions involving α and ψFδ,H.Source: D Proof of Lemma 3 · pp. 45–46

Real-case extension

• The proof extends the result to real Gaussian matrices, while requiring convergence of the empirical spectral distribution and bounded spectral norms.The real-case decomposition follows the same argument as the complex case.Source: D Proof of Lemma 3 · pp. 46, 49

Outlier criterion

• For positive-semidefinite weights, the largest eigenvalue is outside the limiting support exactly when ψ′Fδ,H(α∗)>0.The relevant outlier location is mapped through ψFδ,H(α∗), with α∗ defined from the Stieltjes transform.Source: D Proof of Lemma 3 · p. 46

Indefinite weights

• For indefinite weights, the matrix is decomposed into positive and negative parts, whose limiting spectra are combined through free additive convolution.Rotational invariance and Haar-unitary symmetry provide the decomposition used to analyze the two parts independently.Source: D Proof of Lemma 3 · pp. 46–47

Outlier criterion

• The largest eigenvalue of the indefinite model lies outside the limiting support under the same derivative condition ψ′Fδ,H(α∗)>0.Subordination transfers the positive-part spike to the free-convolution spectrum, where the support criterion is applied.Source: D Proof of Lemma 3 · p. 48

AMP state evolution

• A general AMP iteration is rewritten using two-component state variables and component-wise functions so that existing state-evolution results apply.The construction introduces ht and ˆht together with matrices Bt and ˆBt, then invokes Proposition 5 of [JM13].Source: E Proof of Lemma 4 and Theorem 5 · pp. 49–50
• The state-evolution theorem gives almost-sure limits for admissible functions of the AMP iterates under the stated initialization and moment-growth condition.The result applies for any ψ satisfying the displayed growth-Lipschitz bound.Source: E Proof of Lemma 4 and Theorem 5 · p. 49
• State evolution tracks the AMP iterates through a recursion involving the overlap q and variance parameter μ.The proof establishes the recursion inductively using Gaussian representations, conditional expectations, and Stein’s lemma.Source: E Proof of Lemma 4 and Theorem 5 · pp. 49–51

Fixed-point stability

• The point (q, μ)=(0,0) is a fixed point of the state-evolution recursion when condition (131) holds.The proof first verifies the fixed-point equations before analyzing local stability.Source: E Proof of Lemma 4 and Theorem 5 · p. 52
• For δ<δu, the uninformative fixed point is stable after linearizing the recursion near zero and controlling the resulting terms by Stein’s lemma and dominated convergence.The proof derives local expansions for numerator and denominator functions before concluding stability.Source: E Proof of Lemma 4 and Theorem 5 · pp. 52–53

Linearized operator

• The proof introduces the preprocessing function and diagonal matrix used to formulate the linearized operator Ln.The diagonal entries are defined from the derivative F′(0, yi; 1).Source: F Proof of Lemma 5 and Theorem 6 · pp. 53–54
• All eigenvalues of Ln are real because its characteristic equation reduces to generalized eigenvalues of symmetric matrix pairs.An SVD of A transforms the eigenvalue condition into a determinant involving AAT−In and J−1.Source: F Proof of Lemma 5 and Theorem 6 · pp. 54–55

Threshold analysis

• Theorem 6 analyzes the largest eigenvalue through the limiting spectral function ψδ and its unique minimizer, using convexity and analyticity.The point of minimum λ̄δ is the unique local minimizer because ψδ is convex and analytic.Source: F Proof of Lemma 5 and Theorem 6 · pp. 55–57
• The proof verifies that T∗δ satisfies the hypotheses needed for the spectral analysis, including boundedness and support conditions.The argument treats the cases where T∗δ is constant, has an atom at its support supremum, or is approximated by a point-mass construction.Source: F Proof of Lemma 5 and Theorem 6 · p. 57
• The largest eigenvalue of the approximating matrix converges to that of the target matrix as the approximation parameter tends to zero.Weyl’s inequality controls the perturbation and completes the limiting argument.Source: F Proof of Lemma 5 and Theorem 6 · p. 57