Solving A System Of Linear Equations By Randomized Orthogonal Projections

Authors Alireza Entezari, Arunava Banerjee, Leila Kalantari

Publication date 12 November 2021

Eigenvalues, singular values, and eigenvectors (15A18) Iterative numerical methods for linear systems (65F10) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: Randomization has shown catalyzing effects in linear algebra with promising perspectives for tackling computational challenges in large-scale problems. For solving a system of linear equations, we demonstrate the convergence of a broad class of algorithms that at each step pick a subset of

n

equations at random and update the iterate with the orthogonal projection to the subspace those equations represent. We identify, in this context, a specific degree-

n

polynomial that non-linearly transforms the singular values of the system towards equalization. This transformation to singular values and the corresponding condition number then characterizes the expected convergence rate of iterations. As a consequence, our results specify the convergence rate of the stochastic gradient descent algorithm, in terms of the mini-batch size

n

, when used for solving systems of linear equations.

This page was built for publication: Solving A System Of Linear Equations By Randomized Orthogonal Projections

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