The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model

Basic Information

• Paper ID: 2511.06040
• Title: The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model
• Author: Zhangsong Li (Peking University)
• Classification: math.ST, cs.LG, math.PR, stat.ML, stat.TH
• Publication Date: November 14, 2025 (arXiv v2: November 13, 2025)
• Paper Link: https://arxiv.org/abs/2511.06040

Abstract

This paper investigates the computational problem of detecting and estimating correlated signals from a pair of noisy rank-one matrices. The observation model is: $X = \frac{\lambda}{\sqrt{n}} xx^{\top} + W, \quad Y = \frac{\mu}{\sqrt{n}} yy^{\top} + Z$

where $x, y \in \mathbb{R}^n$ are signal vectors satisfying $\|x\|, \|y\| \approx \sqrt{n}$ with correlation $\langle x, y \rangle \approx \rho\|x\|\|y\|$, and $W, Z$ are independent Gaussian Wigner matrices. The authors propose an efficient algorithm that succeeds when $F(\lambda, \mu, \rho) > 1$, where: $F(\lambda, \mu, \rho) = \max\left\{ \lambda, \mu, \frac{\lambda^2\rho^2}{1-\lambda^2+\lambda^2\rho^2} + \frac{\mu^2\rho^2}{1-\mu^2+\mu^2\rho^2} \right\}$

The research demonstrates that the algorithm can leverage signal correlation for detection and estimation even when recovering signals from $X$ or $Y$ alone is computationally intractable. The authors further establish matching computational lower bounds via the low-degree polynomial framework, strongly suggesting that $F(\lambda, \mu, \rho) = 1$ is the exact computational threshold for this problem.

Research Background and Motivation

Research Problem

This paper studies signal detection and recovery in the correlated spiked Wigner model, a natural generalization of the classical spiked matrix model to the multi-modal setting.

Problem Significance

1. Theoretical Importance: The spiked matrix model is a classical framework in high-dimensional statistics for studying phase transitions and the statistical-computational gap. While the BBP (Baik-Ben Arous-Péché) phase transition in the single-matrix case has been thoroughly studied, the computational thresholds in multi-matrix correlated scenarios remain unclear.
2. Practical Relevance: Modern data analysis increasingly involves multiple correlated datasets (e.g., multi-sensor observations, multi-modal learning). Understanding how to effectively leverage inter-data correlations is crucial for practical applications.
3. Computational Complexity: This problem exemplifies the gap between information-theoretic optimality and computational feasibility, providing important insights into the nature of computational hardness.

Limitations of Existing Approaches

1. Suboptimality of Spectral Methods: Standard spectral methods such as Partial Least Squares (PLS) and Canonical Correlation Analysis (CCA) may be suboptimal under this model.
2. Incomplete Theoretical Coverage: Existing research KZ25, MZ25+ primarily focuses on the "linear" case where $\{x_k, y_k\}$ are orthogonal to $\{u_k, v_k\}$, not covering the symmetric spiked case ($u_k = x_k, v_k = y_k$).
3. Unknown Computational Threshold: In parameter regimes where signals are correlated and individual detection is difficult, the exact computational threshold remains undetermined.

Research Motivation

The authors aim to fully characterize the computational phase transition in the symmetric correlated spiked Wigner model:

• Propose an efficient algorithm achieving the optimal computational threshold
• Provide matching computational lower bounds
• Understand how signal correlation enables algorithms to overcome the single-matrix BBP threshold

Core Contributions

1. Exact Computational Threshold Characterization: Proves that $F(\lambda, \mu, \rho) = 1$ is the exact computational threshold for detection and recovery, where algorithms can leverage correlation to succeed at $\lambda < 1$ and $\mu < 1$ (where individual detection is infeasible).
2. Efficient Decorated Cycle Counting Algorithm: Proposes a polynomial-time algorithm based on decorated cycle counting with carefully designed weighting schemes achieving the optimal threshold:
   • Detection algorithm based on weighted counting of decorated cycles
   • Recovery algorithm based on weighted counting of decorated paths
   • Achieves $n^{2+o(1)}$ time complexity using color coding techniques
