Sharp Recovery Thresholds of Tensor PCA Spectral Algorithms
Authors: Michael Jacob Feldman
David Donoho
Venue: NeurIPS 2023 poster (2023)
Keywords: tensor PCA
spectral algorithms
random matrix theory

Abstract: Many applications seek to recover low-rank approximations of noisy tensor data. We consider several practical and effective matricization strategies which construct specific matrices from such tensors and then apply spectral methods; the strategies include tensor unfolding, partial tracing, power iteration, and recursive unfolding. We settle the behaviors of unfolding and partial tracing, identifying sharp thresholds in signal-to-noise ratio above which the signal is partially recovered. In particular, we extend previous results to a much larger class of tensor shapes where axis lengths may be different. For power iteration and recursive unfolding, we prove that under conditions where previous algorithms partially recovery the signal, these methods achieve (asymptotically) exact recovery. Our analysis deploys random matrix theory to obtain sharp thresholds which elude perturbation and concentration bounds. Specifically, we rely upon recent disproportionate random matrix results, which describe sequences of matrices with diverging aspect ratio.

Sharp Recovery Thresholds of Tensor PCA Spectral Algorithms
David L. Donoho Department of Statistics Stanford University donoho@stanf ord. edu
Michael Feldman
Department of Statistics Stanford University fel mal.dmmn@sttaffordd edu
Abstract
Many applications seek to recover low-rank approximations of noisy tensor data. We consider several practical and effective matricization strategies which construct specific matrices from such tensors and then apply spectral methods; the strategies include tensor unfolding, partial tracing, power iteration, and recursive unfolding. We settle the behaviors of unfolding and partial tracing, identifying sharp thresholds in signal-to-noise ratio above which the signal is partially recovered. In particular, we extend previous results to a much larger class of tensor shapes where axis lengths may be different. For power iteration and recursive unfolding, we prove that under conditions where previous algorithms partially recovery the signal, these methods achieve (asymptotically) exact recovery. Our analysis deploys random matrix theory to obtain sharp thresholds which clude perturbation and concentration bounds. Specifically, rely upon recent disproportionate random matrix results, which describe sequences of matrices with diverging aspect ratio.
Introduction
censors-mullee way arrays-and and tensor methods are fundamental to modern data analysis. Data given by three or more indices are increasingly the focus diverse areas including signal and image processing [9, 19, 22], while high-order moments represented by tensors are of interest in problems such as community detection and learning latent variable models [1, 2, 8].
The spiked tensor model, introduced by Montanari and Richard [20]. is a simple statistical model of tensor data with latent low-rank structure. Observed data X of dimensions n1 X n2 ny are the sum of low-rank tensor and noise:
j E [b]] E [ng], where 1: 2 2 is the tensor order, is a signal strength, " E S E [R:]. are unit vectors, and 7 is noise tensor. Noise entries assumed be independent standard Gaussians:
Xiy A01, U2,42 Ukit + 42....22
(1)
Zi..i.....h fidd 1),
[K], ig [my].
Estimation of ......, Ug. and the low-rank component of X generalizes to tensors the problem of low-rank matrix approximation- prinncppll component analysis (PCA) and therefore known as tensor PCA.
This model reduces for V1 and 02 given by the first left and right singular vectors i and 0r2 of X, respectively. For k: 2 3. however, computation of the maximum likelihood estimators the low rank component amounts solving an NP hard problem (Hillar and Lim [14]).
the spiked matrix model, with maximum likelihood estimators of
sup u
Σ $1....
X U1.6 Ug.
(2)
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

necessitating alternate, efficient algorithms.
1.1 Contributions
This paper studies matricization- approaches, which convert tensors matrices (by reshaping or by contracting constructions to be described) and then apply spectral methods. We assume the spiked tensor model in -igh-iimensional asymptotic framework in which each array dimension 7i1 .... ng tends to infinity; we make no assumptions on their relative rates. While previous analyses of tensor PCA algorithms have assumed order k 3. supersymmetry 2 22 format n2
Vk. or hypercubical TAj: we permit tensors of diverse dimensions nj and unrelated V/j
In this setting, fully analyze tensor unfolding or reshaping, a widespread technique [12, 19]. Additionally, we analyze the partial tracing approach of Hopkins et al. [16], discovering its asymptotic equivalence unfolding in performance- improvement over previous analysis. We identify sharp thresholds in signal-to-noise ratio above which these algorithms partially recover the signal, and provide exact formulas for their limiting performance. Finally, we study generalizations of the power iteration and recursive unfolding algorithms of [20]. Above the same thresholds characterizing partial recovery of unfolding and partial tracing, these algorithms achieve (asymptotically) exact signal recovery. In other words, for signal- -ooiie ratios such that unfolding or partial tracing partially recover the signal, power iteration and recursive unfolding exactly recover the signal.
Our approach relies upon fundamental and penetrating random matrix theoretic (RM'T) results. Precise analysis of tensor PCA algorithms, including pinpointing of phase transitions and sharp performance quantification as provided here, is not possible purely via more standard tools in theoretical machine learning, such as matrix concentration and vector perturbation bounds. Specifically, we rely upon recent disproportionate random matrix results (introduced in Section I.3) which describe sequences of matrices with diverging aspect ratio.
This work conciscly demonstrates in the context of tensor PCA the advantages of an RMT-backed approach. Indeed, application of spiked matrix results yields simple and elegant theorems and proofs which are easily read. For example, the analysis of the partial tracing in [16], involving challenging matrix concentration and perturbation calculations, is reduced results are admittedly purely asymptotic, there are no hidden constants or logarithmic factors. Even for modest-sized tensors, simulations demonstrate close agreement with theory.
few careful lines. Though
1.2 Assumptions and Notation
Without loss of generality, we assume À 2 and my S n2 S ... S ni. taking ny to be the "fundamental" problem index; that is n, ny (m)). ). [k.] We say estimator ig partially recovers ny if almost surely,
lim inf (ey, 05)1 0, Bi B10000
and új exactly recovers vy if (ey, 05)l 0.s. 1. In words, partial recovery demands a positive limit for the cosine similarity, while exact recovery requires asymptotically perfect cosine similarity.
We make the rank-one signal assumption model ① purely for expository efficiency; the spectral algorithms in this paper naturally generalize to rank-r spiked tensors of the form
X Xindi
(1) - Ar i=1
2,4 ... k.le + Zz
j E [k], in E [my]
(3)
where r 2 is the rank and {u,) ......??) decompositions are unique by Kruskal's theorem [18]. Where we estimate u/" by the first right
. c gn are orthonormal sets, j E [k]. Such tensor
singular vector of an appropriate matrix Mj. v/2) uf may be estimated by the subsequent right singular vectors, with analogous theoretical guarantees holding (that is, v/ is the right singular vector associated with the i-th largest singular value of M2).
We denote by @ both the tensor outer product and Kronecker product (the latter is simply a vectoriza- tion of the former); is clear from context which is meant. Let x, denote multiplication between tensor along the j-th axis and vector of conformable dimension. The notation a(nz) S b(xz)

