On Unbiased Low-Rank Approximation with Minimum Distortion

We describe an algorithm for sampling a low-rank random matrix Q that best approximates a fixed target matrix Pn× m in the following sense: Q is unbiased, i.e., E[Q] = P; rank(Q)≤ r; and Q minimizes the expected Frobenius norm error E\|P-Q\|F². Our algorithm mirrors the solution to the efficient unbiased sparsification problem for vectors, except applied to the singular components of the matrix P. Optimality is proven by showing that our algorithm matches the error from an existing lower bound.