3. Matching Computational Lower Bounds: Establishes via the low-degree polynomial framework that when $F(\lambda, \mu, \rho) < 1$, all low-degree polynomial algorithms fail at strong detection.
4. Novel Analysis Techniques:
   • Lindeberg interpolation method for correlated signals
   • Fine-grained variance analysis controlling complex correlations in decorated subgraph counting
   • Two-step proof strategy combining Gaussian approximation and moment matching
5. Statistical Threshold for Rademacher Prior: Proves that for correlated Rademacher priors, the statistical threshold also occurs at $F(\lambda, \mu, \rho) = 1$, eliminating the statistical-computational gap.

Methodology Details

Task Definition

Detection Problem (Definition 1.1): Design an algorithm $A: \mathbb{R}^{n \times n} \times \mathbb{R}^{n \times n} \to \{0,1\}$ achieving strong detection, i.e.: $P(A(X,Y) = 0) + Q(A(X,Y) = 1) \to 0 \text{ as } n \to \infty$ where $P$ is the distribution of the signal-containing model and $Q$ is the pure noise distribution.

Recovery Problem (Definition 1.2): Design an algorithm $A: \mathbb{R}^{n \times n} \times \mathbb{R}^{n \times n} \to (\hat{x}, \hat{y})$ achieving weak recovery, i.e.: $\mathbb{E}_P\left[\frac{|\langle \hat{x}, x \rangle|}{\|\hat{x}\|\|x\|} + \frac{|\langle \hat{y}, y \rangle|}{\|\hat{y}\|\|y\|}\right] \geq \epsilon$ for some constant $\epsilon > 0$.

Model Architecture

1. Detection Statistic

Decorated Graph Definition: A decorated graph $H = (V(H), E(H); \gamma(H))$ is a graph where each edge is assigned a decoration $\gamma(e) \in \{\bullet, \circ\}$, corresponding to edges from matrices $X$ or $Y$ respectively.

Core Statistic (Formula 2.3): $f_H(X,Y) = \frac{1}{\sqrt{n^\ell \beta_H}} \sum_{[H] \in \mathcal{H}} \Xi(H) \sum_{S \subset K_n, S \cong H} f_S(X,Y)$

where:

• $\mathcal{H} = \mathcal{H}(\ell)$ is the set of all decorated cycles of length $\ell$
• $f_S(X,Y) = \prod_{(i,j) \in E_\bullet(S)} X_{i,j} \prod_{(i,j) \in E_\circ(S)} Y_{i,j}$ is the subgraph "signature"
• $\Xi(H) = \lambda^{|E_\bullet(H)|} \mu^{|E_\circ(H)|} \rho^{|\text{diff}(H)|}$ is the decorated weight
• $\beta_H = \sum_{[H] \in \mathcal{H}} \frac{\Xi(H)^2}{|\text{Aut}(H)|}$ is the normalization constant
• $\text{diff}(H)$ is the set of vertices appearing in both $\bullet$ edges and $\circ$ edges

Key Design Insights:

1. Decorated Cycles: By marking each edge of a cycle as coming from $X$ or $Y$, the number of possible decoration patterns grows exponentially as $2^\ell$, far exceeding the count of undecorated cycles.
2. Fine-Grained Weighting: The weight $\Xi(H)$ is carefully designed according to the combinatorial structure of the decoration, ensuring correct amplification of signal contributions.
3. Correlation Exploitation: The term $\rho^{|\text{diff}(H)|}$ captures the contribution of signal correlation.

2. Recovery Statistic

Decorated Paths: Define $\mathcal{J}(\ell)$ as the set of decorated paths of length $\ell$ where leaf nodes are on $\bullet$ edges.

