MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Moore-Penrose bound question

Suppose that we are given an equation $Ax=b$. The minimum least-squares solution is of course $x_{m}=A^{\dagger}b$. What I want to know is whether there are known bounds on $||x-x_{m}||$. In the problem I am dealing with I want to estimate $||x||$ and I can find $x_{m}$.

I hope that this is well-known... :)

-
may be I am misunderstanding something but what is "x" ? it does not exist usually, it it exists then x_m=x ... I mean typically we use least squares when we have MORE equations than variables, so we canNOT find solution in general so we look for approximate solution which is x_m. – Alexander Chervov Jun 9 2012 at 7:30
@Alexander Chervov: This is a theoretical problem where I do know that $x$ exists and am trying to bound it. Basically, I'm trying to sort-of-generalize a well-known method to assess the effect of a perturbation of a Markov chain on the stationary distribution. – Felix Goldberg Jun 9 2012 at 10:23
@Felix Goldberg: It's a spelling joke. – Mark Meckes Jun 9 2012 at 13:21
@Mark, I was trying to point out the spelling error, en.wikipedia.org/wiki/… – Will Jagy Jun 9 2012 at 15:43
Now I see it (fixed). – Felix Goldberg Jun 9 2012 at 17:50
show 8 more comments

If $Ax=b$ has a unique solution $x^{*}$, then $x_{m}=x^{*}$.

If $Ax=b$ has infinitely many solutions, then $x_{m}$ will be one of these solutions. In particular, it will be the solution with the smallest two-norm. There will be other solutions $x$ such $\| x-x_{m} \|$ is arbitrarily large.

If $Ax=b$ has no solutions then it isn't clear at all what you mean by referring to a specific $x$.

Are you asking about what happens in the presence of noise in $A$ or the right hand side vector $b$? In these cases the condition number of $A$ can be used to bound the effect of the noise on the pseudoinverse solution. Unfortunately, if $\mbox{cond}(A)=\infty$, there is no bound.

-
 can you comment why if many solutions then x_m will have smallest 2-notm ? – Alexander Chervov Jun 12 2012 at 9:10 Alexander- this is an important property of the pseudoinverse solution that can be found in many textbooks. For example, it's in Strang's "Linear Algebra and its Applications." There isn't room in this comment for a complete proof, but the key point is that any least squares solution $x_{LS}$ can be written uniquely as $x_{LS}=x_{m}+x_{n}$, where $x_{m}$ (the pseudoinverse inverse solution) is in $R(A^{T})$ and $x_{n}$ is in $N(A)$. Since $N(A) \perp R(A^{T})$, $\| x_{LS} \|^{2}=\| x_{m} \|^{2}+ \| x_{n} \|^{2}$, and $\| x_{LS} \|$ is minimized when $x_{n}=0$. – Brian Borchers Jun 12 2012 at 14:26 It should also be clear that you can add any vector in $N(A)$ to $x_{m}$ to get another least squares solution. Thus if $N(A)$ is nontrivial, then the set of least square squares solutions is unbounded. – Brian Borchers Jun 13 2012 at 4:40 Brian thank you. Let me think . – Alexander Chervov Jun 14 2012 at 19:20