Algorithm 971

Algorithm 971: An implementation of a randomized algorithm for principal component analysis. 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).


References in zbMATH (referenced in 10 articles , 1 standard article )

Showing results 1 to 10 of 10.
Sorted by year (citations)

  1. Floater, Michael S.; Manni, Carla; Sande, Espen; Speleers, Hendrik: Best low-rank approximations and Kolmogorov (n)-widths (2021)
  2. Yurtsever, Alp; Tropp, Joel A.; Fercoq, Olivier; Udell, Madeleine; Cevher, Volkan: Scalable semidefinite programming (2021)
  3. Jaffe, Ariel; Kluger, Yuval; Linderman, George C.; Mishne, Gal; Steinerberger, Stefan: Randomized near-neighbor graphs, giant components and applications in data science (2020)
  4. Bjarkason, Elvar K.: Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views (2019)
  5. Buhr, Andreas; Smetana, Kathrin: Randomized local model order reduction (2018)
  6. Li, Huamin; Kluger, Yuval; Tygert, Mark: Randomized algorithms for distributed computation of principal component analysis and singular value decomposition (2018)
  7. Yu, Wenjian; Gu, Yu; Li, Yaohang: Efficient randomized algorithms for the fixed-precision low-rank matrix approximation (2018)
  8. H. Li, G. C. Linderman, A. Szlam, K. P. Stanton, Y. Kluger, M. Tygert: Algorithm 971: An Implementation of a Randomized Algorithm for Principal Component Analysis (2017) not zbMATH
  9. Li, Huamin; Linderman, George C.; Szlam, Arthur; Stanton, Kelly P.; Kluger, Yuval; Tygert, Mark: Algorithm 971: An implementation of a randomized algorithm for principal component analysis (2017)
  10. Tropp, Joel A.; Yurtsever, Alp; Udell, Madeleine; Cevher, Volkan: Practical sketching algorithms for low-rank matrix approximation (2017)