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 $\tilde O\left( {k{\varepsilon ^{ - 4/p}}} \right)$ 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, [1] constructed coresets of modified points with a similar dependence on k, while [2] 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 [1] coreset of modified points had a dependence of ${\varepsilon ^{ - {p^2}/2}}$ and the [2] 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 [1], 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 [3]. All prior approaches lose poly(k) factors in this setting, even when allowed to modify the original points.

Authors

• David P. Woodruff
• Taisuke Yasuda 0002

Keywords

• Computer science
• Costs
• Approximation algorithms
• Sparse matrices
• Principal component analysis
• Leverage Scores
• Estimation Problem
• Low-rank Approximation
• Lower Bound
• Running Time
• Probability Sampling
• Normal Operation
• Singular Value Decomposition
• Constant Factor
• Random Matrix
• Additional Error
• L1-norm
• Recursive Algorithm
• Rotation Invariance
• Computational Geometry
• Low-dimensional Subspace
• Matrix Integrity
• Sampling Theorem
• Standard Gaussian
• Online Fashion
• Stream Model
• Additional Row
• Projection Matrix
• Sample Matrix
• Objective Function
• Prior Results
• Frobenius Norm
• Orthogonal Matrix
• Upper Bound
• subspace approximation
• coresets