Root Ridge Leverage Score Sampling for ℓp Subspace Approximation

The ℓp 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 = ∞). 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 + ε) relative error for a small constant ε.

We obtain an algorithm for constructing a strong coreset for ℓp subspace approximation of size Õ(kε -4/p ) for p < 2 and Õ(k p/2 ε -p ) for p > 2. This offers the following improvements over prior work:

• We construct the first strong coresets with nearly optimal dependence on k for all p = 2. In prior work, [SW18] constructed coresets of modified points with a similar dependence on k, while [HV20] constructed true coresets with polynomially worse dependence on k.

• We recover or improve the best known ε dependence for all p. In particular, for p > 2, the [SW18] coreset of modified points had a dependence of ε -p 2 /2 and the [HV20] coreset had a dependence of ε -3p .

Our algorithm is based on sampling by root ridge leverage scores, which admits fast algorithms, especially for sparse or structured matrices. Our analysis completely avoids the use of the representative subspace theorem [SW18], which is a critical component of all prior dimension-independent coresets for ℓp subspace approximation.

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