# How can I efficiently solve $Ax$=$b$ given $A$ is symmetric and contains very small (even negative) eigenvalues using EIGEN

Currently I am using the EIGEN C++ library to try to solve $x$ from the equation $Ax$ = $b$. One problem I encountered is that the matrix $A$ is a correlation matrix with size > 5000 and can sometimes be rank deficient and have small, even negative eigenvalues. As a result of that, the matrix tends to have huge condition numbers 100~1000+.

Special properties of the matrix $A$ include: symmetric (because it is a correlation matrix) and the correlation decreases as the two entries get further away (e.g. $R_{1,2}$ > $R_{1,6}$).

The current way I used to solve the equation is to use the truncated SVD method to obtain a pseudoinverse of $A$. I also tried to exploit the fact that the matrix is symmetric by using the self-adjoint eigen solver instead of SVD which speed up the process considerably. However, it still remains rather slow and from what I read, people always said one should NEVER EVER try to solve the inverse whenever possible.

As a result of that, I wonder if there is anyway for one to speed up this process even further. I have read that one can use the QR method to obtain the pseudoinverse. My understanding is that for $A$ = $QR$, I can replace $R$ with $R_k$ the when the diagonal at $k$ is the last element bigger than a threshold and any subsequent row will be replaced by 0.

So, my question is: is this QR method correct? Or is there any method that can better solve this kind of equation?

• How slow is too slow? How fast do you need it to be? – Bill Barth Jun 14 '15 at 16:09
• When using the SVD with matrix size > 3000, I have to wait for 3 days and still couldn't get a solution. Now with the self-adjoint method, I can get a 500x5000 matrix done within an hour. The main problem is that it is not scalelable with the required time increases exponentially. I am just interested to see if, for example, whether if I can solve a 10000x10000 matrix within say, an hour – Sam Jun 14 '15 at 16:10
• I am currently using multi-threading with roughly 12 threads. Also, I don't have access to graphic card, so I couldn't use CUDA... – Sam Jun 14 '15 at 16:12
• It shouldn't take more than a few seconds to compute the SVD of a 3000 by 3000 matrix using any reasonably efficient linear algebra library. Don't use the QR factorization without pivoting- it's not a stable rank revealing factorization. – Brian Borchers Jun 14 '15 at 16:14
• The problem of SVD is that EIGEN use Jacobian SVD which is one of the slowest I think. So if it is the pivoting QR, it is ok? [e.g.][eigen.tuxfamily.org/dox/classEigen_1_1ColPivHouseholderQR.html] – Sam Jun 14 '15 at 16:31