2018/04/20 by Elvar K. Bjarkason, Bjarkason, Elvar K. · 3 citations
Computer Science · Engineering · Mathematics · #15A18 #35R30 #65F30 #68W20 #86A22 #Algorithm #Artificial intelligence #Blind Source Separation Techniques #Block (permutation group theory) #Computer science #FOS: Mathematics #Iterative method #Krylov subspace #Mathematics #Matrix (chemical analysis) #Numerical Analysis (math.NA) #Rank (graph theory) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Subspace topology
paper · pdf · doi:10.48550/arxiv.1804.07531
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2018/04/20 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
This paper describes practical randomized algorithms for low-rank matrix\napproximation that accommodate any budget for the number of views of the\nmatrix. The presented algorithms, which are aimed at being as pass efficient as\nneeded, expand and improve on popular randomized algorithms targeting efficient\nlow-rank reconstructions. First, a more flexible subspace iteration algorithm\nis presented that works for any views v \≥ 2, instead of only allowing an\neven v. Secondly, we propose more general and more accurate single-pass\nalgorithms. In particular, we propose a more accurate memory efficient\nsingle-pass method and a more general single-pass algorithm which, unlike\nprevious methods, does not require prior information to assure near peak\nperformance. Thirdly, combining ideas from subspace and single-pass algorithms,\nwe present a more pass-efficient randomized block Krylov algorithm, which can\nachieve a desired accuracy using considerably fewer views than that needed by a\nsubspace or previously studied block Krylov methods. However, the proposed\naccuracy enhanced block Krylov method is restricted to large matrices that are\neither accessed a few columns or rows at a time. Recommendations are also given\non how to apply the subspace and block Krylov algorithms when estimating either\nthe dominant left or right singular subspace of a matrix, or when estimating a\nnormal matrix, such as those appearing in inverse problems. Computational\nexperiments are carried out that demonstrate the applicability and\neffectiveness of the presented algorithms.\n