Symmetric Tensor Completion from Multilinear Entries and Learning Product Mixtures over the Hypercube

Tselil Schramm, Benjamin Weitz

We give an algorithm for completing an order-$m$ symmetric low-rank tensor from its multilinear entries in time roughly proportional to the number of tensor entries. We apply our t…