Fast Algorithms for Linear Algebraic Computation
Event details
| Date | 17.06.2022 |
| Hour | 14:00 › 16:00 |
| Speaker | Kshiteej Sheth |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Linear algebraic objects and computation are at the core of modern machine learning and data science. Large and high-dimensional datasets are represented in terms of matrices and modern computational tasks require fast primitives to quickly manipulate them. In this report, we focus on two main paradigms in linear algebraic computation in modern settings. First, we discuss a fundamental work in linear sketching and matrix compression which obtains embeddings for large data matrices that approximately preserve the norm of every vector in their column space with high probability and applying the embedding takes input-sparsity time. This leads to input-sparsity time algorithms for various problems such as approximate regression and low-rank approximation. Secondly, we discuss a recent result that obtains linear and sublinear time algorithms for computing coarse information about the full eigenspectrum of an $n\times n$ hermitian matrix. This employs fast algorithms for approximating the trace of a matrix and we also discuss another recent work that obtains tight bounds for this problem. Finally we discuss future research directions concerning these two paradigms and the progress we have made so far.
Background papers
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Michael Kapralov
Co-examiner: Prof. Ola Svensson
Abstract
Linear algebraic objects and computation are at the core of modern machine learning and data science. Large and high-dimensional datasets are represented in terms of matrices and modern computational tasks require fast primitives to quickly manipulate them. In this report, we focus on two main paradigms in linear algebraic computation in modern settings. First, we discuss a fundamental work in linear sketching and matrix compression which obtains embeddings for large data matrices that approximately preserve the norm of every vector in their column space with high probability and applying the embedding takes input-sparsity time. This leads to input-sparsity time algorithms for various problems such as approximate regression and low-rank approximation. Secondly, we discuss a recent result that obtains linear and sublinear time algorithms for computing coarse information about the full eigenspectrum of an $n\times n$ hermitian matrix. This employs fast algorithms for approximating the trace of a matrix and we also discuss another recent work that obtains tight bounds for this problem. Finally we discuss future research directions concerning these two paradigms and the progress we have made so far.
Background papers
- OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings, FOCS 2013 - https://arxiv.org/pdf/1211.1002.pdf
- Linear and Sublinear Time Spectral Density Estimation, STOC 2022 - https://arxiv.org/pdf/2104.03461.pdf
- Hutch++: Optimal Stochastic Trace Estimation, SOSA 2021 - https://arxiv.org/pdf/2010.09649.pdf
Practical information
- General public
- Free