A randomized algorithm for the decomposition of matrices (Q617703)

Given a large real matrix \(A\in{\mathbb R}^{m\times n}\), the idea is to approximate it with a rank-\(k\) matrix that is as close as possible in the spectral norm. The authors analyse a method that starts from a random matrix \(G\in{\mathbb R}^{l\times m}\), \(k<l<\min(m,n)\) with entries that are \(N(0,1)\) Gaussian distributed. By constructing a particular rank-\(k\) approximation to \(GA\), it is possible to select \(k\) columns from \(A\) that are stored in a matrix \(B\). From these computations it is also possible to construct a matrix \(P\in{\mathbb R}^{k\times n}\). Together they lead to a rank-\(k\) matrix \(Z=BP\) that approximates \(A\). Usually \(l\) is moderately larger than \(k\). For example if \(l=k+20\) then \(\|A-Z\|\leq 10\sqrt{k(k+20)nm}\;\sigma_{k+1}\), with probability at least \(1-10^{-17}\). Here \(\sigma_{k+1}\) is the \((k+1)\)st singular value of \(A\). This \(\sigma_{k+1}\) is the error for the classical optimal rank-\(k\) approximation obtained by keeping only the \(k\) largest singular values in the the SVD of \(A\). Not only the rank-\(k\) approximant for \(A\) is computable using simple matrix-vector multiplications with \(A\) and \(A^T\), also the approximating singular value decomposition (SVD) can be obtained. The computational complexity is in general comparable to a Lanczos procedure.