Multiplicative Rank-1 Approximation using Length-Squared Sampling

摘要

We show that the span of Ω(1/(ε~4)) rows of any matrix A {is truely contained in} R~(n×d) sampled according to the length-squared distribution contains a rank-1 matrix A{top}~ such that || A-A{top}~||_F~2 ≤ (1+ε)·||A-π_1(A)||_F~2, 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.