# 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]