2017/01/09 by Huamin Li, George C. Linderman, Arthur Szlam +4 · 61 citations
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Applied mathematics #Computation #Computer science #Convergence (economics) #Eigenvalues and eigenvectors #Electromagnetic Scattering and Analysis #Lanczos algorithm #Lanczos resampling #MATLAB #Mathematical optimization #Mathematics #Rank (graph theory) #Singular spectrum analysis #Singular value #Singular value decomposition #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · open access · doi:10.1145/3004053
published in ACM Transactions on Mathematical Software 43(3), 1-14 (Association for Computing Machinery)
openalex publication_date 2017/01/09 · openalex created_date 2017/01/13 · openalex updated_date 2026/08/01
Recent years have witnessed intense development of randomized methods for low-rank approximation. These methods target principal component analysis and the calculation of truncated singular value decompositions. The present article presents an essentially black-box, foolproof implementation for Mathworks' MATLAB, a popular software platform for numerical computation. As illustrated via several tests, the randomized algorithms for low-rank approximation outperform or at least match the classical deterministic techniques (such as Lanczos iterations run to convergence) in basically all respects: accuracy, computational efficiency (both speed and memory usage), ease-of-use, parallelizability, and reliability. However, the classical procedures remain the methods of choice for estimating spectral norms and are far superior for calculating the least singular values and corresponding singular vectors (or singular subspaces).