Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
arXiv:1612.06013
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.
arXiv comment161 pages, PhD thesis, Univ Edinburgh, 2016
References in corpus (21)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- Distributed Coordinate Descent Method for Learning with Big Data
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
- Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
- Stochastic Dual Ascent for Solving Linear Systems
- An Asynchronous Parallel Randomized Kaczmarz Algorithm
- SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
- On the Randomized Kaczmarz Algorithm
- Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
- Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- A Proximal Stochastic Gradient Method with Progressive Variance Reduction
- Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
- Parallel coordinate descent for the Adaboost problem
- Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
- Action constrained quasi-Newton methods
- Higher-order Reverse Automatic Differentiation with emphasis on the third-order
- Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?