PaperlayerView exact revision on arXiv

Source-linked AI summary

Rank-One Signal Recovery in Sparse Wishart Noise

Preben Forer, Urte Adomaityte, Pierpaolo Vivo

arXiv:2609.28163v1cond-mat.dis-nncond-mat.stat-mechmath-phmath.MPstat.ML

TL;DR

The paper asks when a rank-one signal can be recovered from sparse Wishart noise, a setting relevant to sparse covariance structures with global effects. It uses replica calculations and population dynamics to characterize the top-eigenpair observables, finding a connectivity-dependent BBP-like threshold separating non-recovery from recovery.

  • Problem

    The paper asks when a rank-one signal can be recovered from sparse Wishart noise, which models sparse interactions alongside a global signal.

    Source: §1 · p. 3

  • Method

    The replica formalism expresses spectral observables through self-consistent recursive distributional equations, which are solved using population dynamics.

    Source: §7 · p. 23

  • Results

    Below θcrit the top eigenvalue remains that of the noise and overlap is zero; above θcrit the signal-associated eigenvalue leads and overlap is nonzero, with analytical results agreeing with numerical diagonalisation.

    Source: §7 · p. 24

  • Takeaways & Limitations

    The top eigenvector permits signal recovery when signal strength exceeds the connectivity-dependent critical threshold.

    Source: §7 · p. 24

    For non-degenerate degree distributions, determining the bulk transition requires second-largest-eigenpair analysis, and λb and θb are left for future work.

    Source: §5.2 · p. 18

Abstract

from arXiv · show

We study the high-dimensional recovery of a signal vector $\mathbf{x}$ in the presence of sparse Wishart-like noise. We define an $N \times N$ matrix $A = J+(\theta/N)\mathbf{xx}^{\top}$, where $\mathbf{xx}^{\top}$ is the rank-one deformation of the random noise matrix $J$. We consider a Wishart-like matrix $J={X}^{\top} X$, where $X$ is a sparse $M \times N$ random matrix with entries $X_{ij} = c_{ij}W_{ij}$, with $c_{ij}$ regulating the density of non-zero elements, and $W_{ij}$ the bond weights. Using the replica method, we compute analytically the top eigenpair statistics of $A$, and their dependence on the signal strength $\theta$, the rectangularity ratio $\alpha=\sqrt{M/N}$, and the average connectivity of the noise. The spectral observables are expressed in terms of a system of Recursive Distributional Equations, which are efficiently solved via a Population Dynamics algorithm. They allow us to compute the average largest eigenvalue $\langle\lambda_1\rangle_{A}$, the average top eigenvector component density, and the average overlap between the top eigenvector of $A$ and $\mathbf{x}$. We identify a critical threshold $\theta_{\mathrm{crit}}$--depending on the average connectivity of the noise--that marks a BBP-like phase transition: below this value, $\langle\lambda_1\rangle_{A}$ is unaffected by the signal, and the overlap vanishes. Thus, the signal is not recoverable from the top eigenvector of $A$. For $\theta>\theta_{\mathrm{crit}}$, the signal-related outlier eigenvalue becomes $\langle\lambda_1\rangle_{A}$ and the overlap is nonzero, allowing for recovery of the signal. The results are in excellent agreement with numerical diagonalisation. We show that in the dense limit, the recovery threshold and eigen-statistics converge to the results predicted by the classical BBP transition for additive rank-one deformations of dense Wishart matrices.

1. Introduction

The paper studies whether a global rank-one signal can be recovered from sparse Wishart noise, a setting motivated by sparse interactions and global effects in applications. It uses replica methods to characterize the recovery threshold as a function of noise connectivity and rectangularity.

1. Introduction

  • Rank-one signal recovery is relevant to PCA, matrix denoising, and teacher-student learning, where leading eigenpairs support dimensionality reduction or signal inference.The introduction also describes the surge in available data as motivating this high-dimensional problem.Source: §1 · p. 2
  • Classical dense spiked models exhibit a BBP threshold above which the top eigenvalue detaches from the bulk edge and the top eigenvector overlaps nontrivially with the signal.The cited classical setting includes rotationally invariant Wigner or Wishart noise.Source: §1 · pp. 2–3
  • Sparse covariance structures with dense global effects appear in financial markets and ecological association networks, but recovery thresholds and spectral observables remain largely unexplored.The paper frames recovery through the leading eigenvector of the observed matrix.Source: §1 · p. 3
  • The paper applies the replica formalism to sparse Wishart noise plus a dense rank-one signal, aiming to characterize recovery and the BBP-like transition by connectivity and rectangularity ratio α.Here α is introduced as the rectangularity ratio; the introduction writes its expression as α = M/N.Source: §1 · p. 3

