Skip to main content

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Author(s): Bhaskara, Aditya; Charikar, Moses; Vijayaraghavan, Aravindan

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBhaskara, Aditya-
dc.contributor.authorCharikar, Moses-
dc.contributor.authorVijayaraghavan, Aravindan-
dc.identifier.citationBhaskara, Aditya, Moses Charikar, and Aravindan Vijayaraghavan. "Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability." In Proceedings of The 27th Conference on Learning Theory, 35 (2014): 742-778.en_US
dc.description.abstractWe give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: given a tensor whose decomposition satisfies a robust form of Kruskal’s rank condition, we prove that it is possible to approximately recover the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error. Kruskal’s theorem has found many applications in proving the identifiability of parameters for various latent variable models and mixture models such as Hidden Markov models, topic models etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings – an essential first step towards efficient learning algorithms. Our methods also apply to the “overcomplete” case, which has proved challenging in many applications. Given the importance of Kruskal’s theorem in the tensor literature, we expect that our robust version will have several applications beyond the settings we explore in this work.en_US
dc.format.extent742 - 778en_US
dc.relation.ispartofProceedings of The 27th Conference on Learning Theoryen_US
dc.relation.ispartofseriesProceedings of Machine Learning Research;-
dc.rightsFinal published version. This is an open access article.en_US
dc.titleUniqueness of Tensor Decompositions with Applications to Polynomial Identifiabilityen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
UniquenessTensorDecompositionPolynomIdentifiability.pdf517.47 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.