Finding the least norm solution of least squares problem with a sparse matrix

Specific Domains Numerics
#1

I have a matrix M which is the transpose of the Laplacian of a graph and a vector d that may or may not be in the range of M. I want to compute pinv(M)*d.

I assumed that qr(M)\d does what I want, however it does it only when M is represented by a full matrix, see my previous question. If M is represented by a sparse matrix, it gives a solution but not the least norm one.

So what is the most efficient to get pinv(M)*d?

Differences in A \ b for sparse and nonsparse rank-deficient A
#2

That will probably depend on your matrix. The iterative solvers LSQR and LSMR compute the least norm least square solution. In particular, they approximate the least norm solution if your system is feasible. These methods are implemented in IterativeSolvers.jl, cf. https://juliamath.github.io/IterativeSolvers.jl/dev/linear_systems/lsqr/.

3 Likes
#3

See also https://github.com/JuliaSmoothOptimizers/Krylov.jl

3 Likes