Multiplicative Rank-1 Approximation using Length-Squared Sampling

Abstract

We show that the span of $\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\le (1+\epsilon )\cdot ||A-{\pi }_1(A)|{|}_F^2$, 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.

A section on open problems added in the new version