Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices

arXiv1612.06013MaRDI QIDQ6280993FDOQ6280993

Publication date: 18 December 2016

Abstract: Probabilistic ideas and tools have recently begun to permeate into several fields where they had traditionally not played a major role, including fields such as numerical linear algebra and optimization. One of the key ways in which these ideas influence these fields is via the development and analysis of randomized algorithms for solving standard and new problems of these fields. Such methods are typically easier to analyze, and often lead to faster and/or more scalable and versatile methods in practice. This thesis explores the design and analysis of new randomized iterative methods for solving linear systems and inverting matrices. The methods are based on a novel sketch-and-project framework. By sketching we mean, to start with a difficult problem and then randomly generate a simple problem that contains all the solutions of the original problem. After sketching the problem, we calculate the next iterate by projecting our current iterate onto the solution space of the sketched problem.

Has companion code repository: https://github.com/c-dickens/phd-work

Mathematics Subject Classification ID

Quadratic programming (90C20) Complexity and performance of numerical algorithms (65Y20) Random matrices (algebraic aspects) (15B52) Probabilistic methods, particle methods, etc. for boundary value problems involving PDEs (65N75) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40) Linear equations (linear algebraic aspects) (15A06) Iterative numerical methods for linear systems (65F10)

This page was built for publication: Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280993)