2. Literature review

The literature review situates the paper among work on detectability, sparse random matrices, and dense spiked covariance models. It identifies finite-connectivity rank-one deformations of diluted Wishart matrices as an unaddressed top-eigenpair and recovery-transition problem.

2. Literature review

  • Related detection-threshold research spans sparse community detection and low-rank matrix estimation, with universality connections and recovery thresholds studied in stochastic block models.The review also mentions spectral clustering for sparse graphs.Source: §2 · p. 4
  • Neural-network studies connect sparse connectivity and low-rank structure to eigenspectra, network dynamics, and BBP-like separation of isolated eigenvalues from the bulk.The cited teacher-student analysis reports a BBP-like transition in learning dynamics.Source: §2 · p. 4
  • The review distinguishes robust PCA, which decomposes low-rank signal plus sparse corruption, from the paper’s sparse random-noise setting.The cited robust-PCA applications include video background separation and face-image analysis.Source: §2 · p. 4
  • Dense spiked Wishart research established eigenvalue and eigenvector behavior around the BBP transition, while sparse Wigner studies extended transition analysis to sparse noise.The review also notes replica-based population-dynamics methods for sparse matrix spectral calculations.Source: §2 · pp. 5–6
  • Prior work had not analyzed finite-connectivity additive rank-one deformations of diluted Wishart matrices at the level of top eigenpairs and recovery transitions.Earlier replica work treated diluted Wishart matrices without an added signal.Source: §2 · p. 5

3. The Model

The paper defines a sparse spiked Wishart observation model and uses replica methodology to obtain top-eigenpair observables. Its model builds sparse covariance noise from a weighted bipartite graph, while the replica setup turns eigenvalue and eigenvector quantities into averages of an auxiliary partition function.

3.1. The sparse spiked Wishart matrix model

  • The model’s goal is to compute top-eigenpair statistics and recovery thresholds for an observation matrix formed from sparse Wishart noise and a rank-one signal.The signal components are sampled independently from a distribution with finite second moment, and θ controls signal strength.Source: §3.1 · p. 6
  • The noise matrix is J = XᵀX, with X built from weighted edges of a bipartite graph whose row and column degrees are sampled under the handshake constraint.Conditioned on the degree sequences, the adjacency matrix is sampled uniformly over simple bipartite graphs satisfying those degrees.Source: §3.1 · pp. 6–7

3.2. Replica Methodology

  • In the zero-temperature limit, the partition-function mass concentrates around the leading eigenvector, enabling calculations of the largest eigenvalue, component density, and signal overlap.The replica trick is used to express the desired averages through the auxiliary partition function.Source: §3.2 · pp. 8–10
  • The replica method introduces an auxiliary partition function to compute averages of functions of the signal, a scalar argument, and the top eigenvector.At zero auxiliary coupling it recovers the partition function used for the top eigenvalue; derivatives with respect to the coupling yield top-eigenvector observables.Source: §3.2 · pp. 9–10

4. Main Results

The main results express the top eigenvalue and eigenvector observables through coupled self-consistency equations. A connectivity-dependent threshold separates non-recovery from partial recovery, and the threshold approaches the classical BBP result in the dense limit.

Self-consistency equations

  • The average largest eigenvalue equals λθ at the extremising saddle-point solution of coupled integral equations, which population dynamics can solve numerically.The resulting probability densities also support computation of other spectral properties.Source: §4 · pp. 11–12

Eigenvector observables

  • The results include the average top-eigenvector component density and overlap with the signal; q represents the average overlap under the paper’s orientation convention.The overlap is signed, and the top eigenvector is oriented relative to the signal.Source: §4 · p. 12

Recovery threshold

  • For θ≤θcrit, the top eigenvalue stays at the noise value and the asymptotic signal overlap vanishes; for θ>θcrit, the signal eigenvalue leads and overlap is nonzero.The latter regime permits partial signal recovery through the top eigenvector.Source: §4 · p. 13
  • The overlap equation has a q=0 non-recovery solution and a nonzero branch; the threshold occurs where that branch meets the noise top eigenvalue.The threshold condition is evaluated at λ=λθ=0.Source: §4 · p. 13

