We prove that any real matrix A contains a subset of at most
4k/\eps + 2k \log(k+1) rows whose span ``contains" a matrix of
rank at most k with error only (1+\eps) times the error of the
best rank-k approximation of A. This leads to an algorithm to
find such ... more >>>