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?
$\begingroup$
$\endgroup$
2
-
$\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$– 0x0Feb 15, 2011 at 2:05
-
$\begingroup$ @Sunil: unfortunately, the link does not help. :( $\endgroup$– Qiang LiFeb 15, 2011 at 3:15
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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$.
-
$\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 LiFeb 15, 2011 at 17:35
$\begingroup$
$\endgroup$
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
