2019/12/27 by Zhili Feng, Praneeth Kacham, Feng, Zhili +3 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1912.12003
27 pages, 2 figures. To appear at ICML 2021
arxiv created 2021/06/24 · arxiv updated 2021/06/25
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.