A Caltech Library Service

Analyzing Tensor Power Method Dynamics in Overcomplete Regime

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.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Additional Information:© 2017 Animashree Anandkumar, Rong Ge, and Majid Janzamin. License: CC-BY 4.0, see 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.
Funding AgencyGrant Number
Microsoft ResearchUNSPECIFIED
Office of Naval Research (ONR)N00014-14-1-0665
Army Research Office (ARO)W911NF-13-1-0084
Air Force Office of Scientific Research (AFOSR)FA9550-15-1-0221
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81619
Deposited By: Tony Diaz
Deposited On:20 Sep 2017 18:16
Last Modified:03 Oct 2019 18:45

Repository Staff Only: item control page