Similarity Score (Formula 2.13): $\Phi^{\mathcal{J}}_{u,v} = \frac{1}{n^{\frac{\ell}{2}-1}\beta_{\mathcal{J}}} \sum_{[J] \in \mathcal{J}} \Xi(J) \sum_{\substack{S \subset K_n: S \cong J \\ L(S) = \{u,v\}}} f_S(X,Y)$

where $L(S) = \{u,v\}$ denotes the leaf nodes of the path.

Recovery Algorithm (Algorithm 2):

1. Compute similarity scores $\Phi^{\mathcal{J}}_{u,v}$ for all vertex pairs
2. Choose a reference vertex $w$ and set $\hat{x}_u = \Phi^{\mathcal{J}}_{w,u} \cdot \mathbb{1}\{\Phi^{\mathcal{J}}_{w,u} \leq R^4\}$ (truncation to control variance)
3. Output $\hat{x}$

Technical Innovations

1. Innovation in Decorated Subgraph Counting

• Distinction from Single-Graph Methods: Traditional cycle counting operates within a single graph; this work counts in the "product space" of two matrices.
• Necessity of Decoration: Decorations cause the number of possible patterns to grow exponentially, which is key to breaking the BBP threshold.
• Weighting Scheme: Unlike "unweighted" spectral methods such as PLS/CCA, this work's weighting scheme assigns different weights to different decoration patterns.

2. Technical Challenges in Statistical Analysis

Variance Control (Lemma 3.3): For decorated subgraphs $S, K$, the covariance bound is: $\text{Cov}_P(f_S, f_K) \leq \mathbb{1}_{V(S) \cap V(K) \neq \emptyset} \cdot n^{-\ell + |E_\bullet(S) \cap E_\bullet(K)| + |E_\circ(S) \cap E_\circ(K)|} \cdot M(S,K)$

where $M(S,K)$ is a complex combinatorial factor. The proof requires:

• Fine-grained moment condition analysis (Assumption 2.1)
• Case-by-case analysis of different overlap patterns
• Exploitation of the structure of $\text{diff}(S), \text{diff}(K)$

Key Lemma 2.2: Proves that the normalization constant satisfies: $D^{-1}\ell^{-2} A_+^\ell \leq \beta_H \leq D A_+^\ell$ where $A_+ = \frac{\lambda^2 + \mu^2 + \sqrt{\lambda^4 + \mu^4 - (4\rho^4-2)\lambda^2\mu^2}}{2}$

When $F(\lambda, \mu, \rho) > 1$, we have $A_+ > 1 + \delta$, ensuring exponential growth of the signal.

3. Color Coding for Efficient Computation

Challenge: Direct enumeration of all isomorphic subgraphs requires $n^{O(\ell)}$ time.

Solution (Section 4):

1. Random coloring $\tau: [n] \to [\ell]$, with each vertex independently and uniformly colored
2. Count only "colored" subgraphs (all vertices have different colors)
3. Repeat $t = \lceil 1/r \rceil$ times (where $r = \ell!/\ell^\ell = e^{-\Theta(\ell)}$) and average
4. Dynamic programming computation: reduces time complexity from $n^{O(\ell)}$ to $n^{2+o(1)}$

Approximate Statistic (Formula 4.4): $\tilde{f}_H = \frac{1}{\sqrt{n^\ell \beta_H}} \sum_{[H] \in \mathcal{H}} \Xi(H) \left(\frac{1}{tr} \sum_{k=1}^t g_H(X,Y,\tau_k)\right)$

Proposition 4.1: Proves that $\frac{\tilde{f}_H - f_H}{\mathbb{E}_P[f_H]} \xrightarrow{L^2} 0$, i.e., the approximation error is negligible.

4. Novel Techniques for Low-Degree Polynomial Lower Bounds

Gaussian Additive Model (Section 5.2): Leverages known results (Proposition 5.6); the low-degree advantage is: $\chi^2_{\leq D}(\hat{P}; \hat{Q}) = \mathbb{E}_{(x,y), (x',y') \sim \pi}\left[\exp_{\leq D}\left(\frac{\lambda^2\langle x,x' \rangle^2 + \mu^2\langle y,y' \rangle^2}{2n}\right)\right]$

