Title: Smoothed Analysis of Tensor Decomposition
Speaker: Aditya Bhaskara, Google
Date: Wednesday, April 9, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Low rank decomposition of tensors is a powerful tool that can been used to learn the parameters of a variety of probabilistic mixture models. However, tensors pose significant algorithmic challenges, and tensors analogs of much of the matrix algebra toolkit are unlikely to exist because of hardness results. Efficient decomposition in the overcomplete case (where rank exceeds dimension) is particularly challenging. We introduce a smoothed analysis model for studying these questions and develop an efficient algorithm for tensor decomposition in the highly overcomplete case (rank polynomial in the dimension). In this setting, we also show that our algorithm is robust to inverse polynomial error, a property necessary for learning applications.
We use our decomposition algorithm to obtain results for learning multi-view models and mixtures of axis-aligned Gaussians where there are many more "components" than dimensions, in a smoothed analysis framework. We believe this an appealing way to analyze realistic instances of learning problems, since it allows us to overcome many of the (hardness related) limitations of using tensor methods.
Joint work with Moses Charikar, Ankur Moitra and Aravindan Vijayaraghavan
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/