This thesis proposes and analyzes randomized algorithms for solving large-scale numerical linear algebra problems. A major theme of the thesis is to extend existing randomized low-rank approximation techniques to develop fast and reliable algorithms for parameter-dependent and time-dependent problems.

In Chapter 2, we present subspace embedding properties of random matrices with Khatri-Rao product structures. These properties are fundamental for analyzing randomized numerical linear algebra algorithms. We also propose two eigenvalue solvers that leverage the structure of Khatri-Rao product random matrices, enabling us to solve eigenvalue problems efficiently and with low memory usage.

In Chapter 4, we extend randomized low-rank approximation algorithms to compress parameter-dependent matrices. We propose parameter-dependent versions of the randomized SVD and the generalized Nyström method. In particular, our algorithms do not resample the random matrix for each parameter, making them computationally attractive. Based on the theoretical guarantees presented in Chapter 3, we show that our parameter-dependent algorithms provide sub-optimal approximation guarantees. We also present numerical findings to illustrate these results.

In Chapter 5, we combine randomized low-rank approximation with time-integration schemes to obtain a low-rank approximation of the solutions of matrix differential equations. In contrast to existing methods, which typically rely on tangent space projections, our method constructs a low-rank approximation from random sketches of the discretized dynamics, making it simpler and more robust when the dynamics deviate from the tangent space. We provide error bounds and numerical results demonstrating that our method is efficient and accurate with high probability.

In Chapter 6, we analyze the use of the discrete empirical interpolation method to accelerate the evaluation of the tangent space projector in dynamical low-rank approximation when approximating solutions of matrix differential equations. Using the theory of differential inclusions, we provide guarantees on the approximation error with respect to the true solution in the continuous-time setting. We also propose a practical numerical scheme for time integration, supported by both theoretical analysis and numerical experiments showing its effectiveness.