We study the problem of finding orthogonal low-rank approximations of symmetric tensors. In the case of matrices, the approximation is a truncated singular value decomposition which is then symmetric. Moreover, for rank-one approximations of tensors of any dimension, a classical result proven by Banach in 1938 shows that the optimal approximation can always be chosen to be symmetric. In contrast to these results, this article shows that the corresponding statement is no longer true for orthogonal approximations of higher rank. Specifically, for any of the four common notions of tensor orthogonality used in the literature, we show that optimal orthogonal approximations of rank greater than one cannot always be chosen to be symmetric.
The convergence guarantees of the orthogonal approximation problem have been improved by imposing structural assumptions on the tensors under consideration. An important special case that guarantees also global convergence is when @math is completely orthogonally decomposable, i.e., when @math has an exact orthogonal (but unknown) decomposition @math with @math for all @math . Optimal rank- @math orthogonal decompositions for these tensors can be computed by successively computing the optimal rank-one approximations, subtracting these from @math and iterating, in a deflation procedure @cite_10 . An optimal rank-one approximation of orthogonally decomposable tensors can be computed efficiently by the tensor power iteration method @cite_24 and each term corresponds to a singular vector of the original tensor. This method has also been extended to nearly completely orthogonally decomposable tensors @cite_24 @cite_4 @cite_6 .
@cite_24 @cite_10 @cite_6 @cite_4
2105724942 2002598080 2624256161 2242384245
This work considers a computationally and statistically efficient parameter estimation method for a wide class of latent variable models--including Gaussian mixture models, hidden Markov models, and latent Dirichlet allocation--which exploits a certain tensor structure in their low-order observable moments (typically, of second- and third-order). Specifically, parameter estimation is reduced to the problem of extracting a certain (orthogonal) decomposition of a symmetric tensor derived from the moments; this decomposition can be viewed as a natural generalization of the singular value decomposition for matrices. Although tensor decompositions are generally intractable to compute, the decomposition of these specially structured tensors can be efficiently obtained by a variety of approaches, including power iterations and maximization approaches (similar to the case of matrices). A detailed analysis of a robust tensor power method is provided, establishing an analogue of Wedin's perturbation theorem for the singular vectors of matrices. This implies a robust and computationally tractable estimation approach for several popular latent variable models. The singular value decomposition (SVD) has been extensively used in engineering and statistical applications. This method was originally discovered by Eckart and Young in [Psychometrika, 1 (1936), pp. 211--218], where they considered the problem of low-rank approximation to a matrix. A natural generalization of the SVD is the problem of low-rank approximation to high order tensors, which we call the multidimensional SVD. In this paper, we investigate certain properties of this decomposition as well as numerical algorithms. Finding the symmetric and orthogonal decomposition of a tensor is a recurring problem in signal processing, machine learning, and statistics. In this paper, we review, establish, and compare the perturbation bounds for two natural types of incremental rank-one approximation approaches. Numerical experiments and open questions are also presented and discussed. Many idealized problems in signal processing, machine learning, and statistics can be reduced to the problem of finding the symmetric canonical decomposition of an underlying symmetric and orthogonally decomposable (SOD) tensor. Drawing inspiration from the matrix case, the successive rank-one approximation (SROA) scheme has been proposed and shown to yield this tensor decomposition exactly, and a plethora of numerical methods have thus been developed for the tensor rank-one approximation problem. In practice, however, the inevitable errors (say) from estimation, computation, and modeling necessitate that the input tensor can only be assumed to be a nearly SOD tensor---i.e., a symmetric tensor slightly perturbed from the underlying SOD tensor. This paper shows that even in the presence of perturbation, SROA can still robustly recover the symmetric canonical decomposition of the underlying tensor. It is shown that when the perturbation error is small enough, the approximation errors do not accumulate with ...