Core Difficulty: $\langle x, x' \rangle$ and $\langle y, y' \rangle$ are correlated, making standard analysis fail.

Innovative Solution (Lemma 5.8):

1. Gaussian Approximation: Proves that $(\frac{\langle x,x' \rangle}{\sqrt{n}}, \frac{\langle y,y' \rangle}{\sqrt{n}})$ behaves like a standard normal pair $(U,V)$ with correlation $\rho^2$
2. Lindeberg Interpolation: Constructs an interpolation sequence $U_t, V_t$ (Formulas D.2-D.3), gradually transitioning from $(X_1,Y_1),\ldots,(X_n,Y_n)$ to $(\zeta_1,\eta_1),\ldots,(\zeta_n,\eta_n)$
3. Moment Matching: Proves that for all low-order moments, the difference is $n^{-1/2+o(1)}$ (Claims D.1-D.2)
4. Gaussian Bound (Lemma 5.7): Direct computation in the Gaussian case, using $F(\lambda,\mu,\rho) < 1$ to obtain an $O(1)$ bound

Experimental Setup

Theoretical Results (No Experimental Data)

This is a purely theoretical work containing no numerical experiments. All results are mathematical theorems and proofs.

Main Theoretical Guarantees

Theorem 2.4 (Detection Upper Bound): Under Assumption 2.1 and $F(\lambda, \mu, \rho) > 1 + \epsilon$, choosing $\omega(1) = \ell = o(\log n / \log \log n)$, we have: $P(f_H(X,Y) \leq \tau) + Q(f_H(X,Y) \geq \tau) = o(1)$

Theorem 2.8 (Recovery Upper Bound): Under the same conditions and $(1+\delta)^\ell \geq n^2$: $\mathbb{E}_P\left[\frac{|\langle \hat{x}, x \rangle|}{\|\hat{x}\|\|x\|}\right] \geq \Omega(1)$

Theorem 5.4 (Computational Lower Bound): Under Assumption 5.1 and $F(\lambda, \mu, \rho) < 1 - \epsilon$, for all $D = n^{o(1)}$: $\chi^2_{\leq D}(\hat{P}; \hat{Q}) = O_{\lambda,\mu,\rho,\epsilon}(1)$

Theorem E.1 (Statistical Lower Bound, Rademacher Case): For correlated Rademacher priors, when $F(\lambda, \mu, \rho) < 1 - \epsilon$, we have $\chi^2(\hat{P}; \hat{Q}) = O(1)$, making strong detection statistically impossible.

Experimental Results

Summary of Theoretical Results

The paper establishes the following main results through rigorous mathematical proofs:

1. Exact Phase Transition Threshold

$F(\lambda, \mu, \rho) = \max\left\{\lambda, \mu, \frac{\lambda^2\rho^2}{1-\lambda^2+\lambda^2\rho^2} + \frac{\mu^2\rho^2}{1-\mu^2+\mu^2\rho^2}\right\} = 1$

• Upper Bound: Polynomial-time algorithm succeeds when $F > 1$
• Lower Bound: Low-degree polynomial fails when $F < 1$
• Statistical Threshold (Rademacher): $F = 1$ is also the information-theoretic threshold

2. Role of Correlation

When $\lambda, \mu < 1$ (individual detection infeasible, below BBP threshold) but $\frac{\lambda^2\rho^2}{1-\lambda^2+\lambda^2\rho^2} + \frac{\mu^2\rho^2}{1-\mu^2+\mu^2\rho^2} > 1$, the algorithm leverages correlation to succeed.

Example: Set $\lambda = \mu = 0.8, \rho = 0.9$, then:

• Single matrix: $\lambda = 0.8 < 1$ (below BBP threshold, detection difficult)
• Dual matrix: $F \approx 1.8 > 1$ (detection feasible)

3. Algorithm Complexity

