PCMI summer school lectures, P.G. Martinsson, July 2016

PCMI summer school lectures:

Randomized algorithms for matrix computations and analysis of high dimensional data

Lecturer: Per-Gunnar Martinsson (Univ. of Colorado at Boulder)
TA: Nathan Heavner (Univ. of Colorado at Boulder)

This wepage is set up to provide convenient links to supplementary material for a series of three lectures and three problem solving sessions that formed a part of the PCMI program The Mathematics of Data, held in Midway, Utah, in July 2016.

The lectures will be self-contained, and will in principle assume only knowledge of basic material on linear algebra and probability theory. Some prior experience with numerical analysis would be helpful, but is far from necessary.

Lecture slides.

Lecture summary. This document provides a road map of the lectures. Some key concepts are described in detail. References are provided on where to look for further details.

Manuscript. The material in the lectures is drawn largely from the manuscript linked to (arxiv.org report 1607.01649). This is the first half of a longer text currently in progress. Beware that the manuscript may very well contain errors of various types - if you see any then please contact the author! Other feedback is also very welcome. (Local copy.)

Survey paper. While getting a few years old by now, this survey provides a detailed description of some of the techniques described. The survey is quite long, but the introduction (section 1.1 - 1.6) can be read by itself, and provides a concise introduction to the key ideas. I would also recommend an early PNAS paper that also provides a very brief treatment of the key concepts.

Problem sets. Set 1, solutions, Set 2, solutions, Set 3.

Software:
- Tutorial codes implementing RSVD in Matlab. There is GPU support via Matlab (for supported machines).
- RSVDPACK (With Sergey Voronin.) CPU and GPU implementations in C of most of the techniques covered: RSVD, randomized ID and CUR, etc.
- ID (With Mark Tygert.) FORTRAN and Matlab codes for RSVD, RSFT, interpolative decompositions, etc.
- HGRRP (With Gregorio Quintana-Orti, Nathan Heavner, and Robert van de Geijn.) Highly optimized implementations of (Householder) column pivoted QR with randomization for pivoting. Functions with LAPACK compatible interfaces are included.

Research support by:

P.G. Martinsson, July 2016