Tensor PCA and the Kikuchi Algorithm (problem 9)

In 2014, Andrea Montanari and Emile Richard (Montanari & Richard, 2024) proposed a statistical model for understanding a variant of Principal Component Analysis in Tensor data. This is currently referred as the Tensor PCA problem. We will consider symmetric version of the problem in which the signal of interest is a point in the hypercube. Given $n,r$ and $\lambda$, the goal is to estimate (or detect) an unknown “signal” $x\in{\pm1}^n$ (drawn uniformly from the hypercube), from ``measurements’’ as follows: for $i_1<i_2<…<i_r$, \(Y_{i_1,i_2,...,i_r} = \lambda x^{\otimes r} + Z_{i_1,i_2,...,i_r}\) where $Z_{i_1,i_2,…,i_r}$ are iid $\mathcal{N}(0,1)$ random variables (and independent from $x$).

We will consider $r$ (and $\ell$, to be introduced below) fixed and $n\to\infty$, all big-O notation will be in terms of $n$. Tensor PCA is believed to undergo a statistical-to-computaional gap: Without regards for computational efficiency, it is possible to estimate $x$ for $\lambda=\Omega\left(n^{-\frac{r}{2}+\frac{1}{2}}\right)$. Efficient algorithms, such as the Sum-of-Squares hierarchy, are able to solve the problem at $\lambda=\tilde{\Omega}\left(n^{-\frac{r}{4}}\right)$, where $\tilde{\Omega}$ hides logarithmic factors. Local methods, such as gradient descent and approximate message passing succeed at $\lambda=\tilde{\Omega}\left(n^{-\frac12}\right)$. For $r=2$, the problem simply involves matrices, and indeed all these thresholds coincide. We point the reader to (A. Wein et al., 2019) and references therein for more on each of these thresholds.

In 2019, Alex Wein, Ahmed El Alaoui, and Cris Moore (A. Wein et al., 2019) proposed an algorithm for this problem based on the so-called Kikuchi Free Energy, it roughly corresponds to a hierarchy of message passing algorithms. They showed that this approach achieves (up to logarithmic factors) the threshold for the sum-of-squares approach, shedding light on the gap between the message passing and sum-of-squares frameworks.

We briefly describe the Kikuchi approach. We will focus on even $r$. There is a design parameter $\ell$ (with $n\gg \ell\geq \frac{r}2$) which we will consider fixed. The Kikuchi matrix $M$ is the $\binom{n}{\ell} \times \binom{n}{\ell}$ matrix (with rows and columns indexed by subsets $I\subset[n]$ of size $\ell$) given by \(M(\lambda)_{I,J} = \Big\{ \begin{array}{cl} Y_{I \Delta J} & \text{if} |I \Delta J| = r,\\ 0 &\text{otherwise,} \end{array}\) where $I\Delta J = (I\cup J) \setminus (I\cap J)$ denotes the symmetric difference. The goal is to understand when the top of the spectrum of $M$ reveals the spike $x$. It is shown in (A. Wein et al., 2019) that this happens for $\lambda = \tilde{\Omega}\left( n^{- \frac{r}4} \right)$. Since $Z$ is rotation invariant, we can assume WLOG that $x=\mathbf{1}$, the all-ones vectors.
The following conjecture also appears in (Bandeira, 2024) and is a reformulation of a conjecture in (A. Wein et al., 2019).

Conjecture 9 (Kikuchi Spectral Threshold)

Given $r,\ell, n$ positive integers satisfying $n\gg \ell\geq \frac{r}2$ and r even ($r$ and $\ell$ will be fixed and $n\to\infty$). For each $S\subset [n]$ with $|S|=r$ let $Z_S\sim\mathcal{N}(0,1)$, and all independent. Let $\lambda\geq 0$ and let $M$ be the $\binom{n}{\ell} \times \binom{n}{\ell}$ matrix (with rows and columns indexed by subsets $I\subset[n]$ of size $\ell$) given by \(\\ M(\lambda)_{I,J} = \left\{ \begin{array}{ccl} \lambda + Z_{I \Delta J} & \text{if} & |I \Delta J| = r,\\ 0 &\text{otherwise,}& \end{array} \right. \\\) where $I\Delta J = (I\cup J) \setminus (I\cap J)$ denotes the symmetric difference. Let $\lambda^\natural_{r,\ell}$ denote the threshold at which eigenvalues ``pop-out’’ of the spectrum of $M(\lambda)$: in other words $\lambda^\natural_{r,\ell}$ is the real number such that, for all $\lambda>\lambda^\natural_{r,\ell}$, there exists $\varepsilon>0$ such that $\mathbb{E}\lambda_{\max} M(\lambda)>(1+\varepsilon+o(1))\mathbb{E}\lambda_{\max} M(0),$ where $o(1)$ is a term that goes to zero as $n\to\infty$. For fixed $r$, we have \(n^{\frac{r}4}\lambda^\natural_{r,\ell}\to 0\) as $\ell\to\infty$ (note that this is after one has taken $n\to\infty$).

This would establish the very interesting phenomenon that there is no sharp threshold for polynomial time algorithms in Tensor PCA in the following sense: This conjecture would imply that by increasing $\ell$ (while remaining $\Theta(1)$, corresponding to increasing the computational cost of the algorithm while keeping it polynomial time), one would be able to decrease the critical signal-to-noise ratio in the sense of $n^{\frac{r}4}\lambda^\natural_{r,\ell}$ getting arbitrarily close to zero. Since the bound in (A. Wein et al., 2019) contains logarithmic factors on $n$ (present in $\tilde{\Omega}(\cdot))$, it does not allow to see this phenomenon for $\ell=\Theta(1)$.

For even $r$ and $\frac12r\leq\ell<\frac34r$ the threshold has been characterized in my work with Giorgio Cipolloni, Dominik Schr"oder, and Ramon van Handel (A. S. Bandeira et al., 2024), which is a follow up to the matrix concentration inequalities (leveraging intrinsic freeness) in my work with March Boedihardjo, and Ramon van Handel (A. S. Bandeira et al., 2023).

References

1. Montanari, A., & Richard, E. (2024). A statistical model for tensor PCA. Neural Information Processing Systems (NIPS 2014).
2. A. Wein, Alaoui, A. E., & Moore, C. (2019). The Kikuchi hierarchy and tensor PCA. FOCS.
3. Bandeira, A. S. (2024). Ten Open Problems involving Matrices, Randomness, Graphs, and more. Oberwolfach Report for Workshop 2417 (21.04.2024–26.04.2024). Available at \Urlhttps://Publications.mfo.de/Handle/Mfo/4149.
4. A. S. Bandeira, Cipolloni, G., Schroder, D., & R. van Handel. (2024). Matrix Concentration Inequalities and Free Probability II. Two-sided Bounds and Applications. Preprint, Available on ArXiv.
5. A. S. Bandeira, M. Boedihardjo, & R. van Handel. (2023). Matrix Concentration Inequalities and Free Probability. Inventiones Mathematicae, 234, 419–487.