Dense limit

  • As ⟨s⟩→∞ after suitable rescaling, the recovery threshold converges to the classical BBP result for additive dense-Wishart deformations.Source: §4 · p. 14

Connectivity dependence

  • Increasing mean column degree ⟨s⟩ raises the signal strength needed for recovery, as denser noise obscures the signal.Source: §4 · p. 14

5. Special Cases

The special cases apply the general results to truncated Poisson and random biregular degree distributions, using their marginal degree distributions. Both show signal-recovery transitions, while the biregular case also exposes an intermediate regime involving the second eigenvector.

5. Special Cases

  • The RDE solutions depend on the marginal degree distributions, so the analysis specializes to truncated Poisson and random biregular cases with fixed noise weights and a zero-centered signal.The signal distribution has finite positive variance.Source: §5 · p. 14

5.1. Truncated Poisson

  • For truncated Poisson degrees, the observables use a numerically solved system of 2P equations with 2P unknowns, and the approximation improves as P increases.The resulting formulas specify the critical signal strength, top eigenvalue in recovery, and squared overlap.Source: §5.1 · p. 17
  • For the truncated Poisson setup, θ > θcrit makes the signal-associated eigenvalue overtake the noise eigenvalue, while the top-eigenvector overlap jumps to a positive value, matching direct diagonalisation.The comparison uses 50 matrices of size N = 5000 and theoretical predictions with truncation P = 7.Source: Figure 4 · p. 16, §5.1 · p. 17

5.2. Random Biregular

  • In the random biregular case, the critical signal strength and squared overlap have closed-form expressions; the noise outlier is λθ=0 = ⟨s⟩⟨k⟩.The right bulk edge determines when the signal-associated eigenvalue first exits the bulk.Source: §5.2 · p. 18
  • For θb < θ ≤ θcrit, the signal has nonzero overlap with the second eigenvector but is not recoverable from the top eigenvector; above θcrit, the top-eigenvector overlap is nonzero.The three-phase predictions agree with direct diagonalisation, and both overlap values are predicted by the formula in (55).Source: §5.2 · pp. 18–19
  • The biregular case permits exact bulk-transition analysis because its population distributions are point masses; for non-degenerate degrees, determining the bulk edge and transition is left to future work.For general degree distributions, the text expects partial recovery through the second eigenvector in an intermediate regime but does not establish it.Source: §5.2 · pp. 18–19

6. Population Dynamics

The population dynamics algorithm solves the recursive distributional equations by updating two empirical populations until their moments stabilize. It then checks integral constraints to select the eigenvalue and overlap parameters and estimates the top-eigenvector component density.

6. Population Dynamics

  • The algorithm updates two populations according to the recursive relations and treats stabilized population moments as equilibrium before evaluating integral constraints by Monte Carlo sampling.The populations represent joint distributions π(ω, h) and ρ(σ, μ), initialized from random uniform draws.Source: §6 · pp. 20–21
  • If either integral constraint fails, the algorithm rescales λ and q using α1 and α2, then repeats the population-dynamics sweeps until both constraints reach 1 within tolerance.The rescaling is motivated by how parameter changes affect the recursive distributional equations.Source: §6 · p. 21
  • In the recovery phase, the first moment of h shrinks to zero for all λ > λθ=0, so population stability alone does not identify the top eigenvalue.The constants α1 and α2 reach 1 only at the correct parameter choices, including λ = ⟨λ1⟩A and q as described by the constraints.Source: §6 · p. 21
  • The stabilized populations support Monte Carlo estimation of the top-eigenvector component density and average overlap, with the density matching numerical diagonalisation and the spike distribution in the recovery phase.The density is estimated by binning sampled values; Figure 7 compares population dynamics with diagonalisation across non-recovery and recovery settings.Source: §6 · pp. 21–22, Figure 7 · p. 23

7. Summary and conclusions

The paper uses replicas and self-consistent distributional equations to characterize eigenvalue and eigenvector observables for a rank-one signal in sparse Wishart noise. It identifies a connectivity-dependent recovery threshold and develops the replica calculation through disorder averaging, functional-integral representation, and a replica-symmetric change of variables.

