1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – 0x0 Feb 15 '11 at 2:05
  • $\begingroup$ @Sunil: unfortunately, the link does not help. :( $\endgroup$ – Qiang Li Feb 15 '11 at 3:15
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Qiang Li Feb 15 '11 at 17:35
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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