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 $P\in {\mathbb{C}}^{n\times m}$ in the following sense: $Q$ is unbiased, i.e., $\mathbb{E}[Q]=P$; $\mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}(Q)\le r$; and $Q$ minimizes the expected Frobenius norm error $\mathbb{E}\mathrm{\parallel }P-Q{\mathrm{\parallel }}_F^2$. 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.