CAAM 651: Topics in Numerical Linear Algebra

Randomized Matrix Algorithms

Fall 2013 · Rice University

Meetings:	Thursdays 4-5:30pm, Duncan Hall 1046
Instructors:	Mark Embree (embree@rice.edu), Duncan Hall 3019, (713) 348-6160     Office hours: Tuesday 2-4pm (DCH 3092), Friday 1pm-2pm (DCH 3019), or by appointment. Dan Sorensen (sorensen@rice.edu), Duncan Hall 2035, (713) 348-5193     Office hours: by appointment.
Syllabus:	syllabus.pdf

---

Key References:	Throughout the semester we will be working from these two key references. Halko, Martinson, and Tropp, "Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions", SIAM Review, 2011. Mahoney, Randomized Algorithms for Matrices and Data, FnTML, 2011.
Lecture 3: 19 Sep	The norm of the mismatch of a random projection: probabilistic bounds (Thm 10.5) Halko/Martinsson/Tropp, Section 10 and appendices MATLAB code: thm_10_5.m Chen and Dongarra, Condition Numbers of Gaussian Random Matrices, SIAM J. Matrix Anal. Appl., 2005. Edelman, Eigenvalues and Condition Numbers of Random Matrices, SIAM J. Matrix Anal. Appl., 1988. Tao and Vu, From the Littlewood-Offord Problem To the Circular Law..., Bulletin AMS, 2009.
Lecture 2: 12 Sep	The norm of the mismatch of a random projection: deterministic bound (Thm 9.1) Halko/Martinsson/Tropp, Theorem 9.1 MATLAB code: thm_9_1.m
Lecture 1: 5 Sep	Overview of randomized matrix algorithms Application to principal orthogonal decompositions (POD) and approximate Gramians Halko/Martinsson/Tropp, Section 1 MATLAB codes: randSVD.m, randSVDApA.m, driveRandSVD.m