University of Illinois Urbana-Champaign

Efficient matrix computations via subsampling sketches

Chen, Yifan

This item's files can only be accessed by the Administrator group.

Permalink

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

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
Copyright and License Information
Copyright 2023 Yifan Chen

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois