Input Sparsity and Hardness for Robust Subspace Approximation

Kenneth L. Clarkson, David P. Woodruff

In the subspace approximation problem, we seek a k-dimensional subspace F of R^d that minimizes the sum of p-th powers of Euclidean distances to a given set of n points a_1, ..., a…