Back to Search
Start Over
Matrix decompositions using sub-Gaussian random matrices.
- Source :
-
Information & Inference: A Journal of the IMA . Sep2019, Vol. 8 Issue 3, p445-469. 25p. - Publication Year :
- 2019
-
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 present a new algorithm, which achieves with high probability a rank- |$r$| singular value decomposition (SVD) approximation of an |$n \times n$| matrix and derive an error bound that does not depend on the first |$r$| singular values. Although the algorithm has an asymptotic complexity similar to state-of-the-art algorithms and 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 providing the same error rates as those of the state-of-the-art algorithms. We also show that an i.i.d. sub-Gaussian matrix with large probability of having null entries is metric conserving. This result is used in the SVD approximation algorithm, as well as to improve the performance of a previously proposed approximated LU decomposition algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 20498764
- Volume :
- 8
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Information & Inference: A Journal of the IMA
- Publication Type :
- Academic Journal
- Accession number :
- 138621843
- Full Text :
- https://doi.org/10.1093/imaiai/iay017