# Dimensionality Reduction for Sum-of-Distances Metric

arXiv: https://arxiv.org/abs/1912.12003 · HTML: https://mlsanity.com/paper/1912.12003/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Dec 2019.

## Built on by (most cited first, 7 of 7)

- [Almost Linear Constant-Factor Sketching for ℓ1 and Logistic Regression](https://mlsanity.com/paper/2304.00051/) (2023)
- [An Empirical Evaluation of k-Means Coresets](https://mlsanity.com/paper/2207.00966/) (2022)
- [Efficient Algorithms For Fair Clustering with a New Fairness Notion](https://mlsanity.com/paper/2109.00708/) (2021)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Improved Coresets for Euclidean k-Means](https://mlsanity.com/paper/2211.08184/) (2022)
- [Coresets for Multiple ℓp Regression](https://mlsanity.com/paper/2406.02432/) (2024)
- [k-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation](https://mlsanity.com/paper/2507.14631/) (2025)

## Abstract (arXiv)

We give a dimensionality reduction procedure to approximate the sum of distances of a given set of n points in Rd to any "shape" that lies in a k-dimensional subspace. Here, by "shape" we mean any set of points in Rd. Our algorithm takes an input in the form of an n × d matrix A, where each row of A denotes a data point, and outputs a subspace P of dimension O(k3/ε6) such that the projections of each of the n points onto the subspace P and the distances of each of the points to the subspace P are sufficient to obtain an ε-approximation to the sum of distances to any arbitrary shape that lies in a k-dimensional subspace of Rd. These include important problems such as k-median, k-subspace approximation, and (j,l) subspace clustering with j · l ≤ k. Dimensionality reduction reduces the data storage requirement to (n+d)k3/ε6 from nnz(A). Here nnz(A) could potentially be as large as nd. Our algorithm runs in time nnz(A)/ε2 + (n+d)poly(k/ε), up to logarithmic factors. For dense matrices, where nnz(A) ≈ nd, we give a faster algorithm, that runs in time nd + (n+d)poly(k/ε) up to logarithmic factors. Our dimensionality reduction algorithm can also be used to obtain poly(k/ε) size coresets for k-median and (k,1)-subspace approximation problems in polynomial time.