Fast and Memory Optimal Low-Rank Matrix Approximation
In this paper, we revisit the problem of constructing a near-optimal rank k approximation of a matrix M ∈ [0, 1]   m×n under the streaming data model where the columns of M are revealed sequentially. We present SLA (Streaming Low-rank Approximation), an algorithm that is asymptotically accurate, when
is the (k + 1)-th largest singular value of M . This means that its average mean-square error converges to 0 as m and n grow large (i.e.,
with high probability, whereM (k)  and M (k) denote the output of SLA and the optimal rank k approximation of M , respectively). Our algorithm makes one pass on the data if the columns of M are revealed in a random order, and two passes if the columns of M arrive in an arbitrary order. To reduce its memory footprint and complexity, SLA uses random sparsification, and samples each entry of M with a small probability δ. In turn, SLA is memory optimal as its required memory space scales as k(m+n), the dimension of its output. Furthermore, SLA is computationally efficient as it runs in O(δkmn) time (a constant number of operations is made for each observed entry of M ), which can be as small as O(k log(m) 4 n) for an appropriate choice of δ and if n ≥ m.
Let $M^k$ be the best rank $k$ approximation to $M$.1. The right way to evaluating the approximation error is contrasting $|| M - \tilde{M}^k ||$ with $|| M - M^k||$, rather than contrasting $|| M^k - \tilde{M}^k ||$ to $mn$.That $|| M^k - \tilde{M}^k || = o(mn)$ does not indicate convergence! E.g. Let m=n and $||M|| = O(n^2)$ by this paper's assumption. Assume the singular values decays slowly in that $\sigma_{max}^2 = c \sigma_{min}^2$ for a constant $c$. Then $||M^k||_F^2 < k \sigma_{max}^2 = k c \sigma_{min}^2 < k c n^{-1} ||M||_F^2 = O(kn) = o(n^2)$. This indicates that even the all-zero matrix satisfies this paper's error bound: $|| 0 - M^k ||_F^2 = o(n^2)$. 2. This paper proves an IMPOSSIBLE convergence bound. Assume that the 1st to the 2k-th singular values are equal. Any among the first 2k principal components cannot be distinguished from each other [2]. Thus $\tilde{M}^k$ can be entirely different from $M^k$, which means the impossibility of convergence. (In fact, in this case, $\tilde{M}^k$ converges to $M^k$ with ZERO measure.) Interestingly, the authors tell us their streaming PCA converges to $M^k$. 3. Stronger results have been established by Boutsidis & Woodruff [1].[1] arXiv:1504.06729v1, April 25, 2015. Communication-optimal Distributed Principal Component Analysis in the Column-partition Model. Boutsidis, Christos, Woodruff, David P.[2] Topics in matrix analysis. RA Horn, CR Johnson.