MATH6590
Rensselaer Polytechnic Institute MATH 6590, Spring 2024
This is the official website for course Math 6590: Randomized Numerical Linear Algebra in Spring 2024.
This website contains most of the information you need for this course (lecture notes, assignments). Course sensitive information (announcements, exam, grade distribution etc.) will be posted on LMS (Rensselaer credentials required).General information
Please read the course syllabus VERY CAREFULLY
Instructor: Fabian M. Faulstich
Lecture: TueFri 10:00AM - 12:00AM Carnegie 206
Office hours: Tue 1:00PM-2:00PM, Thu 4:00PM-5PM. 406 Amos Eaton Hall
Piazza page: General questions about the course and its content, which might be of interest to other students, can be asked on the piazza page.
Gradescope page: Homework assignments are to be submitted through Gradescope.
Additional resources
Randomized Numerical Linear Algebra:
Randomized numerical linear algebra: Foundations and algorithms by P.-G. Martinsson and J. A. TroppFinding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions by N. Halko, P. G. Martinsson and J. A. Tropp
Randomized Algorithms for Matrices and Data by M. W. Mahoney
Sketching as a Tool for Numerical Linear Algebra by D. P. Woodruff
An Introduction to Matrix Concentration Inequalities by J. A. Tropp
Randomized algorithms in numerical linear algebra by R. Kannan and S. Vempala
Numerical Linear Algebra:
Numerical linear algebra by L. N. Trefethen and D. Bau, IIIMatrix Algorithms Volume 1: Basic Decompositions by G. Stewart
Matrix algorithms volume 2: eigensystems by G. W. Stewart
Matrix computations by G. H. Golub and C. F. Van Loan
Matrix analysis by R. A. Horn and C. R. Johnson
Matrix analysis by R. Bhatia
Probability Theory:
Lecture notes
Lecture 2
[pdf] and
[LaTeX]
Further relevant resources:
- Paper on interpolative decomposition [Efficient Algorithms for Constructing an Interpolative Decomposition]
- Blog post by Gregory Gundersen on randomized SVD [Link]
- Extensions of Lipschitz mappings into a Hilbert space by W. B. Johnson and J. Lindenstrauss
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions by N. Halko, P.-G. Martinsson and J. A. Tropp
- MATLAB code produced in class [MATLAB]
Lecture 9 [pdf]
Lecture 10 [pdf]
Lecture 11 [pdf]
Lecture 16 [pdf] and [LaTeX] (Annotated version: pdf)
Lecture 17
[pdf] and
[LaTeX]
Further relevant resources (in no particular order):
- Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format by R. Minster, A. K. Saibaba and M. E. Kilmer
- Practical sketching algorithms for low-rank matrix approximation by J. A. Tropp, et al.
- Near Optimal Sketching of Low-Rank Tensor Regression by X. Li, J. Haupt, and D. Woodruff
- Low-Rank Tucker Decomposition of Large Tensors Using TensorSketch by O. A. Malik and S. Becker
- A randomized algorithm for a tensor-based generalization of the singular value decomposition by P. Drineas and M. W. Mahoney
- Randomized methods for higher-order subspace separation by M. N. da Costa, R. R. Lopes, J. M. T. Romano
- Fast and Guaranteed Tensor Decomposition via Sketching by Y. Wang, H.-Y. Tung, A. Smola and A. Anandkumar
- Decomposition of Big Tensors With Low Multilinear Rank by G. Zhou, A. Cichocki and S. Xie
- MATLAB code produced in class [MATLAB]
Further relevant resources (in no particular order):
- Optimal Eigenvalue Approximation via Sketching by W. Swartworth, and D. P. Woodruff
- Testing Positive Semidefiniteness Using Linear Measurements by D. Needell, W. Swartworth, and D. P. Woodruff
- Eigenvalues of a matrix in the streaming model by A. Andoni, and H. Nguyen
- Fast & Accurate Randomized Algorithms for Linear Systems and Eigenvalue Problems by Y. Nakatsukasa, and J. A. Tropp
Homework Assignments
Latex example: [zip]
Homework assignemnt 1: [pdf] and [LaTeX]
Homework assignemnt 2: [pdf] and [LaTeX]