Randomized methods for rank-deficient linear systems

2014/01/14 by Josef Sifuentes, Zydrunas Gimbutas, Sifuentes, Josef +3 · 2 citations
Computer Science · Engineering · #Matrix Theory and Algorithms #Stochastic Gradient Optimization Techniques #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1401.3068

Abstract

We present a simple, accurate method for solving consistent, rank-deficient linear systems, with or without addi- tional 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 ob- servation that if the matrix is rank-k deficient, then a random rank-k perturbation yields a nonsingular matrix with probability 1.

Citations

• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Cited by

• Fast integral methods for the Neumann Green's function: applications to capture and signaling problems in two dimensions
• Accurate Derivative Evaluation for any Grad-Shafranov Solver

Related

• A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations
• Randomized Matrix Computations
• More on the Power of Randomized Matrix Computations
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• On pseudoinverse-free randomized methods for linear systems: Unified framework and acceleration