• Detection: $O(n^{2+o(1)})$ time
• Recovery: $O(n^{T+o(1)})$ time, where $T = O(\ell/\log n + 1)$
• Parameter choice: $\ell = \Theta(\log n)$

Key Technical Insights

1. Asymptotic Behavior of Normalization Constant (Lemmas 2.2, 2.6):
   • $\beta_H \asymp A_+^\ell$, where $A_+ > 1$ if and only if $F > 1$
   • This explains why $F = 1$ is the phase transition point
2. Variance Control (Lemma 3.2): $\frac{\text{Var}_P[f_H]}{\mathbb{E}_P[f_H]^2} = o(1)$ The proof requires fine analysis of $O(\ell^4)$ different subgraph overlap patterns
3. Approximation Error of Color Coding (Proposition 4.1): $\mathbb{E}\left[\left(\frac{\tilde{f}_H - f_H}{\mathbb{E}_P[f_H]}\right)^2\right] = o(1)$
4. Moment Matching for Low-Degree Lower Bound (Lemma 5.8): For $k, \ell = n^{o(1)}$: $\left|\mathbb{E}\left[\left(\frac{\sum X_j}{\sqrt{n}}\right)^{2k}\left(\frac{\sum Y_j}{\sqrt{n}}\right)^{2\ell}\right] - \mathbb{E}\left[\left(\frac{\sum \zeta_j}{\sqrt{n}}\right)^{2k}\left(\frac{\sum \eta_j}{\sqrt{n}}\right)^{2\ell}\right]\right| = n^{-1/2+o(1)} \cdot \mathbb{E}[U^{2k}V^{2\ell}]$

Related Work

Spiked Matrix Models

1. Single-Matrix BBP Phase Transition BBP05, FP07, CDMF09, AGZ10: Classical work establishing $\lambda = 1$ as the spectral method threshold
2. Statistical-Computational Gap LKZ15, KXZ16, BDM+16, BMV+18, EKJ20, LM19: Existence of statistically detectable but computationally hard regions at $\lambda < 1$ in sparse PCA
3. Low-Degree Lower Bounds KWB22, MW25: Proving low-degree polynomial failure at $\lambda < 1$

Correlated Spiked Models

1. Linear Case KZ25, MZ25+: Studies models where $\{x_k, y_k\}$ are orthogonal to $\{u_k, v_k\}$
   • Characterizes detectability thresholds of Bayes-optimal estimators
   • Analyzes high-dimensional limits of PLS and CCA
   • Distinction from This Work: Symmetric case $u_k = x_k, v_k = y_k$ requires entirely new analysis
2. CCA-Related Work BHPZ19, GW19, Yang22a, Yang22b, BG23+:
   • BHPZ19: Studies $X = \lambda x u^\top + W, Y = \mu y v^\top + Z$ ($u, v$ independent of signals)
   • MY23: Studies $X = \lambda x \mathbf{1}^\top + W, Y = \mu y \mathbf{1}^\top + Z$
   • Distinction from This Work: Symmetric structure brings fundamentally different challenges; existing techniques do not directly apply

Subgraph Counting Methods

1. Community Detection MNS15, MNS24, Ban18, BM17: Cycle counting achieves optimal detection threshold for SBM
2. Non-Backtracking Walks Mas14, MNS18, BLM15, AS15, AS18: Used for community recovery
3. Color Coding AYZ95, AR02, ADH+08, HS17, MWXY24, MWXY23, Li25+: Efficient computation of subgraph statistics
4. This Work's Contribution: First generalization of decorated subgraph counting to the dual-matrix setting

Low-Degree Polynomial Framework

1. Theoretical Foundation BHK+19, HS17, HKP+17, Hop18: Low-degree method as a unified framework for computational lower bounds
2. Applications KWB22, SW22, DMW25, MW25, DKW22, BEH+22, DDL23+, CDGL24+: Various high-dimensional inference problems
3. This Work's Innovation: Lindeberg interpolation technique for correlated priors, generalizable to other correlated signal problems

Conclusions and Discussion

Main Conclusions

