Subspace-Orbit Randomized Decomposition for Low-Rank Matrix Approximations

DOI10.1109/TSP.2018.2853137MaRDI QIDQ4622339zbMATH OpenWikidataFDO

Authors Maboud Farzaneh Kaloorazi, Rodrigo C. de Lamare

Publication date 12 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.00462

Mathematics Subject Classification ID

Factorization of matrices (15A23) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: An efficient, accurate and reliable approximation of a matrix by one of lower rank is a fundamental task in numerical linear algebra and signal processing applications. In this paper, we introduce a new matrix decomposition approach termed Subspace-Orbit Randomized singular value decomposition (SOR-SVD), which makes use of random sampling techniques to give an approximation to a low-rank matrix. Given a large and dense data matrix of size $mimesn$ with numerical rank $k$, where $kllextminm,n$, the algorithm requires a few passes through data, and can be computed in $O(mnk)$ floating-point operations. Moreover, the SOR-SVD algorithm can utilize advanced computer architectures, and, as a result, it can be optimized for maximum efficiency. The SOR-SVD algorithm is simple, accurate, and provably correct, and outperforms previously reported techniques in terms of accuracy and efficiency. Our numerical experiments support these claims.

Cited in

(6)

• An efficient algorithm for computing the approximate t-URV and its applications
• Single-pass randomized QLP decomposition for low-rank approximation
• Background subtraction using adaptive singular value decomposition
• Single-pass randomized algorithms for LU decomposition
• An efficient randomized QLP algorithm for approximating the singular value decomposition
• Pass-efficient truncated UTV for low-rank approximations

This page was built for publication: Subspace-Orbit Randomized Decomposition for Low-Rank Matrix Approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4622339)