Phase Transitions of Spectral Initialization for High-Dimensional Nonconvex Estimation

I. INTRODUCTION

• The method constructs a data matrix from measurements and sensing vectors, then estimates ξ using its normalized leading eigenvector; preprocessing can include trimming or truncation.The algorithm does not require knowledge of the exact acquisition process.Source: §I · p. 1
• The analysis extends prior phase-retrieval bounds to arbitrary conditional acquisition models and gives explicit limits for squared cosine similarity ρ when m/n converges to α.For Gaussian measurements, the limit ρ(α) is deterministic and explicit.Source: §I · p. 2
• Below αc,min, ρ(α)=0 and the estimate is asymptotically uncorrelated with ξ, performing no better than a uniformly random hypersphere guess.A random unit-vector estimate typically has correlation of order O(1/√n) with ξ.Source: §I · p. 2
• Above αc,max, ρ(α)>0, the estimate concentrates around ξ on a cone, and ρ(α) tends to 1 as α→∞.The cone representation allows the estimate or its negative to reflect the unknown sign.Source: §I · p. 2
• The thresholds may coincide or leave an interval with alternating correlated and uncorrelated behavior, while the spectral gap is nonzero in the correlated phase and vanishes in the uncorrelated phase.A nonzero gap enables efficient power iterations; a vanishing gap makes them inefficient.Source: §I · p. 2

A. Technical Assumptions

• The asymptotic analysis assumes Gaussian sensing, fixed positive sampling ratio, bounded nonnegative preprocessed observations, and positive correlation between z and s^2.The condition can fail for z=sign(s)+C, where the spectral method is ineffective; the normalized eigenvector also cannot recover ||ξ||.Source: A. Technical Assumptions · pp. 3–4

B. Main Results: Asymptotic Characterizations

• Theorem 1 establishes a complete high-dimensional characterization of the spectral method’s performance through a unique solution λ*_α and the leading eigenvalues of D_m.The squared cosine similarity and spectral gap are characterized asymptotically under assumptions (A.1)–(A.6).Source: B. Main Results: Asymptotic… · p. 4
• The limiting squared cosine similarity is zero in the uncorrelated phase and strictly positive in the correlated phase, depending on the sign of ψ′_α.Thus, the spectral estimate may carry no asymptotic information or may align with the target signal.Source: B. Main Results: Asymptotic… · p. 4
• The spectral gap vanishes in the uncorrelated phase but converges to a positive value in the correlated phase.A vanishing gap makes iterative procedures such as power iterations increasingly difficult to converge.Source: B. Main Results: Asymptotic… · p. 4
• The analysis extends prior performance bounds by deriving exact high-dimensional limits for the alignment quantity, while later work extended the predictions to complex-valued signals and signed preprocessing variables [33].The paper positions its result as an exact asymptotic counterpart to earlier bounds.Source: B. Main Results: Asymptotic… · p. 4
• The phase-transition thresholds are determined by the smallest and largest zero-crossings of Δ(λ), yielding αc,min and αc,max.The resulting alignment function ρ(α) is represented parametrically, and ρ(α) approaches 1 as α grows without bound.Source: B. Main Results: Asymptotic… · pp. 4–5
• When Λ has one element, a single threshold separates uncorrelated and correlated phases; multiple elements can instead produce alternating phases between the two thresholds.The paper notes that both scenarios occur among studied acquisition models.Source: B. Main Results: Asymptotic… · p. 5

C. Worked-Example: Binary Models

• Binary observations permit closed-form expressions for the quantities in Theorem 1, including the critical sampling ratio αc and asymptotic top-eigenvalue predictions.The construction covers logistic regression and one-bit quantized sensing.Source: C. Worked-Example: Binary Models · p. 5
• For one-bit models, the asymptotic performance depends only on constants c and d, not on the detailed joint distributions of s, y, and z.Computing c and d therefore determines the spectral method’s asymptotic behavior in this model class.Source: C. Worked-Example: Binary Models · p. 5

