[R] Solving sparse, singular systems of equations

[A A via R-help]

I have a situation in R where I would like to find any x (if one exists) that solves the linear system of equations Ax = b, where A is square, sparse, and singular, and b is a vector. Here is some code that mimics my issue with a relatively simple A and b, along with three other methods of solving this system that I found online, two of which give me an error and one of which succeeds on the simplified problem, but fails on my data set(attached). Is there a solver in R that I can use in order to get x without any errors given the structure of A? Thanks for your time.
#CODE STARTS HEREA = as(matrix(c(1.5,-1.5,0,-1.5,2.5,-1,0,-1,1),nrow=3,ncol=3),"sparseMatrix")b = matrix(c(-30,40,-10),nrow=3,ncol=1)
#solve for x, Error in LU.dgC(a) : cs_lu(A) failed: near-singular A (or out of memory)solve(A,b,sparse=TRUE,tol=.Machine$double.eps)
#one x that happens to solve Ax = bx = matrix(c(-10,10,0),nrow=3,ncol=1)A %*% x
#Error in lsfit(A, b) : only 3 cases, but 4 variableslsfit(A,b)#solves the system, but fails belowsolve(qr(A, LAPACK=TRUE),b)#Error in qr.solve(A, b) : singular matrix 'a' in solveqr.solve(A,b)
#matrices used in my actual problem (see attached files)A = readMM("A.txt")b = readMM("b.txt")
#Error in as(x, "matrix")[i, , drop = drop] : subscript out of boundssolve(qr(A, LAPACK=TRUE),b)

[William Dunlap via R-help]

This is not a solution but your lsfit attempt

#Error in lsfit(A, b) : only 3 cases, but 4 variables
lsfit(A,b)

gave that error because lsfit adds a column of 1 to
its first argument unless you use intercept=FALSE.
Then it will give you an answer (but I think it converts
your sparse matrix into a dense one before doing
any linear algebra).



Bill Dunlap
TIBCO Software
wdunlap tibco.com

On Wed, Apr 20, 2016 at 4:22 AM, A A via R-help <r-h...@r-project.org>
wrote:

> ______________________________________________
> R-h...@r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
> http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

[[alternative HTML version deleted]]

______________________________________________
R-h...@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.

[Jeff Newmiller]

This is kind of like asking for a solution to x+1=x+1. Go back to linear algebra and look up Singular Value Decomposition, and decide if you really want to proceed. See also ?svd and package irlba.
--
Sent from my phone. Please excuse my brevity.

>------------------------------------------------------------------------

[Berend Hasselman]

Your code is a mess.

A singular square system of linear equations has an infinity of solutions if a solution exists at all.
How that works you can find here: https://en.wikipedia.org/wiki/System_of_linear_equations
in the section "Matrix solutions".

For your simple example you can do it like this:

library(MASS)
Ag <- ginv(A) # pseudoinverse

xb <- Ag %*% b # minimum norm solution

Aw <- diag(nrow=nrow(Ag)) - Ag %*% A # see the Wikipedia page
w <- runif(3)
z <- xb + Aw %*% w
A %*% z - b

N <- Null(t(A)) # null space of A; see the help for Null in package MASS
A %*% N
A %*% (xb + 2 * N) - b

For sparse systems you will have to approach this differently; I have no experience with that.

Berend

[A A via R-help]

Thanks for the advice. I fixed the function and ran it on my systems just to see if it would work; for the first set of A and b, I got a valid solution, but for the second set, I got the error "Error in complete.cases(x, y, wt) : not all arguments have the same length". 

On Wednesday, April 20, 2016 10:59 AM, William Dunlap <wdu...@tibco.com> wrote:

This is not a solution but your lsfit attempt   #Error in lsfit(A, b) : only 3 cases, but 4 variables   lsfit(A,b)gave that error because lsfit adds a column of 1 toits first argument unless you use intercept=FALSE.Then it will give you an answer (but I think it convertsyour sparse matrix into a dense one before doingany linear algebra).

[A A via R-help]

Thanks for the response. Yes, in that situation a solution of x = 1 would be just as good as x = 1000 or any other value of x for me (but in my problem the matrix has nonzero rank, so I can't just randomly choose a vector and have it be a solution). If it helps, what I'm interested in is the R equivalent of 
x = A\b
in MATLAB, for these particular kinds of A matrices. I looked into irlba, and it seems to be able to calculate some of the singular values/vectors for the large dataset without taking too much time. I'll look more into seeing how I can solve the system with it.

On Wednesday, April 20, 2016 11:01 AM, Jeff Newmiller <jdne...@dcn.davis.ca.us> wrote:

This is kind of like asking for a solution to x+1=x+1. Go back to linear algebra and look up Singular Value Decomposition, and decide if you really want to proceed. See also ?svd and package irlba.
--
Sent from my phone. Please excuse my brevity.

On April 20, 2016 4:22:34 AM PDT, A A via R-help <r-h...@r-project.org> wrote:

I have a situation in R where I would like to find any x (if one exists) that solves the linear system of equations Ax = b, where A is square, sparse, and singular, and b is a vector. Here is some code that mimics my issue with a relatively simple A and b, along with three other methods of solving this system that I found online, two of which give me an error and one of which succeeds on the simplified problem, but fails on my data set(attached). Is there a solver in R that I can use in order to get x without any errors given the structure of A? Thanks for your time.
#CODE STARTS HEREA = as(matrix(c(1.5,-1.5,0,-1.5,2.5,-1,0,-1,1),nrow=3,ncol=3),"sparseMatrix")b = matrix(c(-30,40,-10),nrow=3,ncol=1)
#solve for x, Error in LU.dgC(a) : cs_lu(A) failed: near-singular A (or out of memory)solve(A,b,sparse=TRUE,tol=.Machine$double.eps)
#one x that happens to solve Ax = bx = matrix(c(-10,10,0),nrow=3,ncol=1)A %*% x
#Error in
lsfit(A, b) : only 3 cases, but 4 variableslsfit(A,b)#solves the system, but fails belowsolve(qr(A, LAPACK=TRUE),b)#Error in qr.solve(A, b) : singular matrix 'a' in solveqr.solve(A,b)
#matrices used in my actual problem (see attached files)A = readMM("A.txt")b = readMM("b.txt")
#Error in as(x, "matrix")[i, , drop = drop] : subscript out of boundssolve(qr(A, LAPACK=TRUE),b)

[A A via R-help]

Thanks for the help. Sorry, I am not sure why it looks like that in the mailing list - it looks much more neat on my end (see attached file).

[Jeff Newmiller]

The usual culprit in messy code is posting in HTML format. That usually leads to stripping of the formatting by the mailing list and a notice that that occurred, but I don't see that warning here. I still think posting plain text format would fix the problem.

--
Sent from my phone. Please excuse my brevity.

[[alternative HTML version deleted]]