A Precise Performance Analysis of the Randomized Singular Value Decomposition

Akhtiamov, Danil; Ghane, Reza; Hassibi, Babak

Permalink

https://hdl.handle.net/2142/130319 Copy

Description

Title

A Precise Performance Analysis of the Randomized Singular Value Decomposition

Author(s)

• Akhtiamov, Danil
• Ghane, Reza
• Hassibi, Babak

Issue Date

2025-09-17

Keyword(s)

• Randomized singular value decomposition
• RSVD
• Randomized SVD
• Approximation error
• Gaussian comparison inequalities

Abstract

The Randomized Singular Value Decomposition (RSVD) is a widely used algorithm for efficiently computing low-rank approximations of large matrices, without the need to construct a full-blown SVD. Of interest, of course, is the approximation error of RSVD compared to the optimal low-rank approximation error obtained from the SVD. While the literature provides various upper and lower error bounds for RSVD, in this paper we derive precise asymptotic expressions that characterize its approximation error as the matrix dimensions grow to infinity. Our expressions depend only on the singular values of the matrix, and we evaluate them for two important matrix ensembles: those with power law and bilevel singular value distributions. Our results aim to quantify the gap between the existing theoretical bounds and the actual performance of RSVD. Furthermore, we extend our analysis to polynomial-filtered RSVD, deriving performance characterizations that provide insights into optimal filter selection.

Publisher

Allerton Conference on Communication, Control, and Computing

Series/Report Name or Number

2025 61st Allerton Conference on Communication, Control, and Computing Proceedings

ISSN

2836-4503

Type of Resource

Text

Genre of Resource

Conference Paper/Presentation

Language

eng

Handle URL

https://hdl.handle.net/2142/130319&&

Copyright and License Information

Copyright 2025 owned by the authors.

Owning Collections