Dimensionality Reduction for Sum-of-Distances Metric

Zhili Feng, Praneeth Kacham, David P. Woodruff

We give a dimensionality reduction procedure to approximate the sum of distances of a given set of $n$ points in $R^d$ to any "shape" that lies in a $k$-dimensional subspace. Here,…