Input Sparsity and Hardness for Robust Subspace Approximation.

Kenneth L. Clarkson David P. Woodruff

Published in: FOCS (2015)

Keyphrases

high dimensional
input data
low rank representation
data sets
special case
np hard
principal component analysis
computational complexity
low dimensional
computationally efficient
least squares
linear discriminant analysis
error bounds
approximation algorithms
subspace methods