Anandkumar, Animashree and Ge, Rong and Janzamin, Majid (2017) Analyzing Tensor Power Method Dynamics in Overcomplete Regime. Journal of Machine Learning Research, 18 (22). pp. 1-40. ISSN 1533-7928. https://resolver.caltech.edu/CaltechAUTHORS:20170920-110910164
![]() |
PDF
- Published Version
Creative Commons Attribution. 470kB |
![]() |
PDF
- Submitted Version
See Usage Policy. 424kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170920-110910164
Abstract
We present a novel analysis of the dynamics of tensor power iterations in the overcomplete regime where the tensor CP rank is larger than the input dimension. Finding the CP decomposition of an overcomplete tensor is NP-hard in general. We consider the case where the tensor components are randomly drawn, and show that the simple power iteration recovers the components with bounded error under mild initialization conditions. We apply our analysis to unsupervised learning of latent variable models, such as multi-view mixture models and spherical Gaussian mixtures. Given the third order moment tensor, we learn the parameters using tensor power iterations. We prove it can correctly learn the model parameters when the number of hidden components k is much larger than the data dimension d, up to k=o(d^(1.5)). We initialize the power iterations with data samples and prove its success under mild conditions on the signal-to-noise ratio of the samples. Our analysis significantly expands the class of latent variable models where spectral methods are applicable. Our analysis also deals with noise in the input tensor leading to sample complexity result in the application to learning latent variable models.
Item Type: | Article | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||||
Additional Information: | © 2017 Animashree Anandkumar, Rong Ge, and Majid Janzamin. License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. A. Anandkumar is supported in part by Microsoft Faculty Fellowship, NSF Career award CCF-1254106, NSF award CCF-1219234, ONR award N00014-14-1-0665, ARO YIP award W911NF-13-1-0084, and AFOSR YIP award FA9550-15-1-0221. M. Janzamin is supported by NSF Award CCF-1219234. | ||||||||||||||
Funders: |
| ||||||||||||||
Subject Keywords: | tensor decomposition, tensor power iteration, overcomplete representation, unsupervised learning, latent variable models | ||||||||||||||
Issue or Number: | 22 | ||||||||||||||
Record Number: | CaltechAUTHORS:20170920-110910164 | ||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170920-110910164 | ||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||
ID Code: | 81619 | ||||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||||
Deposited By: | Tony Diaz | ||||||||||||||
Deposited On: | 20 Sep 2017 18:16 | ||||||||||||||
Last Modified: | 03 Oct 2019 18:45 |
Repository Staff Only: item control page