Speaker: Petros Drineas
Rensselaer Polytechnic Institute
Title: Sampling algorithms for L2 regression and applications
Abstract: L2 regression, also known as the least squares approximation problem,
and more generally Lp regression, are fundamental problems that have
numerous applications in mathematics and statistical data analysis.
Recall that the over-constrained L2 regression problem takes as input
an n x d matrix A, where n > d, and an n-vector b, and it returns as
output a d-vector x such that ||Ax-b||_2 is minimized. Several
randomized algorithms for this problem, each of which provides a
relative-error approximation to the exact solution, are described. The
first algorithm applies novel ``subspace sampling'' probabilities to
randomly sample constraints and thus construct a coreset for the L2
regression problem. The second algorithm applies a random projection
and uses a ``fast'' version of the Johnson-Lindenstrauss lemma to
obtain an efficient approximation to the L2 regression problem. In
this talk we will also discuss how such ideas can be applied to the
Column Subset Selection Problem (CSSP).
This is joint work with C. Boutsidis, M.W. Mahoney, S. (Muthu)
Muthukrishnan, and Tamas Sarlos.