Nearly Linear Sparsification of Lp Subspace Approximation

Data Science Seminar

David Woodruff (Carnegie Mellon)

Abstract

The Lp subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane problem (p = 1), principal component analysis (p = 2), and the center hyperplane problem (p = infty). A popular approach to cope with the NP-hardness of this problem is to compute a strong coreset, which is a small weighted subset of the input points which simultaneously approximates the cost of every k-dimensional subspace, typically to (1+eps)-relative error for a small constant ε.

We obtain the first algorithm for constructing a strong coreset for Lp subspace approximation with a nearly optimal dependence on the rank parameter k, obtaining a nearly linear bound of k for p< 2, and k^{p/2} for  p>2. Prior constructions either achieved a similar size bound but produced a coreset with a modification of the original points, or produced a coreset of the original points but lost poly(k) factors in the coreset size.

Our techniques also lead to the first nearly optimal online strong coresets for Lp subspace approximation with similar bounds as the offline setting. All prior approaches lose poly(k) factors in this setting, even when allowed to modify the original points.

Based on joint work with Taisuke Yasuda.