D. Numerical Simulations

• In binary logistic regression, analytical squared-cosine predictions match simulations at n = 4096 across 16 independent trials.Below αc the two leading eigenvalues are asymptotically equal; above αc they diverge, producing a growing eigengap.Source: D. Numerical Simulations · p. 5, Figure 2 · p. 6
• For phase retrieval, analytical predictions for trimming and subset algorithms also match simulations at n = 4096, including the comparison of their threshold-dependent behavior.The subset algorithm uses t = 1.5, while the trimming algorithm uses t = 3.Source: D. Numerical Simulations · p. 5, Figure 3 · p. 6
• The critical sampling ratios αc of both phase-retrieval algorithms are evaluated as functions of threshold t at noise levels σ = 0 and σ = 2.These predictions can guide threshold selection and preprocessing-function design; related work obtained a uniformly optimal fixed design under a mild condition.Source: D. Numerical Simulations · p. 6, Figure 3 · p. 6

A. Overview

• The proof handles correlation between the sensing matrix and preprocessing weights by rewriting the data matrix in block-partitioned form and introducing an auxiliary fixed-point formulation.The auxiliary variable decouples the correlation, enabling a random-matrix asymptotic analysis.Source: A. Overview · p. 6

B. A Fixed-Point Characterization

• The block-matrix result applies to arbitrary symmetric P and nonzero q, not only to the specific data matrix used in the spectral method.This gives the deterministic characterization validity for any finite dimension and arbitrary sensing vectors.Source: B. A Fixed-Point Characterization · p. 7
• The leading eigenvalue is represented through a function L(µ), whose monotonicity, convexity, and differentiability properties control the fixed-point analysis.The leading eigenvector’s squared alignment with the target coordinate is also linked to the fixed-point solution through one-sided derivatives of L.Source: B. A Fixed-Point Characterization · p. 7
• The fixed-point equation has exactly one solution because L(µ) is nondecreasing and unbounded while a + 1/µ decreases from infinity to zero.This uniqueness supplies the well-defined auxiliary parameter used in the eigenvalue and eigenvector characterization.Source: B. A Fixed-Point Characterization · pp. 7–8

C. Asymptotic Limit of Lm(µ)

• The finite-dimensional matrix is a rank-one perturbation of a diagonal matrix, so its spectrum can be analyzed through the spectrum of the unperturbed component.The diagonal component has a bulk spectrum, while the perturbation produces a distinguished eigenvalue.Source: C. Asymptotic Limit of Lm(µ) · p. 8
• As m,n →∞, the empirical spectral measure of the bulk matrix converges almost surely to the law of z, with support bounded by τ.The remaining eigenvalues form the bulk spectrum, while the leading eigenvalue is separated as a spike.Source: C. Asymptotic Limit of Lm(µ) · p. 8
• The spike converges to λµ = Q^-1(1/µ) > τ, placing it strictly above the bulk edge.The inverse is well-defined because Q is continuous, strictly decreasing, and spans the required range.Source: C. Asymptotic Limit of Lm(µ) · p. 8
• For i.i.d. Gaussian sensing, Lm(µ) converges almost surely to ζα(λµ), where ζα is the modified deterministic limit function.The limiting expression is obtained by combining the spike location with the asymptotic extreme-eigenvalue characterization.Source: C. Asymptotic Limit of Lm(µ) · p. 8

D. Proof of Theorem 1

• The proof uses rotational invariance of Gaussian sensing vectors to analyze the target ξn = κe1 without loss of generality.The resulting alignment limit for this coordinate-aligned case extends to general target vectors by equality in distribution.Source: D. Proof of Theorem 1 · pp. 8–9
• The fixed-point solution µm converges through monotone-function arguments to the deterministic solution µ*, allowing the finite-dimensional eigenvalue characterization to pass to the high-dimensional limit.The proof uses the almost-sure limit of Lm(µ) together with monotonicity and strict increase.Source: D. Proof of Theorem 1 · p. 9
• The limiting leading eigenvalue is ζα(λ*), with λ* = Q^-1(1/µ*) determined by the unique equation defining the asymptotic fixed point.The proof obtains this by substituting the limits into the deterministic eigenvalue characterization.Source: D. Proof of Theorem 1 · p. 9
• The phase-dependent eigenvector alignment is determined by whether the spike produces a separated leading eigenvalue, using interlacing to compare the full and principal-submatrix spectra.The proof characterizes the first two eigenvalues and relates their separation to the alignment limit.Source: D. Proof of Theorem 1 · p. 9

