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 ).
We consider the tensor principal components analysis (tensor PCA) problem on the sphere, in which we are asked to recover an unknown vector in SN={x∈RN:∥x∥2=N} from a noisy observation of its k-th tensor power, for a fixed k≥3. Tensor PCA exhibits a well-studied information-computation gap: global algorithms such as spectral methods and sum-of-squares work above an algorithmic threshold, below which we know matching lower bounds (against these and some other restricted models of computation). In contrast, local algorithms such as Markov chains were only known to succeed from a random initialization at a polynomially larger signal-to-noise ratio, and were believed to be inferior to global algorithms for tensor PCA. Continuing the program initiated in Part I [arXiv:2610.16705], we show that spherical Langevin dynamics, when supplemented with annealing and ergodic averaging, achieves polynomial-time strong recovery above the algorithmic threshold from a uniformly random initialization. Together with Part I, our results demonstrate that local Markov chains can succeed all the way down to the algorithmic threshold from an uninformative cold start.
We study distinguishability and recovery of a sparse rank-one signal in a spiked Wigner model with independently sparse noise through a variety of algorithms and parameter regimes. The signal and noise have separate sparsity parameters, while the signal-to-noise ratio (SNR) remains of constant order as the matrix size grows. For sub-Gaussian noise and spikes whose nonzero coordinates are bounded away from zero, a leave-one-out quadratic thresholding procedure (a generalization of Ding et al., 2024) identifies the support. Sign synchronization yields exact recovery for a Rademacher spike, and spectral refinement yields strong recovery. The quadratic thresholding search parameter gives an explicit tradeoff between signal sparsity, noise sparsity, and computational cost. We also study extensions to sub-Gaussian spike priors through diagonal and quadratic thresholding. For Rademacher spikes with continuous nonzero noise, we develop an identical search algorithm that exploits unblurred signal entries, the existence of which permits distinguishability; connectivity of the graph they reveal provides a sufficient condition for exact recovery. These guarantees do not require moment assumptions on the continuous noise distribution. Together with our previous PCA results (Dumitriu et al., 2026), our analysis covers almost the entire space of parameters and regimes for distinguishing and recovering in our doubly sparse spiked Wigner model.
Ioana Dumitriu, JD Flynn, Zhichao Wang
University of California, San Diego · University of California, Berkeley
We provide a rigorous random matrix theory analysis of spiked cross-covariance models where the signals across two high-dimensional data channels are partially aligned. These models are motivated by multi-modal learning and form the standard generative setting underlying Partial Least Squares (PLS), a widely used yet theoretically underdeveloped method. We show that the leading singular values of the sample cross-covariance matrix undergo a Baik-Ben Arous-Peche (BBP)-type phase transition, and we characterize the precise thresholds for the emergence of informative components. Our results yield the first sharp asymptotic description of the signal recovery capabilities of PLS in this setting, revealing a fundamental performance gap between PLS and the Bayes-optimal estimator. In particular, we identify the SNR and correlation regimes where PLS fails to recover any signal, despite detectability being possible in principle. These findings clarify the theoretical limits of PLS and provide guidance for the design of reliable multi-modal inference methods in high dimensions.