On the accuracy and robustness of randomised methods for matrix computations

Thesis

Randomised numerical linear algebra provides scalable and robust tools for tackling large-scale problems in the computational sciences. This thesis investigates the accuracy, stability, and robustness of various randomised algorithms, with a particular focus on low-rank matrix approximations.

We begin with a sketch-and-solve approach for approximating trailing right singular vectors of a tall matrix. Using multiplicative perturbation theory, we show that accuracy depends on the relative spectral gap. To improve efficiency, we introduce a sketch update technique that handles matrix modifications without recomputing the full sketch.

Next, we explore the Nyström method for symmetric indefinite matrices. We identify a key source of instability in the standard approach, caused by inaccurate singular value estimation in the core matrix. To address this, we propose a robust variant that truncates the core matrix based on the target rank--representing, to our knowledge, the first stable Nyström method designed for symmetric indefinite matrices.

The rest of the thesis focuses on the CUR decomposition, where a matrix is approximated using a subset of its rows and columns. We analyse both its accuracy and numerical stability, emphasising the role of dependent index selection and the benefits of oversampling. Our theoretical results lead to a numerically stable CUR implementation, highlighting how oversampling mitigates the effects of poorly chosen indices.

Finally, we introduce two efficient, rank-adaptive algorithms--AdaCUR and FastAdaCUR--for low-rank approximation of parameter-dependent matrices via CUR decomposition. These methods aim to reuse previously selected indices across parameter values, thereby greatly reducing computational cost. While AdaCUR offers adaptive rank selection and error control, FastAdaCUR achieves faster runtimes at the expense of robustness.

Authors: Park, T

• DOI: 10.5287/ora-2abdbeovg
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: numerical linear algebra; matrix perturbation theory; numerical stability; randomised algorithms; low-rank approximation; singular vector estimation
• Subjects: Numerical analysis