Multiplicative Rank-1 Approximation using Length-Squared Sampling

Abstract

We show that the span of rows of any matrix A ⊂ ℝn×d sampled according to the length-squared distribution contains a rank-1 matrix à such that , where π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.