Matrix Approximation and Projective Clustering via Volume Sampling

Frieze et al. [17] proved that a small sample of rows of a given matrix A contains a low-rank approximation D that minimizes parallel to A - D parallel to(F) to within small additive error, and the sampling can be done efficiently using just two passes over the matrix [12]. In this paper, we generalize this result in two ways. First, we prove that the additive error drops exponentially by iterating the sampling in an adaptive manner. Using this result, we give a pass-efficient algorithm for computing low-rank approximation with reduced additive error. Our second result is that using a natural distribution on subsets of rows (called volume sampling), there exists a subset of k rows whose span contains a factor (k + 1) relative approximation and a subset of k + k(k + 1)/epsilon rows whose span contains a 1 + epsilon relative approximation. The existence of such a small certificate for multiplicative low-rank approximation leads to a PTAS for the following projective clustering problem: Given a set of points P in R-d, and integers k, j, find a set of j subspaces F-1, ... , F-j, each of dimension at most k, that minimize Sigma(p is an element of P) min(i) d(p, F-i)(2).