---

means a(n1)= v Cb(n1) for a constant C' > 0 and all sufficiently large n1, and a(n1) x b(n1) means a(n.) x b(n1) S a(n)).
Finally, we introduce tensor slices. Let T E Raix-xme and fix l E [k). The set (Tip..th : o E i E [ny]} contains the slices of of order Slices satisfy T Ti..... E 0==4+1 R and have entries
Pe =T Th....
E {e 1,,
Kii Iny].
1.3 Spiked Matrix Model
The behavior of matricization-biin based algorithms fundamentally derives from spectral properties of the spiked matrix model,
,2 A U2,12 + ,2
i [m1], 22 E [m2].
(4)
This model is extensively studied in random matrix theory, particularly under proportional growth, where n and n2 are of comparable magnitude:
11 12 00.
7 > 0.
T02
Under proportional growth, the sample covariance matrix XX1 /nz does not converge to the identity (its expectation), and the leading left and right singular vectors in and i2 of X are inconsistent estimators of e1 and 122 respectively. We highlight the following results of Benaych- Rao Nadakuditi [7], who establish formulas for the limiting misalignment of ú1 and iz:
and
Lemma 1.1. Let ú1 and 82 denote the leading left and right singular vectors of X. respectively, and define
+
T 2/14
(T,,))
7²(2 +7)
0
7 $ 7 1/4
Under x = (1+ where T 2 0 is fixed, and Yn, 7 (0, 1].
Kui, 01}1? a.s, (T,7),
K22,02)) a.a. (17-
(5)
Recently, Ben Arous al. [5] and Feldman [13] independently studied the spiked matrix model under disproportional growth, where 7/, -> 0 or Ym, - co. Transposing X in case Yn, - we assume without loss of generality that Yn, - O. Phase transitions for the left and right singular vectors no longer coincide; U1 is reliably estimated at signal strengths much weaker than X Z /nz.. Drawing upon results in [5], [13], and [7], we have the following disproportionate analogs Lemmaa..]
Lemma 1.2. Let 0j and 02 denote the leading left and right singular vectors of X, respectively, and define
72
(1-)=(1-7
t²(T) 1 + 72
Under A T(1 ((1)))(n))) where + 2 0 is fixed, and Ynn - 0.
1(v1, 01)1 e (T))),
(12, 02)1 2. 0,
(6)
while under x 7(1 + o(1))
(11, 0z)12 0.s.
Kuz, 02)12 ail d²(())
(7)
Limits 7 are corollaries of Theorems 2.9 and 2.10 [7]. We note that [5] requires na is polynomially bounded n This assumption, however, is necessary only to establish non-asymptotic bounds; the almost-sure results Lemma 1.2 hold as 7n, + 0 arbitrarily rapidly. While not explicitly stated in these references, it easily verified that under proportional growth, lim inf X/ A//ng > 7 1/1 implies partial recovery of and v2. Analogous statements hold for disproportional growth.

---

