Matrix decompositions using sub-Gaussian random matrices

DOI10.1093/IMAIAI/IAY017MaRDI QIDQ5006500zbMATH OpenOpenAlexFDO

Authors Yariv Aizenbud, Amir Averbuch

Publication date 16 August 2021

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

Johnson-Lindenstrauss lemmalow-rank approximationLU decompositionoblivious subspace embeddingrandom matricessparse matricessub-Gaussian matricesSVD

Mathematics Subject Classification ID

Factorization of matrices (15A23) Random matrices (probabilistic aspects) (60B20)

Abstract: In recent years, several algorithms, which approximate matrix decomposition, have been developed. These algorithms are based on metric conservation features for linear spaces of random projection types. We show that an i.i.d sub-Gaussian matrix with large probability to have zero entries is metric conserving. We also present a new algorithm, which achieves with high probability, a rank $r$ decomposition approximation for an $mimesn$ matrix that has an asymptotic complexity like state-of-the-art algorithms. We derive an error bound that does not depend on the first $r$ singular values. Although the proven error bound is not as tight as the state-of-the-art bound, experiments show that the proposed algorithm is faster in practice, while getting the same error rates as the state-of-the-art algorithms get.

Recommendations

• A randomized algorithm for the decomposition of matrices
• Randomized generalized singular value decomposition
• Randomized LU decomposition
• Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
• A fast randomized algorithm for the approximation of matrices

Cited in

(12)

• Randomized LU decomposition
• Randomized LU decomposition using sparse projections
• Randomized block Krylov subspace methods for trace and log-determinant estimators
• Single-pass randomized QLP decomposition for low-rank approximation
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• Sublinear-time quadratic minimization via spectral decomposition of matrices
• Subspaces analysis for random projection UTV framework
• The Steerable Graph Laplacian and its Application to Filtering Image Datasets
• Fast heat transfer simulation for laser powder bed fusion
• The Hadamard decomposition problem
• Estimation of local geometric structure on manifolds from noisy data
• Randomized low-rank approximations beyond Gaussian random matrices

This page was built for publication: Matrix decompositions using sub-Gaussian random matrices

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