Simple Models for Noisy Tensors and Their Properties

Andrea Montanari
Stanford University


I will consider simple models for random tensors with independent entries and survey progress on two related questions.
First, assuming that the mean of this tensor is of rank one, how well can we estimate this mean from a single sample
of the whole tensor.
Second, assuming the mean is zero (pure noise tensor), can we find an approximate solution of the optimization problem
that defines the tensor injective norm? For both problems there exist regimes in which the problem appear to be not solvable in polynomial time, and precise conjectures on the tractability boundaries.


Back to Workshop IV: Efficient Tensor Representations for Learning and Computational Complexity