2009.09.14 | Else Magård

Title: Coresets and Sketches for High Dimensional Subspace Approximation Problems

Speaker: Morteza Monemizadeh, University of Dortmund

Abstract:

We consider the problem of approximating a set $P$ of $n$ points in $\\Re^d$ by a $j$-dimensional subspace under the $\\ell_p$ measure, in which we wish to minimize the sum of $\\ell_p$ distances from each point of $P$ to this subspace. More generally, the $F_q(\\ell_{\\mathfrak{p}})$-subspace approximation problem asks for a $j$-subspace that minimizes the sum of $q$th powers of $\\ell_{\\mathfrak{p}}$-distances to this subspace, up to a multiplicative factor of $(1+\\epsilon)$.

We develop techniques for subspace approximation, regression, and matrix approximation that can be used to deal with massive data sets in high dimensional spaces. In particular, we develop coresets and sketches, i.e. small space representations that approximate the input point set $P$ with respect to the subspace approximation problem. Among the results we propose a dimensionality reduction method for various clustering measures, strong coreset, ptas and streaming algorithms in bounded and unbounded precision model for $F_1(\\ell_2)$-subspace approximation in high-dimensional spaces.

Joint work with:

Dan Feldman
Christian Sohler
David P. Woodruff