Reading List 2015.6.2

"Sketching as a Tool for Numerical Linear Algrbra"

-Randomized algorithms:
random sampling, see reference:
1. Randomized algorithms for matrices and data.
2. Iterative row sampling. In FOCS, pages 127-136.
3. Uniform sampling for matrix approximation.

random projection, see reference:
1. Randomized algorithms for matrices and data.
2. Sketching as a Tool for Numerical Linear Algebra.

Some applications: least square regression, least absolute deviation regression, low rank approximation, graph sparsification. The first three applications is introduced in the video tutorial here.

This paper is very technical and not easy to understand. Anyway, sketching technic is a very useful tool in many areas.