Matrix Computations: Low Rank Approximation

This lecture discusses the complexity of matrix computations, focusing on low rank approximation. The instructor explains the problem formulation, the meaning of low rank matrices, and the importance of approximation algorithms. Various algorithms for low rank approximation are explored, including traditional O(n³) methods, powering methods, and randomized algorithms. The lecture covers error measures, matrix norms, and different types of approximation quality. It also delves into sketch and solve algorithms, iterative algorithms, and column subset selection algorithms. Additionally, the lecture touches on other algorithms such as greedy column subset selection, coresets, non-negative matrix factorization, and binary matrix factorization.