R N L a

Randomized Numerical Linear Algebra

we shall discuss randomized numerical linear algebra which is a very active subject now, with ideas from and impacts on various fields, including analysis of big data sets, probability and statistics, numerical analysis, and computational complexity. Selected topics are:

Introduction to the Probability Theory

• Review on Probability

Johnson-Lindenstrauss transform

• Johnson-Lindenstrauss Transform and Random Projection
• Project: Reproduce results in the following paper. You can skip the test with real data first.

Fast Least Squares Approximation

• Least square problem, QR and SVD decomposition
• Fast Least Square Solvers
• Project: Fast Least Square Solvers.

Random Matrix Theory

• Tail bound of random matrices

Randomized Factorization

• Randomized Factorization
• Halko, N., Martinsson, P.G., and Tropp, J.A. (2011). Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions. SIAM Review, 53(2), 217-288.
• Project: Reproduce results in Section 7.1 and 7.4 in the SIAM Review paper (2011), 53(2), 217-288.