7. Summary and conclusions

  • The analysis covers the average largest eigenvalue, top-eigenvector component density, and overlap with the signal for sparse Wishart noise plus a rank-one deformation.The noise matrix X is sparse and the signal term is θxxᵀ/N.Source: §7 · p. 23
  • Self-consistent recursive distributional equations yield the spectral observables, and population dynamics solutions agree excellently with direct diagonalisation.At equilibrium, replica order parameters λ and q correspond to the average largest eigenvalue and average signal overlap, respectively.Source: §7 · pp. 23–24
  • For θ<θcrit the top eigenvalue remains that of the noise and the signal overlap is zero; for θ>θcrit the signal eigenvalue leads and overlap is nonzero.The threshold depends on noise sparsity, encoded by ⟨k⟩ or ⟨s⟩, and on rectangularity α.Source: §7 · p. 24

Appendix A. Replica Calculation

  • The replica calculation averages the replicated partition function over disorder, introduces functional order parameters, applies a replica-symmetric ansatz, and evaluates the saddle point as β→∞.The stated derivation comprises six main steps, including normalization from degree distributions and derivation of saddle-point equations.Source: Appendix A · p. 26

Appendix A.1. Averaging the replicated partition function over the disorder

  • An auxiliary Erdős–Rényi connectivity factor simplifies disorder averaging without changing the ensemble, and the final expressions are independent of that factor.Fourier representations expose the degree constraints used in the averaging.Source: Appendix A.1 · p. 27

Appendix A.2. Znum: Functional integral representation

  • The averaged replicated partition function is rewritten as a functional integral amenable to saddle-point evaluation in the large-system limit.The derivation assumes self-averaging of empirical degree distributions.Source: Appendix A.2 · pp. 30–31

Appendix A.3. Znum: Replica-symmetric functional change of variables

  • A replica-symmetric change of variables represents fields as Gaussian mixtures, making integrals tractable and yielding saddle-point equations in recursive distributional form.The representation assumes field dependence through permutation-symmetric functions of replica-vector components.Source: Appendix A.3 · pp. 32–33

Appendix A.4. Zden: asymptotic behaviour

The appendix obtains large-system asymptotics for the normalization and replicated partition functions, then uses saddle-point densities to extract the leading eigenvalue expression. The resulting expression matches the main-text formula.

Appendix A.4. Zden: asymptotic behaviour

  • The normalization constant is put in a saddle-point form using self-averaging degree distributions, with its asymptotics determined by the normalization saddle-point equations.The equations follow by differentiating the normalization action with respect to its multipliers.Source: Appendix A.4 · p. 38

Appendix A.5. Full Asymptotics of ⟨Zn

  • Combining the numerator and denominator asymptotics gives the full large-system asymptotics of the average replicated partition function.The subsequent derivation obtains recursive distributional equations for the joint densities at the saddle point.Source: Appendix A.5 · pp. 38–39

Appendix A.6. Densities at the saddle point

  • The saddle-point densities and constraints determine λθ, which is used to calculate the average largest eigenvalue, assuming the replica and system-size limits can be exchanged.The appendix derives the expression after inserting the replicated-partition-function asymptotics.Source: Appendix A.6 · pp. 39, 42, 43

Appendix A.7. Extracting the leading β→∞term of A1(β)

  • The q-dependent terms cancel exactly, and inserting (A.146) into (A.126) yields the result claimed in the main text, with λθ satisfying the self-consistency equations in Eqs. (33) to (36).Source: Appendix A.7 · p. 45

Appendix A.8. Further Observables

The appendix extracts eigenvector observables from the replica formalism and identifies the overlap order parameter’s threshold behavior. It then develops inverse-moment tools for treating special degree distributions.

Appendix A.8. Further Observables

  • The appendix computes the average top-eigenvector component density and signal overlap using the formalism already developed for the largest eigenvalue.The order parameter q equals the average overlap between the top eigenvector and the signal.Source: Appendix A.8 · pp. 45–46
  • The overlap equation has a zero solution for θ≤θcrit and a nontrivial solution for θ>θcrit, with the threshold set by the marginal nontrivial solution.At threshold, λθ equals its zero-signal value.Source: Appendix A.8 · p. 47

