Efficient matrix computations via subsampling sketches

Chen, Yifan

Permalink

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

Description

Title

Efficient matrix computations via subsampling sketches

Author(s)

Chen, Yifan

Issue Date

2023-07-12

Director of Research (if dissertation) or Advisor (if thesis)

Yang, Yun

Doctoral Committee Chair(s)

Yang, Yun

Committee Member(s)

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

Department of Study

Statistics

Discipline

Statistics

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• sketching
• approximate matrix multiplication
• randomized algorithms
• kernel methods
• importance sampling

Abstract

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.

Graduation Semester

2023-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2023 Yifan Chen

Owning Collections