Estimating Higher-Order Moments Using Symmetric Tensor Decomposition

DOI10.1137/19M1299633MaRDI QIDQ5146702zbMATHFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1820149 (Why is no real title available?)
• scientific article; zbMATH DE number 46578 (Why is no real title available?)
• A comparison of algorithms for fitting the PARAFAC model
• A tensor approach to learning mixed membership community models
• Algorithm 778: L-BFGS-B
• Anomaly detection in scientific data using joint statistical moments
• Computing symmetric rank for symmetric tensors
• Efficient Computation of Higher-Order Cumulant Tensors
• Efficient MATLAB Computations with Sparse and Factored Tensors
• Estimation and Testing of Parameters in Multivariate Laplace Distribution
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Fourier PCA and robust tensor decomposition
• Generating polynomials and symmetric tensor decompositions
• Learning mixtures of Gaussians in high dimensions
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract)
• Most tensor problems are NP-hard
• Multivariate skewness and kurtosis measures with an application in ICA
• NPSA: Nonorthogonal Principal Skewness Analysis
• Numerical optimization for symmetric tensor decomposition
• Shifted power method for computing tensor eigenpairs
• Symmetric Tensors and Symmetric Tensor Rank
• Tensor decompositions for learning latent variable models
• Tensor methods in statistics
• The sample complexity of multireference alignment

Cited in

(8)

• Moment Estimation for Nonparametric Mixture Models through Implicit Tensor Decomposition
• Tensor decomposition for learning Gaussian mixtures from moments
• A higher-order LQ decomposition for separable covariance models
• Learning diagonal Gaussian mixture models and incomplete tensor decompositions
• Communication lower bounds of bilinear algorithms for symmetric tensor contractions
• Scalable symmetric Tucker tensor decomposition
• Scalable tensor methods for nonuniform hypergraphs
• Monte Carlo approximate tensor moment simulations.

Describes a project that uses

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)