Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity
We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous bounds. The analysis is based on properties of random polynomials, namely the spacings of an ensemble of polynomials. Our technique also applies to other applications of tensor decompositions, including spherical Gaussian mixture models.
Code (0)
등록된 구현이 없습니다.
Tasks
Tensor DecompositionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Generative Modeling via Hierarchical Tensor Sketching
We propose a hierarchical tensor-network approach for approximating high-dimensional probability density via empirical distribution. This leverages randomized singular value decomposition (SVD) techniques and involves so…
Tensor Star Tensor Decomposition and Its Applications to Higher-order Compression and Completion
A novel tensor decomposition framework, termed Tensor Star (TS) decomposition, is proposed which represents a new type of tensor network decomposition based on tensor contractions. This is achieved by connecting the core…
Tensor DecompositionFinite Sample Analysis of Tensor Decomposition for Learning Mixtures of Linear Systems
We study the problem of learning mixtures of linear dynamical systems (MLDS) from input-output data. The mixture setting allows us to leverage observations from related dynamical systems to improve the estimation of indi…
Tensor DecompositionTensor Regression Using Low-rank and Sparse Tucker Decompositions
This paper studies a tensor-structured linear regression model with a scalar response variable and tensor-structured predictors, such that the regression parameters form a tensor of order $d$ (i.e., a $d$-fold multiway a…
parameter estimationregressionSolving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
We consider the problem of solving mixed random linear equations with $k$ components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the cas…
Tensor Decomposition