Multiplicative Rank-1 Approximation using Length-Squared Sampling

We show that the span of Omega(1/(epsilon)4) rows of any matrix A subset of R-nxd sampled according to the length-squared distribution contains a rank-1 matrix (A) over tilde such that parallel to A - (A) over tilde parallel to(2)(F) <= (1+epsilon)center dot parallel to A -pi(1) (A)parallel to(2)(F), where pi(1)(A) denotes the best rank-1 approximation of A under the Frobenius norm. Length-squared sampling has previously been used in the context of rank-k approximation. However, the approximation obtained was additive in nature. We obtain a multiplicative approximation albeit only for rank-1 approximation.