Emmanuel Candes
Stanford University

Some Recent Advances in the Theory of Low-rank Modeling

Abstract: Inspired by the success of compressive sensing, the last three years have seen an explosion of research in the theory of low-rank modeling. By now, we have results stating that it is possible to recover certain low-rank matrices from a minimal number of entries -- or of linear functionals -- by tractable convex optimization. We further know that these methods are robust vis a vis additive noise and even outliers. In a different direction, researchers have developed computationally tractable methods for clustering high-dimensional data points that are assumed to be drawn from multiple low-dimensional linear subspaces. This talk will survey some exciting results in these areas.


Ken Clarkson
IBM Almaden Research Center

Sublinear Optimization for Machine Learning, and its Relatives

Abstract: In recent work, Elad Hazan, David Woodruff, and I have shown that some classical algorithmic problems of machine learning can be solved approximately, with provable bounds that hold with high probability. Moreover, our algorithms are sublinear, that is, they do not need to touch all the data. Specifically, for a set of points a_1...a_n in d dimensions, or equivalently an n by d matrix A, we show that finding a d-vector x that approximately maximizes the margin min_i a_i dot x can be done in O(n+d)/epsilon^2 time, up to logarithmic factors, where epsilon>0 is an additive approximation parameter. We have a similar result for the MEB problem, of finding the Minimum Enclosing Ball containing the input. Our algorithm is a primal-dual version of the classical perceptron training algorithm, in which both the primal and the dual variables are updated using randomization. We also show that our approach extends to kernelized versions of these problems, for some popular kernels. In the course of its operations our algorithm finds a subset of O~(1/epsilon^2) rows of A, and the same number of columns, that determine the solution we find. The rows of A are a *coreset* of the data points, while the column subset amounts to a kind a special-purpose feature selection. Thus a kind of "low rank" subset of the data matrix determines our solution. I will try to relate these results to prior work on sketching, sampling, and sparsification for data analysis.


Petros Drineas
Rensselear Polytechnic Institute

Randomized Algorithms for Low-Rank Approximations and Data Applications

Abstract: The introduction of randomization into the design and analysis of algorithms for common matrix problems (such as matrix multiplication, least-squares regression, the Singular Value Decomposition (SVD), etc.) over the last decade has provided a novel paradigm and complementary perspective to traditional numerical linear algebra approaches to matrix computations. In this talk, we will provide an overview of this approach, including how it can be used to approximate problems ranging from matrix multiplication and the SVD of matrices to approximately solving least-squares problems and systems of linear equations. In addition, application of these algorithms to large-scale data analysis will also be discussed.