A fast randomized algorithm for the approximation of matrices (Q952399)

The authors propose a randomized procedure that, given an \(m \times n\) matrix \(A\) and a positive integer \(k\), approximates \(A\) with a matrix \(Z\) of rank \(k\). The algorithm relies on applying a structured \(l \times m\) random matrix \(R\) to each column of \(A\), where \(l\) is an integer near to, but greater than \(k\). The structure of \(R\) allows us to apply it to arbitrary \(m \times l\) vector at a cost proportional to \(m \log(l)\); the resulting procedure can construct a rank -\(k\) approximation \(Z\) from the entries of \(A\) at a cost proportional to \(mn \log(k)+l^2(m+n)\). The authors prove several bounds on the accuracy of the algorithm. The proposed algorithm operates reliably independently of the structure of the matrix \(A\), can access each column of \(A\) independently and at most twice, and parallelizes naturally. Numerical examples are also provided.