CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20170920-110910164

[img] PDF - Published Version
Creative Commons Attribution.

459Kb
[img] PDF - Submitted Version
See Usage Policy.

414Kb

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:
URLURL TypeDescription
http://www.jmlr.org/papers/v18/15-486.htmlPublisherArticle
https://arxiv.org/abs/1411.1488arXivDiscussion Paper
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:
Funding AgencyGrant Number
Microsoft ResearchUNSPECIFIED
NSFCCF-1254106
NSFCCF-1219234
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: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