IV. SAMPLING RATIOS AND PHASE TRANSITIONS

• The phase-transition analysis specifies the asymptotic cosine similarities as functions of the sampling ratio α and proves the critical-transition characterization.The section studies when the leading eigenvector is asymptotically correlated or uncorrelated with the target.Source: §IV · p. 9, A. Critical Sampling Ratios · p. 9

A. Critical Sampling Ratios

• The critical points are obtained from the sign change of ψ′α at the minimizing point λα of the strictly convex function ψα.The functions ζα and φ determine the unique point λ* and the sign condition governing correlation.Source: A. Critical Sampling Ratios · p. 9
• Transitions between correlated and uncorrelated phases occur exactly at zero-crossings of Δ(λ) within (τ, ∞), which map one-to-one to critical sampling ratios.The critical set is finite because Δ is analytic and not identically zero on the relevant bounded domain.Source: A. Critical Sampling Ratios · pp. 9–10
• At least one critical point exists because the continuous function Δ has a zero-crossing, while boundedness of z yields an upper bound on the critical values.The upper-bound argument uses z ∈ [0,τ] and the associated second-moment inequalities.Source: A. Critical Sampling Ratios · p. 10

• The critical sampling ratios αc,min and αc,max correspond to λc,min and λc,max through a one-to-one mapping.Source: B. Proof of Proposition 1 · p. 10
• The asymptotic squared cosine similarity ρ(α) admits an explicit parametric characterization obtained by substituting the limiting expressions into the main formula.Source: B. Proof of Proposition 1 · p. 10
• As α increases without bound, the squared cosine similarity satisfies ρ(α) → 1.Source: B. Proof of Proposition 1 · p. 10
• With one critical eigenvalue crossing, a single threshold separates an uncorrelated phase from a correlated phase concentrated around a cone about the target.Source: B. Proof of Proposition 1 · p. 10
• With multiple zero-crossings, correlated and uncorrelated phases can alternate between αc,min and αc,max.Source: B. Proof of Proposition 1 · pp. 10–11, Figure 4 · p. 11

C. Multiple Phase Transitions: an Example

• Three zero-crossings produce critical sampling ratios αc,1 = 3.6279×10^3, αc,2 = 9.6302×10^3, and αc,3 = 2.0947×10^5.Source: C. Multiple Phase Transitions: an… · p. 11
• The squared cosine similarity is zero below αc,1, briefly positive between αc,1 and αc,2, returns to zero, and becomes positive again above αc,3 while tending to one.Source: C. Multiple Phase Transitions: an… · p. 11
• The multiple-transition example is theoretical, with transitions at very large sampling ratios, and practical examples and simple conditions for one crossing remain open questions.Source: C. Multiple Phase Transitions: an… · p. 11

V. DISCUSSION

• The asymptotic theory requires m,n →∞, although simulations indicate accuracy at moderate dimensions; convergence rates remain to be quantified.Source: §V · p. 11
• For nonsymmetric acquisition functions, the linear estimator is preferable at very small α, while comparisons at moderate α depend on preprocessing.Source: §V · p. 12
• The target norm is not identified by spectral initialization, and extending the method to incorporate priors or broader low-rank sensing settings remains future work.Source: §V · pp. 12–13
• The asymptotic analysis is exact for Gaussian sensing vectors, while simulations suggest accurate predictions for non-Gaussian and complex ensembles but do not establish universality rigorously.Source: §V · p. 12, Figure 5 · p. 12

