Volume 44, pp. 177-188, 2015.

Randomized methods for rank-deficient linear systems

Josef Sifuentes, Zydrunas Gimbutas, and Leslie Greengard


We present a simple, accurate method for solving consistent, rank-deficient linear systems, with or without additional rank-completing constraints. Such problems arise in a variety of applications such as the computation of the eigenvectors of a matrix corresponding to a known eigenvalue. The method is based on elementary linear algebra combined with the observation that if the matrix is rank-$k$ deficient, then a random rank-$k$ perturbation yields a nonsingular matrix with probability close to 1.

Full Text (PDF) [272 KB], BibTeX

Key words

rank-deficient systems, null space, null vectors, eigenvectors, randomized algorithms, integral equations

AMS subject classifications

15A03, 15A12, 15A18, 65F15, 65F99

< Back