Randomized methods for rank-deficient linear systems

Josef Sifuentes, Zydrunas Gimbutas, Leslie Greengard

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)177-188
Number of pages12
JournalElectronic Transactions on Numerical Analysis
StatePublished - 2015


  • Eigenvectors
  • Integral equations
  • Null space
  • Null vectors
  • Randomized algorithms
  • Rank-deficient systems

ASJC Scopus subject areas

  • Analysis


Dive into the research topics of 'Randomized methods for rank-deficient linear systems'. Together they form a unique fingerprint.

Cite this