A. Sufficient Conditions for Assumption (A.5) to Hold

• A point mass at the upper boundary of z provides one sufficient condition for Assumption (A.5).Source: A. Sufficient Conditions for… · p. 13
• A density and conditional moment bounded below near the upper boundary provide a second sufficient condition for Assumption (A.5).Source: A. Sufficient Conditions for… · p. 13

B. Norm Estimation

• Spectral initialization estimates the orientation of ξn but not its norm.Source: B. Norm Estimation · p. 13
• For Gaussian sensing, moments of the measurements yield a simple norm estimator, and maximum likelihood can provide an asymptotically consistent alternative under standard conditions.Source: B. Norm Estimation · p. 13

• The leading eigenvector’s alignment is preserved under the transformation, reducing the proof to analyzing the transformed matrix.Source: C. Proof of Proposition 2 · p. 13
• The transformed matrix has a block-diagonal structure, so its eigenvalues combine those of a principal submatrix and a diagonal block.Source: C. Proof of Proposition 2 · pp. 13–14
• The principal block is an arrowhead matrix whose leading eigenvalue and eigenvector can be characterized through a scalar equation involving R(λ).Source: C. Proof of Proposition 2 · p. 14
• The proof treats three cases, including distinct leading eigenvalues and a repeated leading eigenvalue with nonunique leading eigenvectors.Source: C. Proof of Proposition 2 · p. 14
• At the critical point, one-sided derivatives of the eigenvalue function yield the corresponding characterization when differentiability fails.Source: C. Proof of Proposition 2 · p. 14

D. Proof of Proposition 3

• The proof begins by reducing convergence of the random measure to convergence of its empirical distribution function at continuity points.Source: D. Proof of Proposition 3 · p. 14
• Interlacing between the eigenvalues of Z and the rank-one perturbation M m yields mF Z(λ) −2 ≤(m −1)F M m(λ) ≤mF Z(λ) + 1.Source: D. Proof of Proposition 3 · pp. 14–15
• The empirical distribution function F M m(λ) converges almost surely to Fz(λ), the cumulative distribution function of z, at continuity points.The argument combines the strong law for the diagonal matrix Z with the interlacing bound in (88).Source: D. Proof of Proposition 3 · pp. 14–15
• The vector v=[z1s1, z2s2, . . . , zmsm]⊤ is almost surely nonzero for all sufficiently large m.Because P(zi=0)<1 and si≠0 almost surely, the i.i.d. sequence zi si contains infinitely many nonzero elements.Source: D. Proof of Proposition 3 · p. 15
• For λ>τ, the strong law gives almost-sure convergence of Rm(λ), and strict monotonicity of −Q(λ) permits the functional inverse characterization.Here τ is the upper support bound of the probability distribution of z.Source: D. Proof of Proposition 3 · p. 15

E. Auxiliary Lemmas

• For continuous nondecreasing fn converging almost surely to f, values at sequences xn→x∗ are controlled through nearby left and right comparison points.Source: E. Auxiliary Lemmas · p. 15
• When fn and f are strictly increasing with common inverse domains, the corresponding inverse evaluations converge through monotone bracketing around f−1(y).Sequences approaching the inverse target from below and above force the liminf and limsup to coincide.Source: E. Auxiliary Lemmas · p. 15
• The inverse-convergence proof uses βk and γk sequences converging to the target from opposite sides, then sends k→∞ to obtain the limit.Source: E. Auxiliary Lemmas · p. 15
• Under pointwise almost-sure convergence of convex functions, derivatives along xn→x∗ converge to f′(x∗) when f is differentiable at x∗.The proof bounds left and right derivatives using sequences approaching x∗ from both sides.Source: E. Auxiliary Lemmas · pp. 15–16
• The derivative lemma constructs an almost-sure event where function convergence and xn→x∗ hold, then applies convexity and one-sided derivative inequalities.The final argument treats both left and right derivatives symmetrically.Source: E. Auxiliary Lemmas · pp. 15–16