Courses

The summer school will bring graduate students up to date on the state-of-the-art of RandNLA, through lectures, interactive tutorials, and hands-on projects. Since RandNLA is quite interdisciplinary, students are likely to come from a variety of different backgrounds within computer science and mathematics. Topics to be covered include:
  • Introduction and interdisciplinary overview of RandNLA
    • Random variables, expectation, moments, concentration, coupon collector's problem, Chernoff and Hoeffding bounds
    • Matrix valued random variables, matrix concentration bounds, coherence
    • Monte Carlo methods, different sampling methods (with and without replacement, Bernoulli), importance sampling
    • Matrix multiplication, SVD, low rank approximations, leverage scores
  • RandNLA in theoretical computer science
    • Models of data access, pass efficiency
    • Lower bounds
    • Input-sparsity time embeddings
    • Graph sparsification
  • RandNLA in numerical linear algebra
    • Computational implementation of sampling methods
    • Conditioning of sampled matrices
    • Randomized pre-conditioners for least squares
    • Sensitivity and numerically stable computation of leverage scores
    • Rank-revealing decompositions, subset selection
    • CUR and Nystrom methods
  • Applications of RandNLA
    • Large-scale machine learning, geometric data analysis
    • Parameter estimation, model reduction, discrete empirical interpolation
    • Genomics
    • Astronomy