A new framework for tensor PCA based on trace invariants
Authors: Mohamed Ouerfelli
mohamed Tamaazousti
Vincent Rivasseau
Venue:  (2021)
Keywords: Tensor
Principal Component Analysis
Tensor decomposition
trace invariant

Abstract: We consider the Principal Component Analysis (PCA) problem for tensors $T \in (\mathbb{R}^n)^{\otimes k}$ of large dimension $n$ and of arbitrary order $k\geq 3$. It consists in recovering a spike $v_0^{\otimes k}$ (related to a signal vector $v_0 \in \mathbb{R}^n$) corrupted by a Gaussian noise tensor $Z \in (\mathbb{R}^n)^{\otimes k}$ such that $T=\beta v_0^{\otimes k} + Z$ where $\beta$ is the signal-to-noise ratio. In this paper, we propose a new framework based on tools developed by the theoretical physics community to address this important problem. They consist in trace invariants of tensors built by judicious contractions (extension of matrix product) of the indices of the tensor $T$. Inspired by these tools, we introduce a new process that builds for each invariant a matrix whose top eigenvector is correlated to the signal for $\beta$ sufficiently large. Then, we give examples of classes of invariants for which we demonstrate that this correlation happens above the best algorithmic threshold ($\beta\geq n^{k/4}$) known so far. This method has many algorithmic advantages: (i) it provides a detection algorithm linear in time and that has only $O(1)$ memory requirements (ii) the algorithms are very suitable for parallel architectures and have a lot of potential of optimization given the simplicity of the mathematical tools involved (iii) experimental results show an improvement of the state of the art for the symmetric tensor PCA. Furthermore, this framework allows more general applications by being able to theoretically study the recovery of a spike in the form of $v_1 \otimes \dots \otimes v_k$ with different dimensions ($T \in \mathbb{R}^{n_1\times n_2\times \dots \times n_k}$ with $n_1,\dots, n_k \in \mathbb{N}$) as well as the recovery of a sum of different orthogonal spikes. We provide experimental results to these different cases that match well with our theoretical findings.

