Efficient matrix computations via subsampling sketches

This dissertation investigates the improvement and the application of subsampling sketching, a dimension reduction technique, in various statistical contexts. Firstly, we propose a framework, accumulative sketching, which encompasses Gaussian sketching and subsampling sketching as special cases, for approximate matrix multiplication (AMM). Theoretical analysis and empirical experiments demonstrate that our approach achieves a balance between computational efficiency and statistical accuracy, enhancing tasks such as generalized linear regression, randomized SVD, and kernel ridge regression. Furthermore, we develop efficient algorithms for accurately approximating statistical leverage scores in kernel ridge regression, resulting in significant improvements in efficiency of subsampling sketching compared to existing methods. We extend this technique to empirical risk minimization in reproducing kernel Hilbert spaces (RKHS), ensuring the adaptation maintains the minimax-optimal error rate of kernel estimators. Overall, our research offers potent tools for efficiently computing large-scale matrices via subsampling sketches in various settings while still preserving the statistical accuracy.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Statistics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Chen, Yifan

Contributors dc:contributor

• Yang, Yun
• Chen, Xiaohui
• Liang, Feng
• Zhu, Ruoqing

• Sketching
• Approximate Matrix Multiplication
• Randomized Algorithms
• Kernel Methods
• Importance Sampling

Statement dc:rights

• Copyright 2023 Yifan Chen

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/121209

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F121209