1. Exact Threshold: $F(\lambda, \mu, \rho) = 1$ is the exact computational threshold for the symmetric correlated spiked Wigner model (under the low-degree polynomial framework)
2. Value of Correlation: Algorithms can leverage signal correlation to succeed in regions where individual detection is infeasible ($\lambda, \mu < 1$)
3. Algorithm Optimality: The decorated subgraph counting algorithm achieves the computational threshold and may outperform standard spectral methods like PLS/CCA
4. No Gap for Rademacher Case: For correlated Rademacher priors, statistical and computational thresholds coincide

Limitations

1. Prior Assumptions (Assumptions 2.1, 5.1):
   • Requires bounded fourth moments (upper bound)
   • Requires sub-Gaussianity and positive correlation (lower bound)
   • Does not cover all possible prior distributions
2. Symmetry Restriction: Only considers the symmetric case $u = x, v = y$; the general rank-one case $X = \lambda xu^\top + W$ remains unresolved
3. Suboptimality of Recovery: Only proves weak recovery (correlation $\Omega(1)$); exact $L^2$ loss characterization is missing
4. Limitations of Low-Degree Framework:
   • Low-degree conjecture has been refuted in some problems BHJK25
   • Cannot completely rule out the existence of non-low-degree algorithms
   • Still provides strong evidence for "high-dimensional" problems
5. Computational Complexity: While polynomial-time, $n^{2+o(1)}$ may still be slow on large-scale data
6. General Rank Case: Computational thresholds for rank $r > 1$ correlated spiked models remain open

Future Directions

The authors propose several important future research directions in Section 6:

1. Statistical Thresholds: For general priors (e.g., correlated Gaussian, sparse Rademacher), is the statistical threshold also $F = 1$?
2. Optimal Recovery Algorithms: In the $F > 1$ region, find algorithms achieving minimal $L^2$ loss (analogous to AMP algorithms MV21 in the single-matrix case)
3. General Rank Models: Generalize to rank $r > 1$ correlated spiked models (Formula 1.1)
   • Characterization of computational thresholds
   • Generalization of decorated subgraph methods
4. Other Multi-Modal Problems:
   • Multi-layer community detection
   • Multi-view clustering
   • General multi-modal inference problems
5. Algorithm Improvements:
   • Reduce computational complexity (from $n^{2+o(1)}$ to near-linear)
   • Practical algorithm variants

In-Depth Evaluation

Strengths

1. Depth and Completeness of Theoretical Contribution

• Exact Threshold: Upper and lower bounds match perfectly, providing a complete picture
• Novel Proof Techniques: Both decorated subgraph counting and Lindeberg interpolation for correlated signals are innovative
• Generality: Methods may apply to a broader class of correlated signal problems

2. Technical Innovation

• Decorated Subgraphs: Natural generalization of single-graph subgraph counting to the dual-matrix setting; simple yet non-trivial
• Weighting Scheme: Carefully designed weights $\Xi(H) = \lambda^{|E_\bullet|}\mu^{|E_\circ|}\rho^{|\text{diff}|}$ capture the combinatorial structure of signals
• Variance Analysis: Fine-grained analysis handling $O(\ell^4)$ overlap patterns demonstrates technical sophistication

3. Mathematical Rigor

• All theorems have complete proofs
• Auxiliary lemmas are well-organized with clear logical flow
• Constant dependencies are explicit ($O_{\lambda,\mu,\rho,\epsilon}(1)$)

4. Writing Quality

• Clear structure: introduction, main results, proofs, appendix are well-organized
• Comprehensive symbol system: Section 1.4 provides detailed notation conventions
• Intuitive explanations: Clear exposition of ideas before technical details

Weaknesses

1. Lack of Numerical Verification

• As a purely theoretical work, no numerical experiments verify theoretical predictions
• Cannot assess algorithm performance at finite $n$
• Missing practical comparisons with PLS/CCA

2. Limited Practical Utility

