Abstract:We present a generalization of the collaborative filtering algorithm for the task of tensor estimation, i.e. estimating a low-rank 3-order n-by-n-by-n tensor from noisy observations of randomly chosen entries in the sparse regime. Not only does the algorithm have desirable computational properties, it also provably achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Furthermore, our analysis results in high probability bounds on the infinity norm of the error, as opposed to the weaker MSE bounds achieved by previous approaches. Our proposed algorithm uses the matrix obtained from the ``flattened'' tensor to compute similarity with respect to a corresponding observation graph. The algorithm recovers the tensor with max entrywise error decaying to 0 with high probability as long as the entries are sampled uniformly at a density of Omega(n^{-3/2 + epsilon}) for any arbitrarily small epsilon > 0. This sample complexity threshold (nearly) matches a conjectured lower bound as well as the ``connectivity threshold'' of the corresponding observation graph used in our algorithm, providing a different angle to explain the conjectured lower bound.
Bio: Christina Lee Yu is an assistant professor at Cornell University in the Operations Research and Information Engineering Department. Prior to joining Cornell, she was a postdoc at Microsoft Research New England. She received her PhD and MS in Electrical Engineering and Computer Science from MIT in the Laboratory for Information and Decision Systems. She received her BS in Computer Science from California Institute of Technology. She is a recipient of the MIT Jacobs Presidential Fellowship, the NSF Graduate Research Fellowship, and the Claude E. Shannon Research Assistantship. Her research focuses on designing and analyzing scalable algorithms for processing social data based on principles from statistical inference.
.