Efficient Bounds and Estimates for Canonical Angles in Randomized Subspace Approximations

arXiv2211.04676MaRDI QIDQ6416635FDOQ6416635

P. G. Martinsson, Yuji Nakatsukasa, Yijun Dong

Publication date: 8 November 2022

Abstract: Randomized subspace approximation with "matrix sketching" is an effective approach for constructing approximate partial singular value decompositions (SVDs) of large matrices. The performance of such techniques has been extensively analyzed, and very precise estimates on the distribution of the residual errors have been derived. However, our understanding of the accuracy of the computed singular vectors (measured in terms of the canonical angles between the spaces spanned by the exact and the computed singular vectors, respectively) remains relatively limited. In this work, we present bounds and estimates for canonical angles of randomized subspace approximation that can be computed efficiently either a priori or a posterior. Under moderate oversampling in the randomized SVD, our prior probabilistic bounds are asymptotically tight and can be computed efficiently, while bringing a clear insight into the balance between oversampling and power iterations given a fixed budget on the number of matrix-vector multiplications. The numerical experiments demonstrate the empirical effectiveness of these canonical angle bounds and estimates on different matrices under various algorithmic choices for the randomized SVD.

Has companion code repository: https://github.com/dyjdongyijun/randomized_subspace_approximation

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Randomized algorithms (68W20)

This page was built for publication: Efficient Bounds and Estimates for Canonical Angles in Randomized Subspace Approximations

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