The spectral threshold of Kikuchi matrices for tensor PCA
Let $r, \ell, n$ be positive integers with $n \gg \ell \ge \frac r2$ and $r$ even; $r$ and $\ell$ are fixed and $n \to \infty$. For each $S \subset [n]$ with $|S| = r$ let $Z_S \sim \mathcal{N}(0,1)$, all independent. For $\lambda \ge 0$ let $M(\lambda)$ be the $\binom{n}{\ell} \times \binom{n}{\ell}$ matrix, with rows and columns indexed by the subsets $I \subset [n]$ of size $\ell$, given by $$M(\lambda)_{I,J} = \begin{cases} \lambda + Z_{I \Delta J} & \text{if } |I \Delta J| = r,\\ 0 & \text{otherwise,}\end{cases}$$ where $I \Delta J$ is the symmetric difference. Let $\lambda^\natural_{r,\ell}$ be the threshold at which eigenvalues pop out of the spectrum of $M(\lambda)$: for all $\lambda > \lambda^\natural_{r,\ell}$ there is $\varepsilon > 0$ such that $\mathbb{E}\lambda_{\max} M(\lambda) > (1 + \varepsilon + o(1))\, \mathbb{E}\lambda_{\max} M(0)$, where $o(1)$ tends to $0$ as $n \to \infty$. This is the Kikuchi matrix of Wein, El Alaoui and Moore for tensor PCA, whose spectrum reveals the signal at $\lambda = \tilde{\Omega}(n^{-r/4})$, where $\tilde{\Omega}$ hides logarithmic factors. For $r = 2$ the problem involves only matrices, and all these thresholds coincide. Bandeira, Cipolloni, Schröder and van Handel characterized the threshold for $\frac r2 \le \ell < \frac34 r$.
Problem. Prove or disprove that for fixed $r$, $n^{r/4} \lambda^\natural_{r,\ell} \to 0$ as $\ell \to \infty$, after $n \to \infty$ has been taken.
Source: Bandeira, Conjecture 9 of Randomstrasse101, in “Tensor PCA and the Kikuchi Algorithm” (2024), reformulating a conjecture of Wein, El Alaoui and Moore (2019); also in Bandeira's Oberwolfach report (2024). Entry 5 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- PR — Probability
- Secondary
- ST
- Keywords
- Kikuchi hierarchy, random matrices, Randomstrasse101, statistical-to-computational gaps, tensor PCA
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@inproceedings{wein2019kikuchi,
author = {Wein, Alexander S. and El Alaoui, Ahmed and Moore, Cristopher},
title = {The {K}ikuchi hierarchy and tensor {PCA}},
booktitle = {60th IEEE Symposium on Foundations of Computer Science (FOCS 2019)},
year = {2019}
}
@misc{bandeira2024free2,
author = {Bandeira, Afonso S. and Cipolloni, Giorgio and Schr{\"o}der, Dominik and van Handel, Ramon},
title = {Matrix concentration inequalities and free probability {II}. {T}wo-sided bounds and applications},
year = {2024},
eprint = {2406.11453},
archivePrefix = {arXiv}
}
@misc{bandeira2024oberwolfach,
author = {Bandeira, Afonso S.},
title = {Ten Open Problems involving Matrices, Randomness, Graphs, and more},
howpublished = {Oberwolfach Report, Workshop 2417},
year = {2024},
url = {https://publications.mfo.de/handle/mfo/4149}
}
Resolution claims
In this work, we revisit algorithms for Tensor PCA: given an order-$r$ tensor of the form $T = G+λ\cdot v^{\otimes r}$ where $G$ is a random symmetric Gaussian tensor with unit variance entries and $v$ is an unknown boolean vector in $\{\pm 1\}^n$, what's the minimum $λ$ at which one can distinguish $T$ from a random Gaussian tensor and more …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-03 | Open → Solution claimed | The registry's curators | Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices v1 recorded from arXiv:2510.03061v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00054, "The spectral threshold of Kikuchi matrices for tensor PCA", clopen.solutions.