Estimating Higher-Order Moments Using Symmetric Tensor Decomposition

DOI10.1137/19M1299633zbMATH Open1467.15022arXiv1911.03813MaRDI QIDQ5146702FDOQ5146702

Authors: Samantha N. Sherman, Tamara G. Kolda 

Publication date: 26 January 2021

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Abstract: 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 $rllp$ symmetric outer products. The challenge is that forming the empirical moment tensors costs $O(p{n}^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.

Full work available at URL: https://arxiv.org/abs/1911.03813

Recommendations

• Symmetric tensor decomposition by an iterative eigendecomposition algorithm
• Symmetric tensor decomposition
• Tensor symmetrization and its applications in generalized principal component analysis
• Decomposition of Low Rank Multi-symmetric Tensor
• Symmetric tensor decomposition by alternating gradient descent
• Symmetric rank-1 approximation of symmetric high-order tensors
• Stochastic tensors and approximate symmetry
• Gradient Descent for Symmetric Tensor Decomposition
• Efficient Computation of Higher-Order Cumulant Tensors
• General tensor decomposition, moment matrices and applications

zbMATH Keywords

Gaussian mixture modelshigher-order momentshigher-order cumulantssymmetric tensor decompositionimplicit tensor formation

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Efficient MATLAB Computations with Sparse and Factored Tensors
• Algorithm 778: L-BFGS-B
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Estimation and Testing of Parameters in Multivariate Laplace Distribution
• Title not available (Why is that?)
• Most Tensor Problems Are NP-Hard
• Multivariate skewness and kurtosis measures with an application in ICA
• Shifted power method for computing tensor eigenpairs
• Tensor decompositions for learning latent variable models
• Symmetric Tensors and Symmetric Tensor Rank
• Computing symmetric rank for symmetric tensors
• A comparison of algorithms for fitting the PARAFAC model
• Numerical optimization for symmetric tensor decomposition
• Generating polynomials and symmetric tensor decompositions
• Efficient Computation of Higher-Order Cumulant Tensors
• Learning Mixtures of Gaussians in High Dimensions
• Learning mixtures of spherical gaussians
• The Sample Complexity of Multireference Alignment
• Fourier PCA and robust tensor decomposition
• Anomaly detection in scientific data using joint statistical moments
• NPSA: Nonorthogonal Principal Skewness Analysis

Cited In (4)

• Moment Estimation for Nonparametric Mixture Models through Implicit Tensor Decomposition
• Scalable tensor methods for nonuniform hypergraphs
• Communication Lower Bounds of Bilinear Algorithms for Symmetric Tensor Contractions
• Scalable symmetric Tucker tensor decomposition

Uses Software

• L-BFGS-B
• L-BFGS
• TensorToolbox
• LBFGS-B
• Adam
• GitHub

This page was built for publication: Estimating Higher-Order Moments Using Symmetric Tensor Decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146702)