Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the link http://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse, it talks about solving $Ax=b$ by $x = A^+b + [I − A^+A]w$ for any vector $w$. Let's say $A$ is $m\times n$, and $b$ and $x\in \mathbb{R}^n$. My question is: since $w$'s $n$ components are in general more than needed given the kernel of $A$ might be of dimension $n-r\gt 0$, how to use Moore–Penrose pseudoinverse $A^+$ to give an explicit solution with the least number of free parameters?

share|improve this question
    
This link might be helpful to you. It shows you how to use Moore-Penrose pseudoinverse in MATLAB and also gives an neat example. mathworks.com/help/techdoc/ref/pinv.html –  Sunil Feb 15 '11 at 2:05
    
@Sunil: unfortunately, the link does not help. :( –  Qiang Li Feb 15 '11 at 3:15

2 Answers 2

The vector $w \in \mathbb{R}^{n \times 1}$ is an arbitrary vector i.e. all the indices are completely free. The reasoning is as follows.

You are solving $Ax = b$ where $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^{n \times 1}$ and $b \in \mathbb{R}^{m \times 1}$ with $m \leq n$. Assume that $A$ is full rank i.e. rank($A$) = $m$. This guarantees that $AA^{*}$ is invertible and hence the existence of Moore-Penrose pseudo-right-inverse is guaranteed.

If we define $A^{+} = A^{*}(AA^{*})^{-1}$, then this the Moore-Penrose pseudo-right-inverse.

The general solution to $Ax = b$ is then given by $x = A^{+}b + z$ where $z \in \text{Null}(A)$.

The Claim now is that $(I-A^{+}A)w$, where $w \in \mathbb{R}^{n \times 1}$ spans the null space of $A$.

First observe that $(I-A^{+}A)w \in \text{Null}(A)$, $\forall w \in \mathbb{R}^{n \times 1}$.

This is because $A \times (I-A^{+}A)w = (A-AA^{+}A)w = (A-A)w = 0$. Further note that the rank of $(I-A^{+}A)$ is $n-m$ and hence $(I-A^{+}A)w$ spans the null-space of $A$

What happens is, though you choose $w$ with all $n$ components independent, $(I-A^{+}A)w$ which is nothing but a projection of $w$ onto the null-space of $A$ ensures that there are only $(n-m)$ "free" components in the vector $(I-A^{+}A)w$.

So the summary is, you are free to choose all the $n$ components of $w$.

share|improve this answer
    
I understood these. My question REALLY is: if I give you $(n-r)$ independent variables, where $r$ is the rank of $A$. How can you write the solution of $Ax=b$ given $A^+$ and these $(n-r)$ independent variables $w'$, rather than providing $n$ independent variables $w$? –  Qiang Li Feb 15 '11 at 17:35

way too late, but apparently noone answered your followup on marvis' answer: you can write the solution space explicitly as the null space of A, although this will require computing this nullspace (which is generally a lot less numerically stable and more time consuming), e.g. through SVD

share|improve this answer

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.