2
Tensor Unfolding
We study a general unfolding procedure that permits (1) tensors of general, unequal axis lengths and (2) unfolding along arbitrary sets of axes.
Let N TT ne, j E [k], and for S C. [k], S * 0, let N(S) = ITees ne. We define a map R X
Mats
R (M) as follows: for indices i, [myllj [k].
a Σ 11
II ne,
b=1+
Σ
(is
n1
(8)
jE(N)(S
JES
RES:jCE
and
Mats(T)la. Tanda....
(9)
When unfolding along single axis, write Mat, Mat In this case, ( reduces to
& Σ
Not1 n2
== 1+ lie
Σ
+
- 1)N++
(10)
ビ=j+1
(taking Mk+1 1) and ig. The unfolded matrix Mat, (X) a spiked matrix with aspect ratio n2/N::
Mxtx = X(u2 @ 1 vj-1 2 1/+1 @
2 m.) + (Z),
Similarly, Mats(X) is spiked matrix with aspect ratio N(S)²/N1:
(X) se,
+ Mats(Z).
(11)
We now review prior results on unfolding. For Un unfolding S = {l...., [kl...,,k/2]]] [k/2]], estimating @ 14/21y by the first right singular vector of Mats(X). They prove that [k/22 01 is (partially) recovered for X 2 n1
Uk. Montanari and Richard consider the
[k/21/2 and conjecture sufficiency of
A x ni (note that these bounds differ only for odd k)) Theorem 5.8 of Hopkins et al. [15] completes this conjecture for 3, establishing sufficiency of (1 [1++)) ()+m)m] 3/4
Complete analysis of unfolding handdinnnn tensors of arbitrary order and asymmetric dimensions
relies results in Section 1.3 which reveal (1) necessary and sufficient thresholds for recovery and (2) the exact limiting performance of estimates. In addition, spiked matrix results yield the exact limiting cosine similarity of unfolding procedures, not obtained in [20] [15]. The recent disproportional results summarized in Lemma 1.2 are crucial as unfoldings such as Mat, (X), J E [A - 1]. have limiting aspect ratio zero (recall that n1 S.... < n&)). Depending on the relative growth rates of flg, unfoldings such as Matx(X) may fall under disproportional "tall" growth (ng/N1 - 0), proportional growth ( x 1), or disproportional "wide" growth (n./Nr - oc). Our analysis is similar that of Ben Arous al. [5], which permits arbitrary order k yet assumes n1
nlg-
Theorem 2.1. Let S c [k]. NS) /N, O, the first right singular vector of the unfolding (Xts(X) partially recovers &jest; if and only if lim inf X/N T(1 + ([]))N] with + 2 fixed
In particular, for
[00 w){? -ie (7)))
(12)
NNN(S) x Sess is partially recovered if and only ifli inf X/N1/1 > For Yan and > = 7(1 (
-> ?
(0 w) ane, (1T)
(13)
Finally, if (NN + oo, @jesty is partially recovered if and only if lim inf X/ (N(S) 0. For 7(1 + o(1) /N(S).
18)es w)l2 an, c2(r).
(14)

---

All proofs are deferred to the supplement. As the recovery threshold is identical across all unfoldings such that ((5))/ /N1 2 1, we propose the following simple algorithm to estimate Fj, which may be iterated for j E [A:]
Algorithm 1 Tensor unfolding
Input: X.j
return first right singular vector of Mat (X)
Corollary 2.1.1. Algorithm partially recovers Vi....,0K UK-1 if and only if lim inf A/N > 1. Vector Uk. corresponding to the largest dimension, is partially recovered as well n NN X 1. On the other hand, if n NN - co, Uk recovered if and only lim inf A/ ng > 0.
Tonsor unfoldiing
1.0
400
cosine similarity [(rg bN
24
((F)
0.4
0.22
01.1
0.6
0.8
1.2
1.1
1.0
1.8
2.0
signal strongth A/11
Figure Simulations of tensor unfolding with k: 3, supersymmetric signal 01 = 122 v3 and M1 E {400, 800, 1200}. Solid lines display empirical cosine similarities (each point is the average of 50 realizations). The dashed line the theoretical limit Z(T). which agrees closely. Below the phase transition located at r = 1, ê1 is approximately uniformly distributed the surface of the unit sphere, so [11, 01)1 = (n -1/3..
Tensor unfolding, (m) ns) (50, 50, 10000)
Tensor unfolding, (R), (g. (30, 50, 20000)
cosine similarity [[,, 8)]
Ke,, 8:]
18 Pall
E8ta, Ag]
2(A/N)
OD Vey, N.f1g)
50
100 1301
200
250
50
100
150
200
250
signal strength
signal strength
Figure 2: Simulations of tensor unfolding with = 3, ni = 50, and ni = 10000 (left) or ni 20000 (right). Solid lines display empirical cosine similarities (each point is the average of 50 realizations). The dashed lines are theoretical limits based on Theorem 2.1] which agree closely. As na/ (n//n)ng) O(1), compare ((1,, 0z)1 and (u2, 02)1 c(T) and Kes, 03)l to (NT(Ni/ Ni 1/nn) c(>/ /na, N/ng))
3 Partial Tracing
Hopkins al. [16] propose the partial tracing method for tensors of order A: as an alternative to unfolding. Their approach generalizes to orders & > 3. although it inherently relies supersymmetry

---

of the signal, =... The partial tracing operator Tra 8 H R=x" constructs matrix by linearly combining tensor slices with partial trace weights:
(T) = Σ
(T
(15)
This operation of reducing the order of tensor by linear combinations of slices is called contraction in tensor analysis.
Algorithm 2 Partial tracing
Input: X
return first right singular vector of (Xx
is O(n"), while that of unfolding is O( log (see Table of [16]). Hopkins et al. established bound on the recovery threshold of partial tracing which is worse than that of unfolding by a logarithmic factor: À 3/4 (logg)// 1/2, We eliminate the logarithmic factor here: while delivering improvements runtime, Algorithm Dis asymptotically equivalent to unfolding in recovery performance.
For 3, the runtime of Algorithm 2
Theorem 3.1. The first right singular vector é1 of the partial trace matrix (r&(X) partially recovers k/1 en if and only if lim inf X/n 1. For 7(1 o(1))n k/1 where is fixed,
Kel. 0,)1 0n c (T).
(16)
Under n1 ng, the behavior of unfolding is given by 12), matching |6 exactly. Thus, unfolding and partial tracing are asymptotically equivalent in performance.
Partial tracing
81
400
800
cosine similarity [(ta
0.8
(1 1200
a(r)
0.6
0.4
0.6
0.8
1.0
1.2
1.6
signal strength A/n
8/4
Figure 3: Simulations of partial tracing with k 3, supersymmetric signal 01 = U2 U3. and п1 E {400, 800, 12003. Solid lines display empirical cosine similarities (each point is the average of 50 realizations). The dashed line is the theoretical limit c(T), which agrees closely. Note the similarity to Figure])
Exact Recovery
Montanari and Richard [20] consider a two-step recursive unfolding procedure that remarkably exactly recovers U1 above the threshold of unfolding, assuming even order k, hypereubical shape M1 = 7kg, and a supersymmetric signal, ei
Uk- In this section, we prove that exact recovery is possible for tensors of arbitrary axis lengths. We consider generalizations of the power iteration and recursive unfolding algorithms of [20] (initialized via tensor unfolding). Tensor power iteration is previously studied in [17] (assuming supersymmetric signal) and [21] (assuming

---

M1 2 x..x n4), though these works assume the initial iterate is independent of X, precluding initialization via unfolding.
In our more general setting, we find that unfolding-initialine power iteration achieves exact recovery above the partial recovery threshold of unfolding, established in Corollary 2. (assuming n / 0). Recursive unfolding exactly recovers U1...., U with no limitation on the growth rate of na-- Power iteration, which requires initial "warm" estimates of ......y Uk. may fail when ni and Ni comparable. Recursive unfolding, on the other hand, does not rely upon an initial estimate of up to
recover 11, .....U Uk- exactly.
Algorithm 3 Power iteration
Input: X, initial estimates 01,..., 0y from Algorithm Iterate until convergence:
for j from 1 to k:
"j - X X1 01 ... x,-1 0- X,+1 0341 .. X 0g
Úg w// ||0 l2
end for return 01 Ug,...,0 0%
We prove that exact recovery achieved in single iteration of the outer loop. practice, iterating until estimates converge is beneficial.
Theorem 4.1. lim inf A/N > and ng/N1 - O, Algorithm recovers .k exactly: denoting by .1....,
, 0g the estimates after single iteration of the outer loop.
1,
jE [A]]
(17)
Estimating the signal strength X by Å (X, é1 @ ... 0n), have
-- @ @ t Auz @ @ Uk I|
0.
(18)
We next consider recursive unfolding procedure. As stated above, recursive unfolding is guaranteed
to recover U1,.... Uk-1 exactly lim inf A/N1// > 1; no bound needed on the growth rate of ng
in Theorem 4.1 In practice, it is beneficial to iterate Algorithm
Algorithm 4 Recursive unfolding
Input: X, initial estimates 01,..., Og from Algorithm 1
for j from 2 to i;
0, f- first right singular vector of Mat-- X1 61)
end for
i1 first right singular vector of Mat, (X X2 02)
return ug
Theorem 4.2. Under lim inf A/N 1, Algorithm recovers Ui..... Uk-1 exactly. Moreover, Uk is recovered exactly if n $ 1.
The analysis of Algorithm Aegorithmeentaaii entails careful application of spiked matrix model results. By the linearity of the unfolding operator,
Mat, - (X x 0,) Aee, @i)(BeewW))))))a))) + Mat; IZ 61).
(19)
Observe that Z x1 ig is reshaping of the vector Mat, (Z) As ên and Z are dependent, the second term on the right-hand side not a matrix of i.i.d. entries. Despite dependencies, we claim that appropriately scaled, Mat, ( is distributed as Gaussian noise, which case exact recovery thresholds are a consequence of spiked matrix model results of Section 1.3 applied to (19).
Below, display simulation results for power iteration and recursive unfolding and compare to tensor unfolding and partial tracing.
7

---

Power iteration
1.-
==
m=800
0.8
n=1200
1(7 2 1)
cusiue similarily
0.5
0.2
0.4
0.0
10
1.2
1.0
1.6
1.8
2.0
signal strength A/Ri
Figure 4: Simulations of power iteration with k = 3. supersymmetric signal ei 02 U3. and #1 E {400, 800, 12003. Solid lines display empirical cosine similarities (each point the average of 50 realizations). The dashed line is the theoretical prediction 1(T >> 1). Power iteration typically converges within five iterations.
Power iteration, (s).. (50,50, 10000)
Power iteration, (R,,R,, Rill 20000)
cosine smilarrty [(c00)
0.8
0.5
0.0-
0.5
0.4
10 Rea. Fall
[ts.
[ty, Rg)
[eg. Fy3l
3.0
50
250
signal strength
signal strength
Figure 5: Simulations of power iteration with 1: 77 n2 50, and ns 10000 (left) n3 = 20000 (right). Solid lines display empirical cosine similarities (each point the average of 50 realizations). Vector v3, corresponding the longest tensor axis, is estimated less well than v1 022-
Comparison algorithms, 1200
unfolding
onsine similarity ((9,6)) 6y)l
portial tracing
power iteration
[[r]
0.6
01.
0.4
0.6
2.00
1.5
2.0
signal strength
A/m
Figure 6: Simulations of unfolding, partial tracing, and power iteration with k 3, supersymmetric signal U2 = U3. and nı 1200. Solid lines display empirical cosine similarities (each point the average of 50 realizations). The dashed line is the theoretical limit of unfolding and partial tracing, Z(T). Near the phase transition located at over twice that of unfolding.
1, the cosine similarity of power iteration is

---

Recursive unfoldinng (Nu.Pg.. 150.50, 10000)
Recursive unfolding, (R), (50.50) 500,0,,0000
1.0
Keg,
cocine smillarity [ 01)
K5%, Bal
0.4
0.44
R0, vil
0.2
0.2
1r fill
Res, fall
0.0
100 150
2001
200
50
100
150
200
250
signal strength
signal strength
Figure 7: Simulations of recursive unfolding with k 3, f2 50, and 10000 (left) or n3 = 50000 (right). Solid lines display empirical cosine similarities (each point the average of 50 realizations). The performance of recursive unfolding is quite similar to that of power iteration.
References
[1] A. Anandkumar, R. Ge, D. Hsu, and S. M. Kakade. Tensor Approach to Learning Mixed Membership Community Models. Journal of Machine Learning Research, 1:2239-2312. 2014.
[2] A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky. Tensor Decompositions for Learning Latent Variable Models. Journal of Machine Learning Research, 15:2773-2832, 2014.
[3] M. Bayati and A. Montanari. The dynamics of message passing dense graphs, with applications compressed sensing. IEEE Transactions on Information Theory, 57(2):764 785, 2011.
[4] Ben Arous, Gheissari, and A. Jagannath. Algorithmic thresholds for tensor PCA. Annals Probability, 28(4):2052-200 2087, 2020.
[5]G. Ben Arous, D. Z. Huang, and J. Huang. Long Random Matrices and Tensor Unfolding. arXiv preprint 1eXiv2110.1022 2021.
[6] G. Ben Arous, S. Mei, A. Montanari, and M. Nica. The landscape of the spiked tensor model. Communica- fions on Pure and Applied Mathematics, 72:2282-2330, 2019.
[7] F. Semaych-Georger and R. R. Nadakuditi. The singular values and vectors of low rank perturhations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120- 11::120-335 2012.
[8] A. R. Benson. D. E. Gleich, and J. Leskovec. Tensor spectral clustering for partitioning higher-order network structures. Proceedings of the 2015 SIAM International Conference on Data Mining, 118-126, 2015.
[9] X. Bi, Tang, Yuan, Zhang, Qu. Tensors Statistics. Annual Review of Statistics and Its Application, 8:345-368, 2021.
[10] A. Bloemendal, L. Erdos, A. Knowles, H. T. Yau, and Yin. Isotropic local laws for sample covariance and generalized Wigner matrices. Electronic Journal of Probability, 19(33):1-53 2014.
[11] B. B. Chen and G. M. Pan. Convergence of the largest cigenvalue of normalized sample covariance matrices when p and both tend to infinity with their ratio converging to Bernoulli, 18(4): 1ett-14014200 2012.
[12] L. De Lathauwer, B. De Moor, and J. Vandewalle. A Multilincar Singular Value Decomposition. SIAM Journal Matrix Analysis and Applications, 21(4):1253-1277 2000.
[13] M. J. Feldman. Spiked Singular Values and Vectors under Extreme Aspect Ratios. Journal of Multivariate Analysis, 196:105187. 2023.
[14] Hillar
Lim. Most tensor problems are NP-hard. Journal of the ACM, 60(6))1-39, 2013.
[15] B. Hopkins, J. Shi, D. Steurer. Tensor principal component analysis via sum-of-square proofs. Conference on Learning Theory, 956-9006 1006, 2015.
[16] S. B. Hopkins, T. Schramm, Shi, and D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Proceedings of the 48th Annual ACM SIGACT Symposium on Theory Computing, 178 191, 2016.

---

[17] J. Huang. D. Z. Huang, Q. Yang. and G. Cheng. Power Iteration for Tensor PCA. Journl of Machine Learning Research, 23:1-47, 2022.
[18] J. B. Kruskal, Three-way arrass: rank and uniqueness of trilinear decompositions, with application arithmetic complexity and statistics, Linear Algebra and Applications 18(2):95- 138, 1977.
[19] Lu, N. Plataniotis, and A. N. Venetsanopoulos. survey multilincar subspace learning for tensor data, Pattem Recognition, (4(7):1540-155) 2011.
[20] A. Montanari and E. Richard. A statistical model for tensor PCA. Proceedings of the 27th International Conference on Neural Information Processing Systems, 2:2897-2900 2905, 2014.
[. E. A. Seddik, M. Guillaud, and R. Couillet. When random tensors meet random matrices. arXiv preprint arXiv:2112.12345 2021.
[22] N. D. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E, E. Papalexakis, and C. Faloutsos. Ten- Decomposition for Signal Processing and Machine Learning. IEEE Transactions Signal Processing, 65(13)33551-3588 2017.
[23] Tomioka and Suzuki, Spectral norm of random tensors, 2014. arXiv:1407.1870.
[24] Wainwright. High-Dimeen Dimensional Statistics. Cambridge. 2019.
[25] Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis-Kahan theorem for statisticians. Biometrika, 102:315-323, 2015.
Appendix
proof of Theorem 2.7 By 11 Mats(X) ) is a spiked matrix with aspect ratio (S)) and signal strength Ả (as @jesty is unit norm). There are four cases to consider:
Let N 0; by the first point of (6), the recovery threshold lies at (N/N((S) N(S))144 = N//4
Let N(8)3/N1 + (0, 1]: by the first point of ( partial recovery occurs for liminf A/ NI/N(S) > 71/1. Equivalently, lim inf A/N 1. Under À = r(1 +
o/1))N// lim /N, (N)() T///44 implying (8jEs w){? a.x,, (4ry
Let / + (1): by the second point of 5p. partial recovery occurs for lim inf /N() > 7-1/4 Equivalently, lim inf A/N > 1. Under =
T(1 + o lim A/ /N(S)= = 1111
1/4, implying (O)est) w)| od, o 11/4-1/4
- 1/,,)
Let + oo; by the second point of 7 the recovery threshold lies at VN(S).
Proof of Theorem 3./ We provide proof for 1: 3; the proof for higher orders is similar and omitted. For notational simplicity, we suppress the subscripts of n1 and e1.
Let w; = ir(2.), i [n]. and
T..TT Expanding the partial trace matrix,
Tra (X) =
Σ (Av + w; Σ 1222 + >xxws)ooT T + (Au; + w:)
i=1
[AA233 Aoawa)ou T + (Au; + wi) diag(Z, -Z:)) (Ae) + w. w;)diag(Z,
-2))
(20)
where Z is independent copy of Z.
10

