Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubspace power method for symmetric tensor decomposition and generalized PCA
88
0
0.0
(
0
)
Added by
Joe Kileel
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We introduce the Subspace Power Method (SPM) for calculating the CP decomposition of low-rank even-order real symmetric tensors. This algorithm applies the tensor power method of Kolda-Mayo to a certain modified tensor, constructed from a matrix flattening of the original tensor, and then uses deflation steps. Numerical simulations indicate SPM is roughly one order of magnitude faster than state-of-the-art algorithms, while performing robustly for low-rank tensors subjected to additive noise. We obtain rigorous guarantees for SPM regarding convergence and global optima, for tensors of rank up to roughly the square root of the number of tensor entries, by drawing on results from classical algebraic geometry and dynamical systems. In a second contribution, we extend SPM to compute De Lathauwers symmetric block term tensor decompositions. As an application of the latter decomposition, we provide a method-of-moments for generalized principal component analysis.
rate research
Read More
We consider the problem of decomposing a real-valued symmetric tensor as the sum of outer products of real-valued, pairwise orthogonal vectors. Such decompositions do not generally exist, but we show that some symmetric tensor decomposition problems can be converted to orthogonal problems following the whitening procedure proposed by Anandkumar et al. (2012). If an orthogonal decomposition of an $m$-way $n$-dimensional symmetric tensor exists, we propose a novel method to compute it that reduces to an $n times n$ symmetric matrix eigenproblem. We provide numerical results demonstrating the effectiveness of the method.
In this paper we study the problem of recovering a tensor network decomposition of a given tensor $mathcal{T}$ in which the tensors at the vertices of the network are orthogonally decomposable. Specifically, we consider tensor networks in the form of tensor trains (aka matrix product states). When the tensor train has length 2, and the orthogonally decomposable tensors at the two vertices of the network are symmetric, we show how to recover the decomposition by considering random linear combinations of slices. Furthermore, if the tensors at the vertices are symmetric but not orthogonally decomposable, we show that a whitening procedure can transform the problem into an orthogonal one, thereby yielding a solution for the decomposition of the tensor. When the tensor network has length 3 or more and the tensors at the vertices are symmetric and orthogonally decomposable, we provide an algorithm for recovering them subject to some rank conditions. Finally, in the case of tensor trains of length two in which the tensors at the vertices are orthogonally decomposable but not necessarily symmetric, we show that the decomposition problem reduces to the problem of a novel matrix decomposition, that of an orthogonal matrix multiplied by diagonal matrices on either side. We provide two solutions for the full-rank tensor case using Sinkhorns theorem and Procrustes algorithm, respectively, and show that the Procrustes-based solution can be generalized to any rank case. We conclude with a multitude of open problems in linear and multilinear algebra that arose in our study.
We consider the problem of decomposing higher-order moment tensors, i.e., the sum of symmetric outer products of data vectors. Such a decomposition can be used to estimate the means in a Gaussian mixture model and for other applications in machine learning. The $d$th-order empirical moment tensor of a set of $p$ observations of $n$ variables is a symmetric $d$-way tensor. Our goal is to find a low-rank tensor approximation comprising $r ll p$ symmetric outer products. The challenge is that forming the empirical moment tensors costs $O(pn^d)$ operations and $O(n^d)$ storage, which may be prohibitively expensive; additionally, the algorithm to compute the low-rank approximation costs $O(n^d)$ per iteration. Our contribution is avoiding formation of the moment tensor, computing the low-rank tensor approximation of the moment tensor implicitly using $O(pnr)$ operations per iteration and no extra memory. This advance opens the door to more applications of higher-order moments since they can now be efficiently computed. We present numerical evidence of the computational savings and show an example of estimating the means for higher-order moments.
Several tensor eigenpair definitions have been put forth in the past decade, but these can all be unified under generalized tensor eigenpair framework, introduced by Chang, Pearson, and Zhang (2009). Given mth-order, n-dimensional real-valued symmetric tensors A and B, the goal is to find $lambda in R$ and $x in R^n$, $x eq 0$, such that $Ax^{m-1} = lambda Bx^{m-1}$. Different choices for B yield differe
We propose a new algorithm for computing the tensor rank decomposition or canonical polyadic decomposition of higher-order tensors subject to a rank and genericity constraint. Reformulating this as a system of polynomial equations allows us to leverage recent numerical linear algebra tools from computational algebraic geometry. We describe the complexity of our algorithm in terms of the multigraded regularity of a multihomogeneous ideal. We prove effective bounds for many formats and ranks and conjecture a general formula. These bounds are of independent interest for overconstrained polynomial system solving. Our experiments show that our algorithm can outperform state-of-the-art algebraic algorithms by an order of magnitude in terms of accuracy, computation time, and memory consumption.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
