“Spectral Algorithms for Tensor Completion”

There is an unknown tensor, say an *n *x *n *x *n* array. We observe a small random subset of its

entries, and wish to estimate the missing entries under a structural (low rank) assumption.

Barak and Moitra (2015) gave an SDP algorithm for completion on *n *x *n *x *n* rank-r tensors

(under some randomness assumptions) based on m >> n3/2r observed entries, with runtime

O(n15). In a somewhat more restricted setting we obtain a simpler spectral algorithm that

matches the sampling requirement m >> n3/2r, but has an improved runtime O(n6). In

this talk I will explain how the tensor completion problem is related to the problem of

“strong refutation” in random CSPs, and I will present intuition for our algorithm via the

spectral refutation algorithm of Coja-Oghlan, Goerdt, and Lanka (2004).

This is joint work with Andrea Montanari.

### Details

Probability SeminarNike Sun (UC Berkeley)

May 21, 2018

4:00 PM - 5:00 PM

More information available at:

http://mathematics.stanford.edu/probability-seminar/