---

w (A=r + w2; diag( Z, -()). As and Z; diag(Z, Zi - 2,) are independent and the Gaussian distribution is rotationally invariant, M - Z1. Hence, we have
Let M = - +
(Au; + ue ddiag Z: - Z,), (21) a + 11 TTr = avvv' + M + || + wllg" E
where a = [/ _|| (A² + X(v, w)). The partial trace matrix is thus proportional to perturbation of spiked matrix with aspect ratio y 1.
Let & denote the third term on the right-hand side of (21 ; we shall prove 1/ وقك Denoting u = (Au+ / Au the diagonal entries of > i= (,diag(Z;) are i.id. Gaussians with variance one, implying Di=1 u,diag(Zx) 222 S Vlogn, almost surely. Similarly, since (N0 nIn) and
||vv + w|l2 = a. (A + n))
|1 Σ di Zi)
X Vlog n [1+ n m
a/ + w
(22)
22
To bound the remaining term of E, let Z E R denote the matrix with entries Ziz Ziss. i E [n), in which case we may write
Σ
w,diag Zi) 112
sup 15
wi Zijj
sup 15j5n
le
2T,22 ~1,1,
(23)
1=1
1=1
where 1, is the length-n vector of ones. As e] 1 Ze, ~
Xn and
e, z1, eg) _ -n- - 1e] 2 Ze, Vn-1-NNO. Vx
standard bounds such as (2.19) in [24] yield
P
sup isján
[e] 21, - n > cc S ne-Co Cn
(24)
where c, C' >> 0 are constants. As the right-hand side is summable, the
lemma implies
sup 1stsn
le, 2 21 S n,
(25)
almost surely. Collecting the above bounds, have that 1/2 1/21|81|2 0.3 O.
By Weyl's inequality, the limiting spectral distribution of 1/ E) equals that of n 1/2 M,
the quarter circle law. The limits (5) from Lemma 1.1 therefore apply to ovv +M + & well
(see [7]). Basic calculations yield (1) lim inf a/ u//n / > 1 if and only if lim inf A/n > 1, and (2)
under À = 7(1 + m//4 a = 72(1 + ou.s. (e.).(1) (1)) Therefore, á partially recovers v if and only if inf 3/1334 > 1. and under À = 7(1 (1=0(1))n384
Kv, a.e. (7)
(26)
completing the proof.
Proof of Theorem
4.7
By the linearity of the operators X1,..., XX:
wy =
II eE(R]VE/
(ve, - + xx x1 01 X,-1 03-1 XJ+1 0/+1 X du.
(27)
(0z, wy) = A
II (E(RM
(ve, 02) + (2, 2 1 0541 @ 0k).
(28)
Assume that (17) holds for f E [j - 1]. For & E {j + 1,.......A bounded away from zero. The first term on the right- hand side of (28) is therefore (A). The second term is bounded by the spectral norm of Z: using Theorem of [23].
k). Corollary 2. implies Kug, 0z) is
[Z, 61 6 و vy 0z+1
6x) <
sup
(Z, un @ un) S Vnk. (29)
a, 1.- [j(

---

almost surely. Thus, as (vTi/A)* & /ng/N1 + +0
Ku,, 0y)l = 1 Ou.s.
V
0. 1,
(30)
from which 17 follows inductively.
Equation
18) follows from 17 and 29). which imply ||u1 -.... 2 - -0 2
&allF a.s. 0 and
|
II
Ju +2)+ (Z, @-. 0x)
a. 1.
(31)
recovered exactly; proofs for the first and last axes are similar and omitted. By the linearity of the unfolding operator,
Proof of Theorrm 4.2 We shall prove 02,-.., My
x1 i1) X(e, 61) (B + Mat, (Z x1 01)
(32)
Observe that Z x1 61 is reshaping of the vector Mat (Z) As 01 and Z are dependent, the second term on the right-hand side is not a matrix of i.i.d. entries. Despite dependencies, we claim that appropriately scaled, Mat, (Z)û1 is Gaussian noise, in which case exact recovery thresholds are consequence of spiked matrix model results of Section 1.3 applied to (32)
By definition, 01 is the first eigenvector of the symmetric matrix
Mat (X) Mat (X) Loroe + Mat (Z) Ma (Z) E
(33)
where & is rank-two matrix given by
E Aun (1 Mat, (Z) AMat, (
Let 0n denote the first eigenvector Mat, (X) Maty (X) - E; without loss of generality, we assume 87 01 2 0. Since Mat, (Z) ())))))()) ~ (V, 4n,). we have ||E||2 3 Ay'n almost surely. By
Theorem 1.1 of [13], the spectral gap of Mat (X) Mat, (X) is @(*²). Thus, using the Davis-Kahan
theorem (see Corollary 3 of [25]), have
|E112 a.e 0. X2
1 01112 -
(34)
Let Mat, (Z) UAV be a singular value decomposition. As contains i.i.d. Gaussian entries, (1) U. A, and V are independent, (2) U and V are Haar-distributed. Moreover, in is the first eigenvector of X2 r. + Mat, Mat, (Z) 22 VA²VT, 61 is independent of U. Thus, UAV /// 01 11112 is uniform on N2-1, Generating Xa, independent of follows that
Mat (Z)ū,
IN,)
(35)
N2
[A AVVT2112
Defining the constant E/( |V in l122, we deduce that aZ X 01 (which is reshaping of the left-hand side (35) is distributed as a tensor with i..d Gaussian entries despite dependencies between Z and 01 Additionally, since An An/VN2 a.s., 1 and Anyay //N2 a.9. 1, we have ||AVT &, 1/2//22 a.s. and a.s. 1. Thus, conclude that
(X x ū1) X(1 + Oa.s. (1)).11)) ( (i +Z, jE (2, 1}. (36)
where Z E x contains i.i.d. Gaussian entries, enabling to apply spiked matrix results.
Let öy denote the first right singular vector of - x ū1) (cquivalently, that of aMaty-1 x úi )); without loss of generality, we assume 0. 5₁ 2 O. In particular, since (ei, 6i)l x Kei,61)| 1
by Corollary 2.1.1 and (34). Lemma 1.2 implies (ey, أ,)o a.s. (we have À > (ny N2/n,)1/2)
12

