Geodesic
Randomized methods for rank-deficient linear systems
Electronic transactions on numerical analysis, Tome 44 (2015), pp. 177-188
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.
Classification : 15A03, 15A12, 15A18, 65F15, 65F99
Keywords: rank-deficient systems, null space, null vectors, eigenvectors, randomized algorithms, integral equations 
@article{ETNA_2015__44__a21,
     author = {Sifuentes,  Josef and Gimbutas,  Zydrunas and Greengard,  Leslie},
     title = {Randomized methods for rank-deficient linear systems},
     journal = {Electronic transactions on numerical analysis},
     pages = {177--188},
     year = {2015},
     volume = {44},
     zbl = {1312.65057},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2015__44__a21/}
}
TY  - JOUR
AU  - Sifuentes,  Josef
AU  - Gimbutas,  Zydrunas
AU  - Greengard,  Leslie
TI  - Randomized methods for rank-deficient linear systems
JO  - Electronic transactions on numerical analysis
PY  - 2015
SP  - 177
EP  - 188
VL  - 44
UR  - http://geodesic.mathdoc.fr/item/ETNA_2015__44__a21/
LA  - en
ID  - ETNA_2015__44__a21
ER  - 
%0 Journal Article
%A Sifuentes,  Josef
%A Gimbutas,  Zydrunas
%A Greengard,  Leslie
%T Randomized methods for rank-deficient linear systems
%J Electronic transactions on numerical analysis
%D 2015
%P 177-188
%V 44
%U http://geodesic.mathdoc.fr/item/ETNA_2015__44__a21/
%G en
%F ETNA_2015__44__a21
Sifuentes,  Josef; Gimbutas,  Zydrunas; Greengard,  Leslie. Randomized methods for rank-deficient linear systems. Electronic transactions on numerical analysis, Tome 44 (2015), pp. 177-188. http://geodesic.mathdoc.fr/item/ETNA_2015__44__a21/