Under review as a conference paper at ICLR 2021
A NEW FRAMEWORK FOR TENSOR PCA BASED ON TRACE INVARIANTS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the Principal Component Analysis (PCA) problem for tensors E (IR))= of large dimension and of arbitrary order 3. It consists in recov- ering spike o (related signal vector to R² corrupted by Gaussian noise tensor Z (Rm)osk such that T fe & + where 3 is the signal-to-ne ratio. In this paper, we propose new framework based on tools developed by the theoretical physics community to address this important problem. They consist in trace invariants of tensors built by judicious contractions (extension of matrix product) of the indices the tensor T. Inspired by these tools, we introduce a process that builds for each invariant matrix whose top cigenvector is cor- related to the signal for / sufficiently large. Then, we give examples classes demonstrate that this correlation happens above the best algorithmic threshold (3 > //4) known so far. This method has many al- gorithmic advantages: (i) it provides detection algorithm linear in time and with only O(1) memory requirements (ii) the algorithms are very suitable for parallel architectures and have a lot of potential of optimization given the simplicity of the mathematical tools involved (iii) experimental results show improvement of the state of the art for the symmetric tensor PCA. We provide experimental results to these different cases that match well with our theoretical findings.
of invariants for which
INTRODUCTION
Powerful computers and acquisition devices have made it possible to capture and store real-world multidimensional data. For practical applications (Kolda & Bader (2009), analyzing and organizing these high dimensional arrays (formally called tensors) lead to the well known curse of dimension-
ality (Gao al. (2077) Suzuki (20T9). Thus, dimensionality reduction is frequently employed to transform a high fith-ddmmnsiionaa data set by projecting it into lower dimensional space while retaining most of the information and underlying structure. One of these techniques is Principal Component Analysis (PCA), which has made remarkable progress in large number of areas thanks to its sim- plicity and adaptability (Jollifee & Cadima (0166; (eddik et al. (2019)).
In the Tensor PCA, as introduced by Richard & Montanari (2014), we consider model where we attempt to detect and retrieve an unknown unit vector vh from noise-corrupted multi-linear measure- ments put in the form of a tensor T. Using the notations found below, our model consists in:
T =
@k + Z.
(1)
with Z a pure Gaussian noise tensor of order k and dimension n with identically independent dis- tributed (iid) standard Gaussian entries: i2..i..... (O, 1) and the signal-to-noise ratio.
To solve this important problem, many methods have been proposed. However, practical applica- tions require optimizable and parallelizable algorithms that are able to avoid the high computation- ally cost due to an unsatisfactory scalability of some of these methods. A summary of the time and space requirement of some existent methods can be found in Anandkumar et al. (2017).
One way to achieve this parallelizable algorithm is through methods based on tensor contractions (Kim et al. (2018) which are extensions of the matrix product. These last years, tools based on ten- sor contractions have been developed by theoretical physicists where random tensors have emerged generalization of random matrices. In this paper, investigate the algorithmic threshold of

---

Under review as a conference paper at ICLR 2021
tensor PCA and some of its variants using the theoretical physics approach and we show that it leads to new insights and knowledge in tensor PCA.
Tensor PCA and tensor decomposition (the recovery of multiple spikes) is motivated by the increas- ing number of problems in which it is crucial to exploit the tensorial structure (Sidiropoulos et al.
(017 ) Recently it was successfully used to address important problems in unsupervised learning
(learning latent variable models, in particular latent Dirichlet allocation Anannkkumr et al. (2014).
Anandkumar al. (2015). supervised learning (training of two-layer neural networks, Janzamin et al. (2015)) and reinforcement learning (Azizzadenesheli et al. (2016))
Related work Tensor PCA was introduced by RRiharrd & Montanari 2014) where the authors suggested and analyzed different methods to recover the signal vector like matrix unfolding and power iteration. Since then, various other methods were proposed. Hopkins et al. (2015) introduced algorithms based the sum of squares hierarchy with the first proven algorithmic threshold of n h/4. However this class of algorithm generally requires high computing resources and relies on complex mathematical tools (which makes its algorithmic optimization difficult). Other studied methods
have been inspired by different perspectives like homotopy in Anandkumar et al. (017). statistical
physics (Arous et al. (2020). Ros et al.] (2019). WWin et al. (2019) and Biroli et al. (2020). quantum
computing (Hastings (2020) as well as statistical query (Dudeja & Hsu (2020)).
Recently, a fundamentally different set of mathematical tools that have been developed for tensors in the context of high energy physics have been used to approach the problem. They consist in trace invariants of degree E N, obtained by contracting pair of indices of d copies of the tensor T. They have been used in Evnin (2020) to study the highest eigenvalue of a real symmetric Gaussian tensor. Subsequently, Gurau (0220) provided a theoretical study on a function based on an infinite sum of these invariants. Their results suggest transition phase for the highest eigenvalue of tensor for B around n 1/2 in a similar way to the BBP transition in the matrix case (Baik et al. (2005)) Thus, this function allows the detection of a spike. However evaluating it involves computing an integral over n-dimensional space, which may not be possible in polynomial time.
The contribution of this paper is the use of these invariant tools to build tractable algorithms with polynomial complexity. In contrast to Gurau (2020). instead of using invariants, we select one trace invariant with convenient properties to build our algorithms. It lets us detect the presence of the signal linearly in time and with a space requirement in O(1). Moreover, in order to recover the signal vector besides simply detecting it, we introduce new tools in the form of matrices associated to this specific invariant. Within this framework, we show as particular cases, that the two simpler graphs (of degree two) are similar to the tensor unfolding and the homotopy algorithms (which is equivalent to average gradient descent). These two algorithms are the main practical ones known from the point of view of space and time requirement (Anandkumar et al. (2017) provides table comparison).
of an infinite number of
We use bold characters T, M,M for tensors, matrices and vectors and Tisk- Myj vs for their components. [p] denotes the set (1,....n). A real k-th order tensor of order i if it a member of the tensor product of IR: E [k]: T 8 T(. VT G2 where G& is the symmetric group (more details are provided in Appendix ??). For vector v e R", we use & u 8 a @ @ E 8 R. to denote its p-th tensor power.
Notations
k i-i R": It is symmetric if Tiy..i =
(v, w) denotes the scalar product of v and w.
Let's define the operator norm, which is equivalent to the highest eigenvalue of a tensor of any order: |Xl = max (X,,, (X.,....i_ ( ... (wx),,, vi E (1,...,,) n), ||wall| < 1} The trace of A is denoted Tr(A). We denote the expectation of variable X by [[X) and its variance by oXX). We say that a function ff is negligible compared to a positive function and we write f = (g)) lim f/g - O.
Einstein summation convention It is important to keep in mind throughout the paper that we will follow the Einstein summation convention: when index variable appears twice in single term and is not otherwise defined, it implies summation of that term over all the values of the index. For example: Taje Tejz Eisk Teja Task. It is common convention when addressing tensor problems that helps to make the equations more comprehensible.
2

---

Under review as a conference paper at ICLR 2021
2
GENERAL FRAMEWORK FOR SIGNAL DETECTION AND RECOVERY
2.1 WHAT DO WE USE TO STUDY THE SIGNAL?
An important concept in problems involving matrices is the spectral theory. It refers to the study of eigenvalues and eigenvectors of a matrix. It is of fundamental importance in many areas. In machine learning, the matrix PCA computes the eigenvectors and eigenvalues of the covariance matrix of the features to perform a dimensional reduction while ensuring most of the key information is maintained. In this case, the eigenvalues is a very efficient tool to describe data variability. In the case of signal processing, eigenvalue can contain information about the intensity of the signal, while the eigenvector points out to its direction. Lastly, more theoretical example involves quantum physics where the spectrum of the matrix operator is used to calculate the energy levels and the state associated.
In all of these examples, an important property of the eigenvalues of a n-dimensional matrix M is its invariance under orthogonal transformations {M - OMO- 1,0 (n)) where O(n) is the n-dimensional orthogonal group (i.e. the group of real matrices that satisfies 00 = In, which should not be confused with the computational complexity O(n)). Since these transformations es- sentially just rotate the basis to define the coordinate system, they must not affect intrinsic informa- tion like data variability, signal intensity or the energy of a system. The eigenvalues are able to cap- ture some of these inherent information, but recovering the complete general information requires computing their respective eigenvectors (for example to find the principal component, the direction of the signal or the physical state). There are more such invariants than eigenvalues. Another impor- tant set worth mentioning are the traces of the n first matrix powers (r),), Tr Tr(A))..... (A"))) Obtaining them uses slightly different methods than eigenvalues, but they contain the same informa- tion since each set can be inferred from the other through some basic algebraic operations.
On the basis of the matrix case, we expect that for a tensor T E X are invariant under orthogonal transformations (Tay...af + O(1) :=1 R": tensor quantities that (k)
of To....e. for O
On1)) Vi (k) should capture similar intrinsic information like the intensity of the signal, and conceivably, there should be other objects related to these quantities that are able to indicate the direction of the signal. However, the concept of eigenvalue and eigenvector is ill defined in the tensor case and not practical giving that the number of eigenvalues is exponential with the dimension n (Qi (2005). Cartwright & Sturmfels (2033) and computing them is very complicated. In contrast, we have very convenient generalization of the traces of the power matrices for the tensors that call trace invariants. They have been extensively studied during the last years in the context of high energy physics and many important properties have been proven (Gurau 2017
We first give a more formal definition of trace invariants. Let T be a tensor whose entries are Ti.-...ie- Let's define contraction of pair of indices setting them equal to each other and summing over them, as in calculating the trace of a matrix (Aij + > A.). The trace invariants of the tensor T correspond to the different way contract pairs of indices in a product of an even number of copies of T. The degree of the trace invariants consists in the number of copies of T contracted. For example, Ei,dzi Tag Takkkk and Ei kz, Tayksk are trace invariants of degree 2. In the remainder of this paper, we will use the Einstein summation convention defined in the notation subsection.
A trace invariant of degree d of tensor T of order k admits a practical graphical representation as an edge colored graph G obtained by following two steps: we first draw d vertices representing the d different copies of T. The indices of each copy is represented by i half-edges with different color for each index position as shown in Figure Ta Then, when two different indices are contracted in the tensor invariant, we connect their corresponding half-edges in G. Reciprocally, to obtain the tensor invariant associated to a graph G with d vertices, we take d copies of T (one for each vertex), we associate a color for each index position, and we contract the indices of the d copies of T following the coloring of the edges connecting the vertices. We denote this invariant IG(T), Three important examples of trace invariants are: the melon diagram (Figure lb and the tadpole (Ic). Avohou et al. 2020) provides thorough study about the number of trace invariants for a given degree d. A very useful asset of these invariants is that we are able to compute their expectation for tensors whose components are Gaussian using simple combinatorial analysis (Gurau (2017))
3

---

Under review as a conference paper at ICLR 2021
(a) Tisk
Tiza Tiyk
(c) Tup Tisk
Figure 1: Example of graphs and their associated invariants
2.2 WHAT DO WE TO RECOVER THE SIGNAL?
As previously mentioned in Section 2.1, an invariant should be able to detect a signal. But if our goal is to recover it, we should find mathematical objects that are able to provide vector. To this effect, we introduce in this paper new set of tools in the form of matrices. We denote by Mş.e the matrix obtained by cutting an edge of graph g in two half edges (see Figure[for this cut amounts to not summing over the two indices i and i2 associated to these two half-edges and using them to index the matrix instead. We will drop the index G of the matrix when the context is clear.
example). Indeed,
edge
Cut the edge
ls
Tesk Tags
Mg.e = (Taysl Tiask bajk)y (2
Figure Obtaining matrix by cutting the edge of trace invariant graph
2.3 PHASE TRANSITION WITHIN THIS FRAMEWORK
We can represent the tensor from which we hope to extract the signal represented graphically as:
Tij
8 U2Ul Bi--1
Zij
Figure 3: Graphical decomposition of the tensor T
This decomposition leads us naturally to decompose in a similar way a tensor trace invariant Ig (T) into two parts, separating a first contribution (N) (T) associated to the pure noise tensor contribution and second part g (T) enclosing all the other contributions, which are resulting from the addition of the signal.
(5)
(T(T) - -(
(T).
identical decomposition can be carried out for the matrix. Let's consider tensor T, graph G and its associated trace invariant (T). Let's denote (T) the invariant associated to the subgraph obtained by removing from G the edge e and its two vertices. We can distinguish three kind of contributions to the matrix Mg.e that we denote M M.D. and M illustrated in Figure (where we denoted the invariant 1/ (T) by I' and dropped the index G, for simplicity).
(N) B(J! I,.
Lemma 1. ((M((N)
n
Using the lemma [ we identify three possible phases depending on which matrix operator norm is much larger than the others:
No detection and no recovery: If M E(M >
|
[M)
then no recovery and no detection is possible we can't distinguish if there a signal. is for example the phase for - 0.
4

---

Under review as a conference paper at ICLR 2021
M
M
(N)
Ma
(R)
Zi Ziz..
Z Zi......
(vi, Zig.
+
Vig Zi.Zi.....
Vig Pia
$1 02
f 82
22
f
22
f
12
l
r
((S)
M
+
r
Pure noise matrix
Signal contribution to the detection
Signal contribution to the recovery
X
Figure 4: Decomposition of a matrix graph and the melon example
Detection but no recovery: If [
M (MM Moop: [M llap then
detection but recovery. We detect the presence of the signal (thanks to the high- est cigenvalue) but we can't 't recover the signal vector since the leading cigenvector is not correlated to the signal vector.
Detection and recovery: ( 1lop
||M - ((M || the signal vector. It is for example the phase for 3 - oc.
We recover
2.4 ALGORIITMIIC THRESHOLD FOR GENERAL GRAPH
We can now state the important algorithms that will be essential for this paper. It is important to keep mind that the following claims concern the large n limit. Empirically, the approximation of large limit seems valid for 25.
Algorithm 1: Algorithm associated the graph and edge
Input: The tensor T Ok Z
Goal: Detection of v
Result: Gives the probability of the presence of spike
The first algorithm gives criteria for distinguishing pure noise tensor from tensor with spike. Denoting E( ( (B)) the expectation and ( (B)) the variance of the trace invariant associated to graph G for (B)), where the components of are Gaussian random. The algorithm consists simply in calculating the trace invariant of the tensor and comparing its distance from ((Lg(B)) with (B)).. ). straightforward see that calculating a trace invariant (which is scalar) like Tisk Tizt only needs O(1) memory.
Theorem 2. Let G be graph of degree d, 3 Bdet > so that Algorithm detects the presence of a signal for B 2 Bäet.
The second algorithm is able to recover the spike in tensor T through the construction of the matrix of size n X Mg.e (T) associated to a given graph G and edge e.
Algorithm 2: Recovery algorithm associated to the graph G and edge
Input: The tensor T
Bogk
&k
Z
Goal: Estimate Vo
Result: Obtaining an estimated vector v
5

---

Under review as a conference paper at ICLR 2021
Theorem 3. Let G be graph of degree d, 3 Brec 0 so that Algorithm 2 gives estimator so that v is strongly correlated to vo (v, vo) > f.r) 3 2 Bree-
Since the algorithms 2 and consists in algebraic operations on the tensors entries, they are very suitable for parallel architecture. The Theorem gives lower bound to the threshold above which we can detect and recover a spike using a single graph. Interestingly, this threshold which appears naturally in framework, matches the threshold below which there is known algorithm that able to recover the spike in polynomial time. We call the Gaussian variance of a graph g, the variance of the invariant (B) where Bijk are Gaussian random.
Theorem 4. Let k > 3. It is impossible detect or recover the signal using a single graph below the threshold 3 S n( R/4 which is the minimal Gaussian variance of any graph G.
SOME APPLICATIONS OF THIS FRAMEWORK
Using these algorithms, we are now able to investigate the performance of our framework in various theoretical settings. In the first two subsections, we study the algorithms associated to two trace invariants of degree 2. They consist of the melonic diagram, which gives very practical detection algorithm, and whose recovery algorithm is variant of the unfolding algorithm, and the tadpole diagram whose recovery algorithm similar to the homotopy algorithm. The last two sections are an illustration of the versatility of this framework. We study the case the dimensions n, of the tensor
T X )) are not necessarily equal, which is important for practical applications where the dimensions are naturally asymmetric. Our methods allows us to derive a new algorithmic threshold for this case.
3.1 THE MELON GRAPH SIMILAR TO TENSOR UNFOLDING
Let's consider the invariant T....., Tin... (illustrated by the graph in Figure Ib when k = 3). Its recovery algorithm (with the matrix obtained by cutting any of the edges) is similar to the tensor unfolding method presented in Richard & Montanari (2014). The difference is that the melonic algorithm uses only a matrix n X instead of matrix n 6/2 x/2 k/2 for the tensor unfolding. However, the main contribution of this framework for this graph is that it allows the detection in linear time (n* operations for a input (tensor) of size n² ) in a constant memory space (it just calculates a scalar). This provides it potential usefulness to use more computationally costly methods to recover it. Also, to the best of our knowledge, this framework the first theoretically prove conjuncture that the unfolding algorithm works also for the symmetric case.
first step for detecting the signal before deciding
Theorem 5.
The algorithmss I and work for the melon graph with Bast Bree O(nb/1) in linear time and respectively (nn²) and O(1) memory requirement.
3.2 THE TADPOLE GRAPH
Figure 1c has special characteristic: we can obtain two disconnected parts by cutting only one line. Therefore, the matrix obtained by cutting that edge is rank one (in the form of wo?"). Thus, the vector v has weak correlation with the signal Vo. which allow the tensor power iteration (1/ & Ty))))u) to empirically recover (formal proofs require to consider some more sophisti- cated variants of power iteration like in Anandkumar al. (011)) and Biroli et al. (2020)). This algorithm is a variant of the already existent homotopy algorithm.
Theorem 6. The tadpole graph allows to recover the signal vector for l 2 3 and B = O(nt/1) by using local algorithms to enhance the signal contribution of the vector Tésj-
4 NUMERICAL EXPERIMENTS
In this section will investigate the empirical results of the previously mentioned applications in order to see they match with our theoretical results. We restrict to the dimension & 3 for simplicity. More details about the experiments settings could be found in the Appendix.

---

Under review as a conference paper at ICLR 2021
4.1 COMPARISON RECOVERY METHODS
This distinction is easily visible, for n 100 and 3 = 100 in Figure 5a where we plotted the histograms of the melonic invariant (in blue without signal and in orange with signal) for 500 in- dependent instances Gaussian random tensors Thus, to measure the accuracy of the detection of the signal, we use the quantity: 1 cardinal of the Intersection over the cardinal of the Union (1-IoU). Figure ?? suggests that high probability detection requires 3 2 3/1
300
T Z 8r
250
Density
200
Z
150
100
50
0.995
1.000
1.005
1.010
1.015
1.020
(a) Distribution of the melon invariant without (blue) and with (orange) signal.
Figure 5: Detection using the melonic graph.
For the recovery algorithm, we focus in the symmetric case (the most studied case and the most sistent with a symmetric spike) and, as in Richard & Montanari (2014). for every algorithm we use two variants: the simple algorithm outputting e and an algorithm where apply 100 power itera- tions on v: 0, + Ty distinguishable by a prefix "p-". In Figure ??, we run 200 experiments for each value of and plot the 95% confidence interval of the correlation of the vector recovered with the signal vector. We will compare our method to two type of results:
Other algorithmic methods: the melonic (tensor unfolding) and the homotopy. To the best of our knowledge, they give the state of art respectively for the symmetric and asymmet- ric tensor (Biroli et al. (2020)). Other methods exist but are either too computationally expensive (sum of squares) are variants of these algorithms.
information-theorrtiee results: In (Richard & Montanari (0144), it was proven that com- puting the global minimum of the function H> De 2% recovers the signal vector vo above a theoretical threshold fnm = 2.87 /n n but with exponential time, and that no other ap- proach do significantly better than that. Thus, we plot in red dashed line denoted "perf" the deep minimum that is closest to vo, by using gradient method with an initialization in Vo.
CONCLUSION
In this paper we introduced a novel framework for the tensor PCA based on trace invariants. Within this framework, we provide different algorithms to detect a signal vector or recover it. These al- gorithms use tensor contractions that has a high potential of parallelization and computing opti- mization. We illustrate the practical pertinence of our framework by presenting some examples of algorithms and prove their ability to detect and recover signal vector linearly in time for 3 above the optimal algorithmic threshold. Note that, one of the proposed detection algorithms requires only (1)) memory requirement which could be advantageous in some applications. Moreover, we also show that two well known algorithms (Homotopy and Tensor Unfolding) can be mapped to our framework and result to simpler graph (e.g. the melonic graph). Important directions future research is to apply these methods to real data.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Anima Anandkumar, Dean P Foster, Daniel Hsu, Sham M Kakade, and Yi-Kai Liu. A spectral algorithm for latent dirichlet allocation. Algorithmica, 72(1):193 214, 2015.
Anima Anandkumar, Yuan Deng, Rong Ge, and Hossein Mobahi. Homotopy analysis for tensor pea. Conference on Learning Theory, pp. 79-104. PMLR, 2017.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15: 2773-2832, 2014.
Gerard Ben Arous, Reza Gheissari, Aukosh Jagannath, et Algorithmic thresholds for tensor pea. Annals of Probubility, 48(4):2052-2087, 2020.
Remi C. Avohou, Joseph Ben Geloun, and Nicolas Dub. On the counting of ((N) tensor invariants. Ady. Theor. Math. Phys., 24(4):821-878, 2020. doi: 1044300/ATTMP.2200022..... w2...00................
Kamyar Azizzadenesheli, Alessandro Lazaric, and Animashree Anandkumar, Reinforcement learn- ing of pomdps using spectral methods. In 29th Annual Conference Learning Theory, volume 49 of Proceedings of Machine Learning Research, publisher = PMLR, pp. 193-256, 2016.
Jinho Baik, Gérard Ben Arous, Sandrine Péché, al. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5): (00)):144119999 1697, 2005.
Giulio Biroli, Chiara Cammarota, and Federico Ricei- Tersenhi. How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor PCA. Jour- nal of Physics Mathematical General, 53(17): 174003, May 2020.
Giulio Biroli, Chiara Cammarota, and Federico Ricci-Tersenghi. How to iron out rough landscapes and get optimal performances: averaged gradient descent and its application to tensor pea. Journal of Physics A: Mathematical and Theoretical, 53(17):11400) 2020.
Dustin Cartwright and Bernd Sturmfels. The number of eigenvalues of tensor, Linear algebra and its applications, 438(2):942 2013.
Rishabh Dudeja and Daniel Hsu. Statistical Query Lower Bounds for Tensor PCA. arXiv e-prints, art. MxXiv2208.004000 August 2020.
Oleg Evnin. Melonic dominance and the largest eigenvalue of large random tensor, arXiv preprint / 2020.
Lianli Gao, Jingkuan Song, Xingyi Liu, Junming Shao, Jiajun Liu, and Jie Shao. Learning high- dimensional multimedia data: the state of the art. Multimedia Systems, 23(3):303-313, 2017.
R. Gurau, Random Tensors. Oxford University Press, 2017.
Razvan Gurau. On the generalization of the wigner semicircle law to real symmetric tensors. arXiv preprint arXiv:2004.00666 2020.
Matthew B. Hastings. Classical and Quantum Algorithms for Tensor Principal Component Analysis. Quantum, 4:237, February 2020.
Samuel B. Hopkins, Jonathan Shi, and David Steurer. Tensor principal component analysis via sum-of-squares proofs. CoRR, abs/1500..33. 2015.
Majid Janzamin, Hanie Sedghi, and Anima Anandkumar. Beating the perils of non-convexity: Guar- anteed training of neural networks using tensor methods. arXiv preprint arXiv: 2015.
I. T. Jolliffe and Jorge Cadima. Principal component analysis: review and recent developments. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sci- ences, 374, 2016.
8

---

Under review as a conference paper at ICLR 2021
Jinsung Kim, Aravind Sukumaran- Rajam,, Changwan Hong, Ajay Panyala, Rohit Kumar Srivas- tava, Sriram Krishnamoorthy, and Ponnuswamy Sadayappan. Optimizing tensor contractions in cesd (t) for efficient execution on gpus. In Proceedings the 2018 International Conference Supercomputing, pp. 96-106, 2018.
T. Kolda and B. Bader. Tensor decompositions and applications. SIAM Rev., 51:455-500, 2009.
Liqun Qi. Eigenvalues of real supersymmetric tensor. Journal of Symbolic Computation, 40(6): 1302 1324, 2005.
Emile Richard and Andrea Montanari. A statistical model for tensor pea. In Advances in Neural Information Processing Systems, pp. 2897-2905, 2014.
Valentina Ros, Gerard Ben Arous, Giulio Biroli, and Chiara Cammarota. Complex energy land- scapes in spiked-tensor and simple glassy models; Ruggedness, arrangements of local minima, and phase transitions. Physical Review X, 9(1):01 2019.
Mohamed Amine Seddik, Mohamed Tamaazousti, and Romain Couillet. A kernel random matrix- based approach for sparse pea. In International Conference on Learning Representations (ICLR), 2019.
Nicholas D Sidiropoulos, Lieven De Lathauwer, Xiao Fu, Kejun Huang, Evangelos Papalexakis, and Christos Faloutsos. Tensor decomposition for signal processing and machine learning. IEEE Transactions on Signal Processing, 65(13):3551-358222222 2017.
Taiji Suzuki. Adaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Rep- resentations, 2019.
Alexander S Wein, Ahmed El Alaoui, and Cristopher Moore. The kikuchi hierarchy and tensor pca. In Annual Symposium on Foundations of Computer Science (FOCS), pp. 1446-1468. IEEE, 2019.


Reviews:
[{"review_id": "pRAsk8Oa1Tk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a pair of interesting algorithms using trace invariants to detect the signal in the signal-plus-noise tensor PCA framework.  The algorithms function by considering cutting an edge in the graph representation of the trace invariant, yielding a matrix whose leading eigenvector provides a (up to a rotation) estimate of the signal vector $v$.  This algorithm appears to be very interesting and works well in a series of simulations. \n\nUnfortunately, the presentation of the paper makes it very difficult to assess the importance of the contribution.  The introduction is well-written and well-motivated, though the later segmentation of the paper into many small subsections without much exposition makes the flow of the paper and its results hard to follow.  In addition, the notation and terminology in the paper are imprecise and, with important terminology and symbology introduced without definition or background citation.\n\nPros:\n- The proposed algorithm is clever and appears to do well compared to existing approaches in experiments.\n\n- Well written introduction (with the only complaint being some minor grammatical errors).\n\n\n\nCons:\n- Important notation is introduced, and is not defined; Equation 4 is an example of this, where $\\langle \\cdot \\rangle$ (I assume this means $\\mathbb{E}$?), $\\bar{\\mathbf{T}}$, and $\\mathcal{E}^0(\\mathcal{G})$ are all undefined.  This occurs often in the paper and in the appendix.\n\n- In the $\\bullet, \\times, \\bullet$ decomposition at the start of Section 2.3, what is $\\sqrt{N}$?\n\n- What is the variance of a graph (as in Theorem 4)?  The proof sketch of this theorem is very hard to follow.\n\n- Algorithm 1 is imprecise; what does \"compare $\\alpha$ to $\\sigma(I^{(N)}(T))$ mean?  If $\\alpha>\\sigma(I^{(N)}(T))$ then a spike is detected?  How do you compute the variance of $I^{(N)}(T)$?  How would you compute this if the noise model did not have unit variance)?  \n\n- Both algorithms are only presented for 3-way tensors, but the Theoretical claims are for higher order tensors?\n\n- The proofs of the theorems and the statement of the theorems are, in general, a bit imprecise.  For example, in the proof of Theorem 2, Chebyshev's inequality will not guarantee disjointness everywhere, but only with high probability.  This is the case if $\\beta_{det}$ is finite.  This is a finite $\\beta_{det}$ result, with a claim only holding in the limit.\n\n- In Theorem 5, what are the intermediate graphs/matrices?  In addition, this section (and Appendix C discussing perfect one-factorization) are a bit opaque.\n\n- Is the decomposition after equation 5 only for the melon graph?  For more complex graphs (i.e., the tetrahedral), I believe you will have additional trace-like coefficients on all terms.  In any event, I am confused about the summands.  I do not see why the all $Z$ sum would have a $\\beta$, while the cross-terms would not.  Furthermore, why would the all $v$ sum not have a $\\beta^d$ coefficient?  This is what is implicitly being used in the proofs?\n\n- In the experiments, important details are left out.  What is the setup here: what are the $v$'s, how many iterations of tensor power method are applied, how many MC replicates are run to produce the error bars, what is the y-axis, what are the runtimes here, what is Random in Figure 6?  More detail would help a lot to understand how your new approach compares (it appears well) with the current literature.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NvIwXUMyrB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper studies the detection and recovery problem in spiked tensor models in the form T = \\beta v0^\\otimes k + Z, where v0 is the underlying spike signal and Z is a Gaussian noise.  The authors claim that they propose a new framework to solve the problem, by looking at the trace invariants of tensors. The authors provide a detection algorithm (Algorithm 1) and a recovery algorithm (Algorithm 2), as well as the corresponding phases. The authors claim that: 1) they \"build tractable algorithms with polynomial complexity\", \"a detection algorithm linear in time\"; 2) the algorithms are very suitable for parallel architectures; 3) an improvement of the state of the art for the symmetric tensor PCA experimentally. The authors furthermore discuss the asymmetric case and the multiple spike case.\n\n\nRecommendation:\n\nAt the current stage I vote for rejection. I am not able to follow the proofs in this paper due to missing definitions of terms and notations. Also some claims are not proved. See below for details.\n\n\nPros:\n\n- The methods used in the paper seem new for spiked tensor models.\n\n- Some experimental results are provided. \n\n\nCons: \n\n- The readability of this paper severely suffers from its writing. At the current stage, filled with undefined or inconsistent notations and terms, this paper is not self-contained and hard to follow. This becomes worse considering the fact that this paper studies tensor problems -- many tensor-related terms have multiple definitions (e.g., eigenvalues, ranks). It will be very hard to follow the proofs if the definitions are unclear. Here is an incomprehensive list:\n\t- Middle of Page 3: what is the *formal* definition of contracting (instead of saying \"equivalent to a matrix multiplication\")? Also, trace invariants are never formally defined in this paper.\n\t- eq.(2),(3): what is O(n) here? Also, what does the bold O refer to? Right before eq.(4) the authors use another notation \\mathcal{O}(n). Is this the same as the first O(n)? In the abstract the authors use \\mathcal{O}(1) to refer to the constant order. Why the inconsistency?\n\t- End of Page 3: how is \\mathcal{G} related to trace invariants formally?\n\t- Section 2.2: this is not clear. What are the matrices here? What is the definition of M_{G,e}?\n\t- Section 2.3: what is the definition of I_G(T)?\n\t- Theorem 3: what is the Loss function here?\n\t- Top of Page 5: what is the exact definition of \"dominating\" here?\n\n- It should be noted that, without clear definitions of I_G(T) and M_{G,e}(T), there is no way to verify Algorithm 1 and 2.\n\n- The authors claim \"polynomial complexity\" at the beginning of the paper, but it is never proved. Theorem 7 claims that Algorithm 1 and 2 run in linear time. I cannot find that in the proof.   \n\n- It is unclear why the algorithms \"are very suitable for parallel architectures\", as the authors have claimed. Have the authors tried running the experiments in parallel?\n\n- Theorem 4, 5, 9, 10 do not have complete proofs. \n\n\nMinor comments:\n\n- Page 2 Notations: typeface of v is not consistent. \n\n- Page 8: \"eg\" should be \"e.g.\"\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ARRUyGmhYcy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n \nThe paper provides an interesting algorithm for tensor PCA, which is based on trace invariants. The problem consists of recovering a (single-spike/multiple orthogonal spikes) tensor corrupted by a Gaussian noise tensor. The authors proposed a new algorithm which allows recovering a signal for a sufficiently small signal to noise ratio. \n\n##########################################################################\nReasons for score: \n \nOverall, I vote for accepting. I like the idea, and the proofs seem to be coherent and correct. The problem has clear importance for the theoretical/statistical physics community; however, I am not convinced of the importance of the problem considered here for the ICLR community and appreciate the author’s comments on this. I also have a few minor concerns, which, hopefully, can be addressed by the authors in the rebuttal period. \n \n##########################################################################\n\nPros: \n1. The paper takes an interesting question about tensor PCA and proposes a promising approach to solve it based on the trace invariants. For me, the problem is encouraging, while I would appreciate a discussion about possible machine learning/AI applications (learning latent variable models? anything else?)\n \n2. The mathematical justification of the statements seems to be correct for me and ok to follow.  \n\n3. It is claimed in the paper that the algorithm improves the state-of-the-art (signal to noise ratio requirements) in several cases, while a brief survey/table of the recent results is missing.  Unfortunately, I am not working in this area and probably not familiar with recent results\n \n##########################################################################\nCons: \n \n1. Applications for ML/AI/Language processing are not very clear for me, and I would appreciate a discussion on this in the paper. \n\n2. Empirical justification. I would highly appreciate having more experiments on real data (if any) and a detailed comparison of the methods in terms of accuracy/memory/time. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the tensor principal component analysis problem, where we observe a tensor T = \beta v^{\otimes k} + Z where v is a spike and Z is a Gaussian noise tensor. The goal is to recover an accurate estimate to the spike for as small a signal-to-noise ratio \beta as possible. There has been considerable interest in this problem, mainly coming from the statistics and theoretical computer science communities, and the best known algorithms succeed when \beta \geq n^{k/4} where n is the dimension of v. The main contribution of this paper is to leverage ideas from theoretical physics and build a matrix whose top eigenvector is correlated with v for sufficiently large \beta using trace invariants. On synthetic data, the algorithms achieve better performance than existing methods.

The main negative of this paper is that it is not so clear how tensor PCA is relevant in machine learning applications. The authors gave some references to applications of tensor methods, but I want to point out that all of those works are about using tensor decompositions, which despite the fact that they are both about tensors, are rather different sorts of tools. Many of the reviewers also found the paper difficult to follow. I do think exposition is particularly challenging when making connections between different communities, as this work needs to introduce several notions from theoretical physics. I am also not sure how novel the methods are, since a somewhat recent paper Moitra and Wein, "Spectral Methods from Tensor Networks", STOC 2019 also uses tensor networks to build large matrices whose top eigenvalue is correlated with a planted signal, albeit for a different problem called orbit retrieval. 
Decision: Reject