Matrix Computations: Complexity and Solvers

This lecture explores the complexity of matrix computations, focusing on solving least squares problems. It covers the sensitivity of mathematical problems to noise, numerical stability of algorithms, and the impact of noisy inputs. Various methods for solving least squares problems are discussed, including statistical regression and applied mathematics approaches. The lecture delves into the challenges posed by noisy and ill-conditioned matrices, emphasizing the importance of accurate solutions and the role of well-posed problems. Different least squares solvers are presented, ranging from dense matrices using QR factorization to sparse matrices employing LSQR methods. The lecture also touches on randomized algorithms and the use of sketching techniques to enhance computational efficiency.