General solution using pseudo inverse.

307 Views Asked by At

I'm having trouble to understand the general solution of a $Ax=b$ when $x=A^+b+ [I-A^+A]w$

I don't understand why the $w$ is there and why $w$ can be any vector.

My view is: $Ax=b$

$A[A^+b+ [I-A^+A]w]=b$

$Ax^++[A-AA^+A]w=b$

$Ax^++[A-A]w=b$

$Ax^+=b$

But since $A^+A$ is the projection on the row space, $I-A^+A$ is the projection on the null space of A, to this solution be valid $w$ should be a vector on the row space? In my class room $w$ is considered any vector, why this? This don't make any sense to me.

If anyone can provide me any textbook or explain would help a lot.

1

There are 1 best solutions below

2
On

You should give the definition of pseudo-inverse, $A^\dagger$. If you use Moore–Penrose inverse, then it is $A^\dagger = (A^TA)^{-1}A^T$. Therefore: $$I - A^\dagger A = I - (A^TA)^{-1}A^TA = 0$$ $$x = A^\dagger b + 0w, \quad \forall w\in R^n$$ The projection onto range space of $A$ is not $A^\dagger A$, but it is $AA^\dagger$.

As asked in the comments, if A is not full column rank, you should use the following SVD formula for Penrose Inverse: $$A = U\Sigma V^T, \quad \Sigma = diag(\sigma_1,\ldots,\sigma_r,0,\ldots,0)$$ $$A^\dagger = V\Sigma^\dagger V^T, \quad \Sigma^\dagger = diag(1/\sigma_1,\ldots,1/\sigma_r,0,\ldots,0)$$ where $r$ is rank of A. Then: $$I - A^\dagger A = I - V_{r+1:d}V_{r+1:d} = P_{N(A)}$$ where $A\in R^{n\times d}$ and $P_{N(A)}$ is the orthogonal projection onto the null space of $A$. Now, since additional term in the null space it will be mapped to 0 when multiplied with matrix $A$: $$A x = AA^\dagger b + \underbrace{A P_{N(A)}w}_{= 0, \ \forall w\in R^d} = AA^\dagger b = b$$ Last equality holds if $b$ is in the range space of $A$.