• $n^{2+o(1)}$ complexity may be impractical for large-scale data
• Parameter selection (e.g., $\ell$) requires knowledge of $\lambda, \mu, \rho$
• Algorithm constants may be large (though theoretically polynomial)

3. Limited Coverage

• Only handles symmetric case; general rank-one model unresolved
• Strong prior assumptions may exclude some practical distributions
• Rank $r > 1$ case completely open

4. Low-Degree Framework Controversy

• Low-degree conjecture is not a theorem; counterexamples exist BHJK25
• Computational lower bounds hold only for specific computational models
• Cannot completely rule out other algorithms

5. Unclear Relationship with Existing Spectral Methods

• Authors conjecture PLS/CCA are suboptimal but provide no rigorous proof
• MZ25+'s PLS analysis uses different assumptions, making direct comparison difficult
• Actual performance comparison would be valuable

Impact

Contribution to the Field

1. Theoretical Benchmark: Establishes exact computational threshold for correlated spiked models, becoming a benchmark result
2. Methodology: Decorated subgraph counting and low-degree analysis for correlated signals generalizable to other problems
3. Conceptual Clarity: Clarifies how correlation helps overcome single-matrix computational barriers

Practical Value

• Indirect Impact: Theoretical insights can guide practical algorithm design
• Limitations: Direct application constrained by computational complexity
• Potential: Simplified versions or heuristic algorithms may be practical

Reproducibility

• Theoretical Verification: Complete proofs allow expert verification
• Algorithm Implementation: Clear pseudocode (Algorithms 1-6) makes implementation feasible in principle
• Numerical Reproduction: Difficult without experimental code; implementation details require supplementation

Applicable Scenarios

Theoretical Research

• Phase transition phenomena in high-dimensional statistics
• Theoretical analysis of statistical-computational gaps
• Applications and development of low-degree polynomial methods

Potential Applications

1. Multi-Modal Learning: Multiple correlated high-dimensional observations
2. Signal Processing: Multi-sensor signal detection and estimation
3. Bioinformatics: Joint analysis of correlated omics data
4. Network Analysis: Structure detection in multi-layer networks

Constraints

• Requires moderate signal sparsity (not too sparse)
• Requires known or estimable correlation structure
• Data dimension cannot be too large ($n^{2+o(1)}$ complexity)
• Signal-to-noise ratio must be in specific range

Key References

1. BBP05, FP07, CDMF09: Classical BBP phase transition work, foundational for single-matrix theory
2. KWB22: Application of low-degree polynomial framework to PCA, main reference for lower bound analysis
3. MNS15, MNS24: Subgraph counting in community detection, inspired algorithm design
4. KZ25, MZ25+: Recent work on correlated spiked models, direct predecessor to this work
5. AYZ95, HS17: Color coding techniques for efficient subgraph statistics computation
6. LM19, EKJ20: Statistical-computational gap in single-matrix case, provides comparison baseline

Overall Assessment

This is a high-quality theoretical paper achieving important breakthroughs in computational complexity research for correlated spiked Wigner models. Main strengths include:

1. Completeness: Matching upper and lower bounds provide exact threshold characterization
2. Innovation: Both decorated subgraph counting and low-degree analysis for correlated signals are novel
3. Technical Depth: Sophisticated proof techniques handling complex combinatorial and probabilistic problems
4. Theoretical Significance: Reveals fundamental role of signal correlation in computation

Main limitations include:

1. Practical Utility: High algorithm complexity; lacks numerical verification
2. Coverage: Only symmetric case; general models unresolved
3. Framework Dependence: Lower bounds depend on low-degree polynomial conjecture

Recommended For: Researchers in high-dimensional statistics, computational complexity, random matrix theory, or multi-modal learning theory. For practitioners, the paper provides important theoretical guidance, though algorithms may require simplification or modification for practical use.

Academic Value: Expected to become an important reference in the field, likely publishable in top-tier statistics or theoretical computer science venues (e.g., Annals of Statistics, Journal of Machine Learning Research, or theory conferences).