Size / / /
Loading Events
Probability Seminar

“Spectral Algorithms for Tensor Completion”


There is an unknown tensor, say an 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 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.


Probability Seminar
Nike Sun (UC Berkeley)
May 21, 2018
4:00 PM - 5:00 PM
More information available at:


Sequoia Hall Room 200
Stanford University Department of Mathematics
SU Home Maps & Directions Search Stanford Terms of Use Copyright Complaints
© Stanford University, Stanford, California 94305