Appendix B. Special degree distribution cases

  • For non-degenerate degree distributions, the inverse-moment expressions couple moments across all orders and are not closed.The special-case analysis assumes a zero-centered signal with finite variance and considers truncated Poisson and random biregular degrees.Source: Appendix B · pp. 47–48

Appendix B.1. Truncated Poisson

For truncated Poisson degrees, the appendix approximates the distributional equations with a finite truncation and derives threshold, eigenvalue, and overlap results. It compares the threshold estimate with population dynamics and gives the behavior on both sides of the transition.

Appendix B.1. Truncated Poisson

  • As truncation order P increases, the truncated-Poisson estimate of θcrit converges to the population-dynamics value.The comparison uses ⟨s⟩=3, ⟨k⟩=4, and kmax=smax=20.Source: Figure B1 · p. 50
  • The truncated-Poisson expression ˜Q(λθ) determines the transition value, typical top eigenvalue, and squared overlap.The threshold expression becomes exact as P→∞.Source: Transition value, top eigenvalue and… · p. 50
  • For θ≤θcrit, the typical top eigenvalue is the structural noise eigenvalue and the typical squared overlap is zero.Above threshold, the signal-associated eigenvalue is the top eigenvalue and the appendix gives the squared-overlap expression.Source: Transition value, top eigenvalue and… · pp. 50–51

Appendix B.2. Random Biregular

The random biregular case yields closed-form expressions for the recovery threshold and, above it, the typical top eigenvalue and squared overlap. Its noise spectrum is related to the spectrum of a biregular bipartite graph.

Appendix B.2. Random Biregular

  • With constant bond weights and a point-mass degree distribution, the saddle-point equations simplify and require only the (ω, σ) pair, with no truncation.The derivation chooses the positive branch for σ̄ because it is an inverse variance in the Gaussian replica ansatz.Source: Appendix B.2 · p. 51
  • The typical top eigenvalue and squared overlap in the recovery phase, and the critical signal strength, are obtained explicitly in closed form.The threshold is evaluated using the noise outlier eigenvalue; the recovery-phase eigenvalue is determined for θ > θcrit.Source: Appendix B.2 · p. 52
  • For W_ij = 1, the random biregular matrix has noise outlier eigenvalue λ_θ=0 = ⟨s⟩⟨k⟩.The result follows from the row and column sums of X and Perron–Frobenius.Source: Appendix B.2 · pp. 51–52
  • The nonzero spectrum of J is obtained by squaring the positive spectrum of the associated biregular bipartite adjacency matrix.The nontrivial spectral edge is inherited from the infinite biregular tree, and evaluating at that edge gives the transition value.Source: Appendix B.2 · pp. 52–53

Appendix C. The Dense Limit

In the high-connectivity limit, the analysis recovers the additive BBP-type transition for dense Wishart noise under a centered, connectivity-dependent bond-weight scaling. It gives the threshold, outlier eigenvalue, and squared overlap in the recovery phase.

Appendix C. The Dense Limit

  • The dense limit uses centered, connectivity-dependent bond weights so the noise spectrum remains order one as connectivity diverges.The weights have zero mean, and the analysis takes Poisson degree distributions with diverging average degrees.Source: Appendix C · p. 53
  • As connectivity grows, the curvature variables become non-fluctuating and the saddle-point distributions take a deterministic dense-limit form.The size-biased degree laws have vanishing relative fluctuations in this limit.Source: Appendix C · pp. 53–54
  • In the dense limit, the field distribution conditional on the signal coordinate is Gaussian, while its marginal is generally a mixture of Gaussians.This follows from the central limit behavior of the random sums while the signal-dependent term retains a single sample.Source: Appendix C · pp. 54–55
  • The critical threshold is the additive rank-one deformation threshold for dense Wishart (Marchenko–Pastur) noise under the present scaling.The dense noise upper edge is derived from the marginal zero-field solution.Source: Appendix C · pp. 53, 56
  • The recovery-phase outlier eigenvalue recovers the additive dense-Wishart BBP-type outlier branch under this scaling.The outlier is determined for θ > θcrit.Source: Appendix C · p. 56
  • The squared cosine overlap is dimensionless, lies between 0 and 1, and approaches 1 for perfect signal recovery.The paper's squared overlap uses a different normalization and is not itself normalized to unity.Source: Appendix C · p. 56
Loading 2609.28163v1…