Computing Approximate ℓp Sensitivities

Recent works in dimensionality reduction for regression tasks have introduced the notion of sensitivity, an estimate of the importance of a specific datapoint in a dataset, offering provable guarantees on the quality of the approximation after removing low-sensitivity datapoints via subsampling. However, fast algorithms for approximating ℓp sensitivities, which we show is equivalent to approximate ℓp regression, are known for only the ℓ2 setting, in which they are termed leverage scores. In this work, we provide efficient algorithms for approximating ℓp sensitivities and related summary statistics of a given matrix. In particular, for a given n × d matrix, we compute α-approximation to its ℓ1 sensitivities at the cost of O(n/α) sensitivity computations. For estimating the total ℓp sensitivity (i.e. the sum of ℓp sensitivities), we provide an algorithm based on importance sampling of ℓp Lewis weights, which computes a constant factor approximation to the total sensitivity at the cost of roughly O(√d) sensitivity computations. Furthermore, we estimate the maximum ℓ1 sensitivity, up to a √d factor, using O(d) sensitivity computations. We generalize all these results to ℓp norms for p > 1. Lastly, we experimentally show that for a wide class of matrices in real-world datasets, the total sensitivity can be quickly approximated and is significantly smaller than the theoretical prediction, demonstrating that real-world datasets have low intrinsic effective dimensionality.