Multiplicative Rank-1 Approximation using Length-Squared Sampling

We show that the span of $\mathrm{\Omega }(\frac{1}{{\epsilon }^4})$ rows of any matrix $A\subset {\mathbb{R}}^{n\times d}$ sampled according to the length-squared distribution contains a rank-$1$ matrix $\tilde{A}$ such that $||A - \tilde{A}||_F^2 \leq (1 + \varepsilon) \cdot ||A - \pi_1(A)||_F^2$,where$\pi_1(A)$denotesthebestrank-$1$approximationof$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.