---

It therefore suffices to prove that | 8g l2 وقك 0. By Theorem 2.3 of [5] or Theorem 1.1 of [13] and Cauchy's ss interlacing inequality, the spectral gap of 1 1 X1 ū1) MMat,-1XX 1 x 8g is (A²). Let Z denote the reshaping of Z with dimensions n x n2 x N2/nj and slices Mat i E [mi]. Using the bound
| X1 (01 01))112
sup #1E3"1 M2E8" W3E8"2/nj-1
(Z x1 U1 X2 U2 X3 Uz) 100 01 ll2
and Theorem 1 of [23],
| X1 (01 - 01))ll2 E 21 - .... ...88p ux)ll2 + | x1 (01 - 01))
S (A (Na/ny) 11
(37)
almost surely. Thus, using the Davis-Kahan theorem (Theorem 4 of [25]). (34 and (37). have
A(*+ + (N2/n,)
ll2 0,
| - u5l12
(38)
X2
completing the proof.
13


Reviews:
[{"review_id": "1aUmtFciDN", "reviewer": "Reviewer_K1MF", "summary": "This paper studies tensor principal component analysis (PCA) in a high-dimensional asymptotic framework, where each array dimension tends to infinity. The authors analyze matricization-based approaches, which convert tensors to matrices and then apply spectral methods. They fully analyze tensor unfolding or reshaping and the partial trace approach, discovering their asymptotic equivalence in performance. They identify sharp thresholds in signal-to-noise ratio above which these algorithms partially recover the signal and provide exact formulas for their limiting performance. Finally, they introduce an iterative algorithm based on successive contractions of the tensor, which achieves exact signal recovery above the same thresholds characterizing partial recovery of unfolding and partial trace. The authors' approach relies on fundamental random matrix theory results.", "questions": "Please refer to the weaknesses.", "limitations": "The main limitations of the paper are:\n1. The paper considers an asymptotic analysis for Tensor PCA assuming the dimension of the tensor to grow to infinity, while a non-asymptotic analysis or rather a quantification of the fluctuations would be interesting to investigate.\n2. Most of the presented results in the paper are relatively known in the literature (Tensor Unfolding and Partial Trace).\n3. Lack of comparison of the presented successive contraction method with the tensor power iteration algorithm.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The main strengths of the paper are:\n1. The paper provides a comprehensive analysis of tensor PCA algorithms in a high-dimensional asymptotic framework, allowing for tensors of diverse dimensions and unrelated signals.\n2. The paper introduces an iterative algorithm based on successive contractions of the tensor, which achieves exact signal recovery above the best-known algorithmic threshold.\n3. The paper provides exact formulas for the limiting performance of the algorithms and identifies sharp thresholds in the signal-to-noise ratio above which these algorithms partially recover the signal.", "weaknesses": "The main weaknesses of the paper are:\n1. The presented successive contraction is demonstrated to achieve exact recovery only asymptotically, while a non-asymptotic result would be more interesting to investigate. In fact, the authors should compare the obtained performance of the successive contraction method in a non-asymptotic regime with the MLE which was analyzed in [1].\n2. It is unclear how the successive contraction method differs from the tensor power iteration. In fact, [2] showed that the latter achieves also exact recovery above the algorithmic threshold when initialized with signal estimates using the tensor unfolding method.\n\n[1] Mohamed El Amine Seddik, Maxime Guillaud, and Romain Couillet. “When Random Tensors meet Random Matrices”. In: arXiv preprint arXiv:2112.12348 (2021)\n\n[2] Arnab Auddy and Ming Yuan. “On Estimating Rank-One Spiked Tensors in the Presence of Heavy Tailed Errors”. In: arXiv preprint arXiv:2107.09660 (2021)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}, {"review_id": "s0mncxUwYo", "reviewer": "Reviewer_PnQP", "summary": "This paper is concerned of the tensor PCA problem (low-rank tensor recovery with Gaussian noise), in which the authors proposed three new ways to approach the problem with theoretical guarantees.\n\n", "questions": "N/A", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper uses a succinct way to introduce to readers 3 different approaches of tensor PCA, all with formal guarantees. Therefore, a reader can quickly identify the approach they personally need.\n\n2. All of the results are based on well-established matrix PCA results, so it is easier for readers to understand, and also gives people stronger confidence to use, as tensor analysis is notoriously hard.", "weaknesses": "1. Although the results themselves are fine, and solid to my eyes, but none of them provide new insights to the problem, nor did the authors come up with new or innovative techniques. It just seems to me that all this paper is doing is adapting a few matrix PCA techniques to the tensor regime, and only perform minimal changes to the procedure so that the framework can be used. This does not mean the results themselves are inferior, but the merit this paper brings is very limited beyond the verbatim theorems.\n\n2. The paper presented three different approaches, but did not compare/contrast the three, so unfamiliar readers may not know which is the best technique to apply.\n\n3. The simulation is limited (however, this is mostly a theoretical paper, so acceptable).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review of our manuscript. Tensor unfolding and partial trace, we discover, are asymptotically equivalent in performance. Successive contraction is shown in Section 4 to achieve exact recovery above the common threshold of tensor unfolding/partial trace, and we recommend it be used in practice. The benefits of successive contraction over tensor unfolding/partial trace in simulations is shown in Figure 2. We have conducted additional simulations in the case where $n_1 = n_2 \\ll n_3$; please see the plots attached to our response."}, {"review_id": "HlNNkM0NiM", "reviewer": "Reviewer_mafC", "summary": "This paper studies recovery of planted signals from noisy tensors. \nThe model is the prototypical tensor PCA and the emphasis is that (i) the planted low rank tensors (in particular their dimensions) can be different along different modes; (ii) the joint scaling of different dimensions can deviate from the classical proportional regime. \nThe paper studies a few old and new natural algorithms and obtain sharp performance guarantees (specifically the overlap) for almost all of them. ", "questions": "1. In equation (1.3), should (r) in the superscript be (i)?\n\n2. Line 58 'Where we estimate v_j^{(1)} by the first right singular vector...'. Here by 'first', I suppose lambda1 >= lambda2 >= ... is assumed. Am I right?\n\n3. The set {v_j(k)} is assumed to be orthonormal. How strong is this assumption? It seems a bit more realistic to assume v_j^{(k)}'s are in general position. Also, my impression is that this will create quite some technical challenges. Correct me if I'm wrong. \n\n3. Some theorem/lemma statements are not sufficiently clear. E.g., Theorem 2.1, line 120, 122, does 'recovered' still refer to partial recovery as in line 118? I suggest state it more formally, at least in the theorem statement. Please check thoroughly for similar issues. \n\n4. Lemma 3.2 is the standard Gaussian conditioning lemma. It'll be nice to put a reference there. The standard one might be Lemma 11 of Bayati--Montanari (https://arxiv.org/abs/1001.3448), though there might be better ones. Please check the literature. \n\n5. Proof of Theorem 3.1, I feel it's actually better to do the proof for general k instead of k=3, maybe in the full version of the paper if the authors wish. \n\n6. The successive contraction algorithm is indeed quite natural. It reminds me of something called decimation AMP studied here https://arxiv.org/abs/2306.01412. That's in the context of *high*-rank matrix estimation (using AMP, but never mind that) and it estimates each component of the planted matrix sequentially and subtract it out for the next one. \n\n7. I'm not sure if the authors are aware of the following line of work that analyzes MLE (which is computationally expensive) for tensor PCA using a novel technique. The results are not completely new since MLE has been well-understood and moreover their results require the assumption that the limit of overlap exists. However, their techniques involves standard RMT and seem conceptually more accessible. The authors may want to look into or even consider citing some of them. \n- https://arxiv.org/abs/2108.00774 (square case)\n- https://arxiv.org/abs/2112.12348 (rectangular case)\n- and related works by roughly the same authors\n- https://arxiv.org/abs/2110.01652 (spectra of contracted tensors)\n\n\nMinor things:\n- I found it slightly weird that the citations are in the format (1), (2), etc. Note that the same format is also used for bullet points (see line 95, 110). Very similar notation is also used for equation numbers (1.1), (1.2). To avoid confusion, I suggest use the more standard [1], [2] or [ABC20], [XYZ99] format for citation. \n\n- Sometimes the first letter of 'proof of Theorem XXX' is not capitalized. \n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Both the techniques and the results of this paper are neat. \nIt properly combines recent (and some not-so-recent) results in random matrix theory (RMT) and high-dimensional statistics and extend them to a satisfactory extent. \nOnce some prior results are properly organized, the proofs of the present results become rather straightforward. \nBut for ICML, I think this is enough. \nAlso, I thought about a subset of the questions studied in this paper before (perhaps before some of the recent RMT results were available) and at that time it was not clear how these results can be proved. ", "weaknesses": "One important aspect of tensor PCA that the authors seem to ignore by large is the potential existence of information-computation gap. \nThe authors may want to check papers of Sam Hopkins, David Steurer, Andrea Montanari, Guy Bresler, Alex Wein (listed in random order) and many others. \nThey provide evidence of average case hardness from the perspectives of SoS, low-degree polynomials, reduction, statistical query lower bounds, AMP, statistical physics, etc. \nI know the information-theoretic aspect and the info-comp gap is not the focus of this paper. \nBut when it comes to such a prototypical problem of tensor PCA, it's always good to say a few words about it so that the present results are properly positioned in the literature. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed comments and questions! We are familiar with the information-computation gap for tensor PCA and agree with your suggestion that is should be mentioned in the introduction. Here are point-by-point replies:\n\n1.\tYes, that is a typo.\n\n2.\tYes, we will add a clarification.\n\n3.\tIt is not an inconsequential assumption, although it is a generalization to most of the tensor PCA literature which assumes r=1. “Low rank” does not generalize from matrices to tensors as nicely. For example, tensor rank is often defined to be the minimal $r$ such that $T = \\sum_{j=1}^r v_1^{(j)} \\otimes \\cdots \\otimes v_k^{(j)}$, where $\\{v_1^{(j)}, \\ldots v_k^{(j)}\\}$ are not necessarily orthogonal. A tensor that is low-rank under this definition may not have a decomposition into an equal number of terms with orthogonal vectors (this decomposition does always exist in the matrix case $k=2$). \n\n4.\tYes, this is partial recovery. We will clarify this. \n\n5.\tYes, this is standard. Thank you for the suggested reference, we have added it.\n\n6.\tWe elected to write out the proof for $k=3$ for sake of simplicity, the general proof is nearly identical, although sums such as (3.2) become $k$ sums over each tensor axis.\n\n"}, {"review_id": "1lIZoARtMN", "reviewer": "Reviewer_tdbZ", "summary": "This paper considers the (Gaussian, nonsymmetric, rank-1) spiked tensor model introduced in Montanari and Richard.  It gives sharp thresholds for various matricization techniques (unfolding, partial traces, successive contraction).  The statements about random tensors are reduced to known results about left and right singular vectors of spiked non-symmetric random matrices.  The proofs of the new statements are a few lines long.  Some numerical results back up the performance statement about successive contraction.\n\n\n\n\n", "questions": "No questions.", "limitations": "See above.", "rating": 3, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 1, "strengths": "The presentation is generally clear and concise.  The proofs seem reasonably detailed given the content matter.  Some of the results appear novel and improve over substantially longer published work.  Highlights include\n1) Improving an analysis in Hopkins et al.\n2) Generalizing the successive contraction method of Montanari and Richard with excellent performance properties. ", "weaknesses": "The new theoretical content in this paper is very slight: the random matrix theory of spiked Gaussian matrices is extremely well-developed. Once it is noticed that the unfolded tensors satisfy the hypotheses of these theorems, the proof is immediate.\n\nThere is no further elaboration beyond this:\n1) the paper does not show how this fits into a larger picture of non-random-matrix-theory approaches.\n2) the paper does not attempt to expand interesting unexplored aspects which don't follow from textbook random matrix theory (the best hint of this are the numerics that appear for tau=1 at the end).\n3) the new technique (in the abstract \"Finally, we introduce an iterative algorithm based on successive contractions of the tensor\") is rather a generalization of a technique of Montanari and Richard.  The analysis given is in the phase of perfect recovery, exploiting some of the specific structure of the spiked model.\n\nThis is a reasonable topic for a purely theoretical NeurIPS contribution, but there is not enough new material here to warrant publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:
We thank the reviewers for the time and effort they have invested into the review of our manuscript, and for their helpful comments and suggestions. We would like to address the reviewers’ main criticism, that our results follow easily from PCA results of random matrix theory (RMT). The primary purpose of this work is to exhibit spiked matrix results (those of [2] as well as newer results of [1] and [3]) and demonstrate how they can be applied to machine learning problems. While well-known within RMT and to the reviewers, the machine learning community is less familiar (in our opinion) with this literature. There are numerous potential applications of this theory to machine learning, many of which we believe are underexplored. As machine learning problems often concern the setting where dimensions exceed sample size, the recent results of [1] and [3] (which generalize previous “proportional” results of [2] to the “disproportional” setting) may be particularly useful.

Our work concisely demonstrates the advantages of this RMT-backed approach in the context of tensor PCA. Indeed, application of spiked matrix results yields simple and elegant theorems which may be easily read by theoreticians as well as practitioners. For example, analysis of the partial trace method, originally done by challenging matrix concentration and perturbation calculations, is reduced to a few careful lines. Though our results are admittedly purely asymptotic, there are no hidden constants or logarithmic factors as in [4] (which frequently give practitioners pause). Even for modest-sized tensors, our simulations demonstrate close agreement with theory.
 Moreover, this approach reveals the asymptotic exact equivalence in performance of tensor unfolding and partial trace. To the best of our knowledge, we are the first to make this discovery. Our paper makes clear that for a number of (seemingly different) algorithms, performance fundamentally derives from spectral properties of spiked matrices. 

We agree that what we have called successive contraction is simply a generalization of the power iteration algorithm of [5] and ought to be called as such. While previous analysis in [6] is limited to the setting where $n_1 \asymp n_2 \asymp \cdots \asymp n_k$, we make no assumptions on the relative rates of growth of $n_1, n_2, \ldots, n_k$. We have conducted additional simulations where $n_1 = n_2 = 50$ and $n_3 = 10000$ or $n_3 = 20000$, again demonstrating agreement with theory. 
Please see the attached plots.

If accepted, we will clarify these questions in the revision. 


[1] G. Ben Arous, D. Huang, and J. Huang. Long Random Matrices and Tensor Unfolding. arXiv 208 preprint arXiv2110.1021, 2021.

[2] F. Benaych-Georges and R. Rao Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120–135, 2012.

[3] M. Feldman. Spiked Singular Values and Vectors under Extreme Aspect Ratios. Journal of Multivariate Analysis, 196, 2023.

 [4] S. Hopkins, T. Schramm, J. Shi, and D. Steurer. Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors. Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 178–191, 2016.

[5] A. Montanari and E. Richard. A statistical model for tensor PCA. Proceedings of the 27th International Conference on Neural Information Processing Systems, 2:2897–2905, 2014.

[6] M. E. A. Seddik, M. Guillaud, and R. Couillet. When random tensors meet random matrices. arXiv preprint arXiv:2112.12348, 2021.


Meta-review: The reviewers have conducted a detailed reading of the results and comparison with the existing literature. At least one of the reviewer, tdbZ, states they are an expert in the area. The overall conclusion is that the results of the manuscript are fine, but follow overly directly from the exiting literature. Specifically that the proofs are extremely simple and in effect follow from noting that the variant of the question satisfies conditions of theorem from which the new results then follow. That said, it is agreed that the result are worthy of publishing, especially with the more novel result on partial trace and exact recovery in sections 3 and 4. The reviewers also agree that the manuscript is generally well written. The only issue is if the manuscript is suitable for NeurIPS or if it should be in a journal setting; summarised as "too little for NeurIPS." The authors and reviewers have engaged productively.  The manuscript has substantial new contributions with the non-proportional setting.  The contributions are mathematically rigorous.  The only issue for debate is if the manuscript is sufficiently novel for NeurIPS; and for this question my view is that in total yes, the contributions are sufficient for publication at NeurIPS, though best suited for a poster.
Decision: Accept (poster)