We study a fundamental problem in machine learning: partial recovery of a planted signal v∈Sn−1 from a spiked tensor X=λv⊗p+Z, where Z has symmetric Gaussian entries of variance ≍n−1. While previous works replace Z by an i.i.d. standard Gaussian tensor to circumvent technical difficulties caused by dependencies, this paper directly analyzes the symmetric model via random matrix theory. We show that the square unfolding algorithm is subject to a sharp phase transition for partial recovery at λ≍n(p−2)/4, validating an open conjecture from Montanari and Richard (2014). We get precise expressions for the limiting spectral distribution, deterministic equivalent, phase transition threshold and overlap. The main message is that unfolded symmetric tensors spectrally behave like standard Wigner matrices, up to simple transformations accounting for high-order symmetries. We consider extensions to multiple orthogonal spikes, recursive unfolding and non-square unfolding via disproportionate random matrix theory, leading to an interesting conjectured statistical-computational tradeoff regarding the choice of unfolding: square versus long.
Figures & tables
Figure 1: Illustration of the Tensor PCA problem for p=4 and n=20 . Top: spiked tensor model X=λv⊗p+Z , unfolded into an n2×n2 matrix X (see Section 2 for notation). Middle: samples for increasing SNR λ . Bottom: recovered signal, v^v^⊤ , where v^ is the leading eigenvector of X . We observe a phase transition in signal recovery between 0.5 and 1 , where the overlap goes from 0% to 80%.
Figure 2: Simplified illustration of the conjectured statistical–computational gap for partial recovery, as a function of the SNR λ . Estimation of the planted signal v∈Sn−1 is impossible below the statistical threshold ( Jagannath et al., 2020 ) . Above, it is possible by MLE but computationally hard. Below the conjectured computational threshold, no low-degree algorithm achieves recovery ( Kunisky et al., 2022 ) , while above, some polynomial-time algorithms—such as unfolding and partial tracing—do. Above the local threshold, algorithms such as power iteration, approximate message passing and gradient descent work ( Montanari and Richard, 2014 ; Ben Arous et al., 2020 ) . Figure adapted from Wein (2024) .
Figure 3: Theoretical and simulated spectral distribution of M:=αp,q−1n−(p−2)/4Φq(Z) , with Z∼GOTEp,n , for p=4 and n=100 (see Theorem 10 ).
Figure 4: Theoretical and simulated eigenvalues and overlaps of M:=Φq(λv⊗p+Z) , with Z∼GOTEp,n , for p=4 and n∈{20,50,100} (see Theorem 14 ).
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Theoretical and simulated spectral distribution of the normalized symmetrically unfolded standard Gaussian noise, M:=β−1n−p/4Φq(Z) , with Z∼SGp,n , for p=4 and n=100 (see Theorem 20 ).
Figure 6: Theoretical and simulated eigenvalues and overlaps for the symmetrically unfolded spiked tensor M:=Φq(λv⊗p+Z) , with Z∼SGp,n , for p=4 and n∈{20,50,100} (see Theorem 22 ).
Figure 7: Theoretical and simulated spectral distribution and subspace overlap of the symmetrically unfolded CP model M:=αp,q−1n−(p−2)/4Φq(∑k=1rλkvk⊗p+Z) , with Z∼GOTEp,n , for p=4 , r=4 and n=100 (see Corollary 23 ).
Figure 8: Theoretical and simulated overlaps for the recursively unfolded spiked tensor T:=λv⊗p+Z , with Z∼GOTEp,n , for p=4 and n∈{20,50,100} (see Conjecture D ).
Figure 9: Theoretical and simulated eigenvalues and overlaps for the symmetrically unfolded spiked tensor M:=Φk(λv⊗p+Z) , with Z∼GOTEp,n , for (p,k,n)=(3,1,500) (top) and (p,k,n)=(4,{1,2},100) (bottom). See Conjecture E .
Figure 10: Theoretical and simulated overlaps for the recursively symmetrically unfolded spiked tensor M:=Φk(λv⊗p+Z) , with Z∼GOTEp,n , for p=4 , k∈{1,2} and n=100 (see Conjectures D and E ).