0
$\begingroup$

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... :)

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ 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. $\endgroup$
    – Alexander Chervov
    Commented Jun 9, 2012 at 7:30
  • 1
    $\begingroup$ @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. $\endgroup$
    – Felix Goldberg
    Commented Jun 9, 2012 at 10:23
  • 1
    $\begingroup$ @Felix Goldberg: It's a spelling joke. $\endgroup$
    – Mark Meckes
    Commented Jun 9, 2012 at 13:21
  • 1
    $\begingroup$ @Mark, I was trying to point out the spelling error, en.wikipedia.org/wiki/Moore%E2%80%93Penrose_pseudoinverse $\endgroup$
    – Will Jagy
    Commented Jun 9, 2012 at 15:43
  • 1
    $\begingroup$ Now I see it (fixed). $\endgroup$
    – Felix Goldberg
    Commented Jun 9, 2012 at 17:50

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ can you comment why if many solutions then x_m will have smallest 2-notm ? $\endgroup$
    – Alexander Chervov
    Commented Jun 12, 2012 at 9:10
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Brian Borchers
    Commented Jun 12, 2012 at 14:26
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Commented Jun 13, 2012 at 4:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .