Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by the all-one vector).

I have to solve the problem $Ax = b$, with $b \in R(A)$ which has infinitely many solutions. I am looking for the minimum norm solution. The matrix $A$ is very large and sparse, direct methods aren't really an option. The rank-deficient least squares algorithms I have seen also appear to be prohibitive.

I was solving a non-singular version of this problem with Conjugate Gradient. Is there anyway I can modify the algorithm to solve this particular problem?

EDIT: Boiling the problem down to the bone the question is if $A$ is positive semi-definite with exactly one 0 eigenvalue, does CG work?

Thanks.

share|improve this question
1  
mathoverflow.net/questions/7903 –  J. M. Aug 15 '10 at 13:00
add comment

3 Answers

up vote 4 down vote accepted

I'd suggest you to shift away the singularity: solve $(A+ee^T)y=b$ instead and then orthogonalize $y$ with respect to $e$ to get $x$. $A+ee^T$ is not sparse but you can compute matrix-vector products cheaply, and that's all you need for CG.

EDIT: forgot to define it, $e$ is the vector of all ones

share|improve this answer
    
This is exactly what I did. With the help of a preconditioner it converges sufficiently fast. In hindsight it was the obvious route to take. Thanks for pointing it out to me. –  RadonNikodym Aug 16 '10 at 8:21
add comment

Plain CG, without the regularization, will converge to the pseudo-inverse solution provided you start the iteration with $y=0$. The regularized (preconditioned) solution will be different and the operation count will depend on the sparsity, so it's good to maintain this if you can. I guess partly it must depend on whether you can tolerate a solution that has a nonzero component in the null space.

share|improve this answer
add comment

You can add a linear constraint, stipulating that your solution should be orthogonal to the null space, assuming it is known to you ahead of time.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.