  We give a robust version of the celebrated result of Kruskal on the
uniqueness of tensor decompositions: we prove that given a tensor whose
decomposition satisfies a robust form of Kruskal's rank condition, 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.
This polynomial identifiability is an essential first step towards efficient
learning algorithms for these models.
  Recently, algorithms based on tensor decompositions have been used to
estimate the parameters of various hidden variable models efficiently in
special cases as long as they satisfy certain "non-degeneracy" properties. Our
methods give a way to go beyond this non-degeneracy barrier, and establish
polynomial identifiability of the parameters under much milder conditions.
Given the importance of Kruskal's theorem in the tensor literature, we expect
that this robust version will have several applications beyond the settings we
explore in this work.
