A Caltech Library Service

ACM 204: Randomized Algorithms for Matrix Computations

Tropp, Joel A. (2020) ACM 204: Randomized Algorithms for Matrix Computations. [Teaching Resource] (Unpublished)

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


ACM 204 is a graduate course on randomized algorithms for matrix computations. It was taught for the first time in Winter 2020. The course begins with Monte Carlo algorithms for trace estimation. This is a relatively simple setting that allows us to explore how randomness can be used for matrix computations. We continue with a discussion of the randomized power method and the Lanczos method for estimating the largest eigenvalue of a symmetric matrix. For these algorithms, the randomized starting point regularizes the trajectory of the iterations. The Lanczos iteration and randomized trace estimation fuse together in the stochastic Lanczos quadrature method for estimating the trace of a matrix function. Then we turn to Monte Carlo sampling methods for matrix approximation. This approach is justified by the matrix Bernstein inequality, a powerful tool for matrix approximation. As a simple example, we develop sampling methods for approximate matrix multiplication. In the next part of the course, we study random linear embeddings. These are random matrices that can reduce the dimension of a dataset while approximately preserving its geometry. First, we treat Gaussian embeddings in detail, and then we discuss structured embeddings that can be implemented using fewer computational resources. Afterward, we describe several ways to use random embeddings to solve over-determined least-squares problems. We continue with a detailed treatment of the randomized SVD algorithm, the most widely used technique from this area. We give a complete a priori analysis with detailed error bounds. Then we show how to modify this algorithm for the streaming setting, where the matrix is presented as a sequence of linear updates. Last, we show how to develop an effective algorithm for selecting influential columns and rows from a matrix to obtain skeleton or CUR factorizations. The next section of the course studies kernel matrices that arise in high-dimensional data analysis. We discuss positive-definite kernels and outline the computational issues associated with solving linear algebra problems involving kernels. We introduce random feature approximations and Nyström approximations based on randomized sampling. This area is still not fully developed. The last part of the course gives a complete presentation of the sparse Cholesky algorithm of Kyng & Sachdeva [KS16], including a full proof of correctness.

Item Type:Teaching Resource
Tropp, Joel A.0000-0003-1024-1791
Other Contributors:
ContributionOther Contributors NameIdentifierPersonID (may be blank)
CompilerKeung, RichardKeung-RichardUNSPECIFIED
Alternate Title:Randomized Algorithms for Matrix Computations
Additional Information:© 2020 Joel A. Tropp. Typeset on April 21, 2021. The Winter 2020 edition of ACM 204 is the first instantiation of a course on randomized matrix computations. At a high level, the course is organized along the same lines as the survey [MT20]. In contrast to the survey, the course contains full proofs of the major results. Some parts of the class are modeled on the short course [Tro19]; the material on sparse Cholesky has been omitted from these notes because it has been carefully documented in the existing notes. The course notes were transcribed from the lectures by the students as part of their coursework, so they reflect the actual content of the course. The notes have been closely edited by Dr. Richard Kueng, with additional light editing by the instructor. There is no warranty about the correctness of these notes. Furthermore, material is not necessarily accompanied by appropriate citations to the literature. These notes were prepared with the assistance of students and postdocs who participated in the course: Dmitry Burov, Po-Chih Chen, Yifan Chen, Nikola Kovachki, Riley Murray, Richard Kueng, Zongyi Li, Chung-Yi Lin, Fariborz Salehi, Jiace Sun, Oguzhan Teke, Jing Yu, Shumao Zhang, and Ziyun Zhang. Richard Kueng prepared the complete set of notes from the individual lectures. Many thanks are due to them for their care and diligence. All remaining errors are the fault of the instructor.
Group:Caltech CMS Lecture Notes
Series Name:Caltech CMS Lecture Notes
Issue or Number:2020-01
Record Number:CaltechAUTHORS:20210421-101607288
Persistent URL:
Official Citation:Joel A. Tropp, ACM 204: Randomized Algorithms for Matrix Computations, Caltech CMS Lecture Notes 2020-01, Pasadena, March 2020.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108783
Deposited By: George Porter
Deposited On:21 Apr 2021 21:01
Last Modified:26 Aug 2022 18:07

Repository Staff Only: item control page