“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.
Nike Sun (UC Berkeley)
May 21, 2018
4:00 PM - 5:00 PM
More information available at: