Class time and Location:
Prerequisites: General mathematical sophistication; and a solid understanding of Algorithms, Linear Algebra, and Probability Theory, at the advanced undergraduate or beginning graduate level, or equivalent. (If you have not at least seen most of the material in Chapter 2 and 3 of these notes, then you may have difficulties.)
Course requirements: Most likely, multiple homeworks (ca. $60\%$ total), scribe a lecture (ca. $10\%$), and a research project (ca. $40\%$); and perhaps a final exam.
Want more information on RandNLA? DJ Rich of Mutual_Information posted a very nice summary video about RandNLA, motivated by but much more general than our recent RandBLAS/RandLAPACK monograph. Check it out if you want to learn more.
Much of the material has not worked its way into textbooks, and thus we will be reading reviews and primary sources. There are, however, multiple good reviews on the topic. Here are a few articles that should give you an idea of some of the topics.
General introductory overviews:
Primary material (for the first half of the term):
Theoretical computer science perspective:
Low-rank approximation:
Scientific computing perspective:
Software perspective:
Optimization:
Additional material:
Main References:
Chapter 1 of LN-RNLA
Main References:
Section 4 of:
"Lectures on Randomized Numerical Linear Algebra,"
Drineas and Mahoney
(PCMI 2017)
(arxiv)
Backup:
Chapter 2 of LN-RNLA
Drineas, Kannan, and Mahoney,
"Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication"
Main References:
Chapter 3-5 of LN-RNLA
Backup:
Section 4 of:
"Lectures on Randomized Numerical Linear Algebra,"
Drineas and Mahoney
(PCMI 2017)
(arxiv)
Main References:
Same as last class.
We will cover Thm 6, Thm 8, and (hopefully) Lemma 15 of Chapter 5 of LN-RNLA.
Main References:
Chapter 5 of LN-RNLA
Main References:
Section 5 of:
"Lectures on Randomized Numerical Linear Algebra,"
Drineas and Mahoney
(PCMI 2017)
(arxiv)
Backup:
Chapter 6-7 of LN-RNLA
Main References:
Chapter 1-2 of:
"Randomized Numerical Linear Algebra: A Perspective on the Field With an Eye to Software"
Murray, Demmel, Mahoney, Erichson, Melnichenko, Malik, Grigori, Luszczek, Derezinski, Lopes, Liang, Luo, and Dongarra
(SIAM 2023)
(arxiv)
Main References:
Chapter 8-10 of LN-RNLA