Speaker
Description
We introduce a novel procedure for computing an SVD-type approximation of a matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$, $m\geq n$. Specifically, we propose a randomization-based algorithm that improves over the standard Randomized Singular Value Decomposition (RSVD). Most significantly, our approach, the Row-aware RSVD (R-RSVD), explicitly constructs information from the row space of $\mathbf{A}$. This leads to better approximations to $\text{Range}(\mathbf{A})$ while maintaining the same computational cost. The efficacy of the R-RSVD is supported by both robust theoretical results and extensive numerical experiments. Furthermore, we present an alternative algorithm inspired by the R-RSVD, capable of achieving comparable accuracy despite utilizing only a subsample of the rows of $\mathbf{A}$, resulting in a significantly reduced computational cost. This method, that we name the Subsample Row-aware RSVD (Rsub-RSVD), is supported by a weaker error bound compared to the ones we derived for the R-RSVD, but still meaningful as it ensures that the error remains under control. Additionally, numerous experiments demonstrate that the Rsub-RSVD trend is akin to the one attained by the R-RSVD even for small subsampling parameters. Finally, we consider the application of our schemes in two very diverse settings which share the need for the computation of singular vectors as an intermediate step: the computation of CUR decompositions by the discrete empirical interpolation method (DEIM) and the construction of reduced-order models in the Loewner framework, a data-driven technique for model reduction of dynamical systems.
