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.

Say if $\vec{k}$ is a least squares solution to $A\vec{x}=\vec{b}$ such that $A\vec{x}=\vec{b}$ has no solutions. My guts feel tell me that for all constants $c\vec{k}$, where $c\in\mathbb{R}$, it is still a least squares solution to $A\vec{x}=c\vec{b}$ as long as $c$ isn't zero. But to write a proof on this, how should I start off with?

I know that $A\vec{x}=\vec{b}$ does not have a solution. So I have to do a projection to find the closest, that is $A\vec{k}=\vec{p}$ where $\vec{p}$ is the projected vector and is in the column space of $A$. So now, I am not going to care about $A\vec{x}=\vec{b}$ anymore. Then of course, if $A\vec{k}=\vec{p}$ has a solution, then $cA\vec{k}=c\vec{p} \Rightarrow Ac\vec{k}=c\vec{p}$ because it is just a combination the column space of $A$. Since $A\vec{k}=\vec{p}$ is the projected equation that has the closest solution, then this means $c\vec{k}$ indeed is a least squares solution to $A\vec{x}=\vec{b}$ for all $c\in\mathbb{R}$ and $c\neq0$.

Is my proving right? I find it very informal and the proof is somewhat not sharp enough.

share|improve this question
    
"Say if $\vec{k}$ is a least squares solution to $A\vec{x}=\vec{b}$ such that $A\vec{x}=\vec{b}$ has no solutions." - that's kinda sorta self-contradicting, eh? –  J. M. Aug 4 '11 at 12:53
    
hmm...maybe I'm not phrasing it properly. What I meant was $A\vec{x}=\vec{b}$ is inconsistent and cannot be solved. And $\vec{k}$ is its least squares solution. –  xenon Aug 4 '11 at 12:55
    
@J.M. Not at all: $A\vec{x}=\vec{b}$ is inconsistent, and $\vec{k}$ is the least squares solution to the problem (a vector such that $\lVert A\vec{k}-\vec{b}\rVert$ is minimized). –  Arturo Magidin Aug 4 '11 at 12:55
    
@Arturo: I was thinking "if $\vec k$ is an LS solution, why then are you saying that $A\vec{x}=\vec{b}$ doesn't have solutions"? But, yes, that'd be the reasonable phrasing... –  J. M. Aug 4 '11 at 12:58
    
If you think at the practical level, this can't be true. We have that $k$ is in some sense (well, a very definite sense) close to a solution, that $Ak$ is "near" b. Unless b is the zero vector, which it isn't, $A(100k)$ is nowhere near b. –  André Nicolas Aug 4 '11 at 13:02

3 Answers 3

up vote 1 down vote accepted

As to the new question, if $\vec{y}$ is a least squares solution to $A\mathbf{x}=\vec{b}$, and $c\neq 0$, is $c\vec{y}$ a least squares solution to $A\mathbf{x}=c\vec{b}$?

Note that $$\lVert A\vec{y}-c\vec{b} \rVert = \left\lVert cA\left(\frac{1}{c}\vec{y}\right) - c\vec{b}\right\rVert = |c|\left\lVert A\left(\frac{1}{c}\vec{y}\right) - \vec{b}\right\rVert.$$ So $\vec{y}$ is a least squares solution to $A\vec{x}=c\vec{b}$ if and only if $\lVert A\vec{y} - c\vec{b}\rVert$ is as small as possible, if and only if $\lVert A(\frac{1}{c}\vec{y}) - \vec{b}\rVert$ is as small as possible, if and only if $\frac{1}{c}\vec{y}$ is a least squares solution to $A\vec{x}=\vec{b}$; equivalently, $\vec{y}$ is a least square solution to $A\vec{x}=\vec{b}$ if and only if $c\vec{y}$ is a least squares solution to $A\vec{x}=c\vec{b}$, which is what you wanted to show.

share|improve this answer

This isn't right. First, intuitively, if $\vec{k}$ is a least-squares solution, this means that $A\vec{k}$ is close to $\vec{b}$. Multiplying $\vec{k}$ by some arbitrary real number would multiply $A\vec{k}$ by the same number, and this could take it very far from $\vec{b}$.

To engage with your thinking more directly, if $\vec{p}$ is the orthogonal projection of $\vec{b}$ into the column space of $A$, then $c\vec{p}$ is not in general. Visualizing this in 3-space is helpful. Say $\vec{b}$ is a point in 3-space. If $A\vec{x}=\vec{b}$ doesn't have a solution, then the column space of $A$ is some subspace of 3-space that doesn't include $\vec{b}$. Say it is a plane. Then if $\vec{k}$ is the least squares solution, $\vec{p}=A\vec{k}$ is the unique point in this plane that is closest to $\vec{b}$. Scaling $\vec{p}$ by something will take it further away from $\vec{b}$.

EDIT: now that you have edited the question,

YES, you are right; if $\vec{k}$ is the least-squares solution of $A\vec{x}=\vec{b}$, then $c\vec{k}$ is the least-squares solution of $A\vec{x}=c\vec{b}$. Furthermore, your reasoning is correct, though imprecisely articulated (and $\vec{b}$ should be $c\vec{b}$ at the end of the paragraph). I take your question to be about how to make your proof more precise.

Here is one way to do it. As you note, saying that $\vec{k}$ is a least-squares solution of $A\vec{x}=\vec{b}$ is equivalent to saying that $A\vec{k}=\vec{p}$ is the orthogonal projection of $\vec{b}$ into the column space of $A$. Let $\vec{q}=\vec{b}-\vec{p}$, so that $\vec{b}=\vec{p}+\vec{q}$, $\vec{p}$ is in $A$'s column space, and $\vec{q}$ is orthogonal to every vector in $A$'s column space.

Multiplying everything by $c \in \mathbb{R}$, we have $c\vec{b}=c\vec{p}+c\vec{q}$; $c\vec{p}$ is still in $A$'s column space (you noted this in your informal proof), and $c\vec{q}$ is still orthogonal to everything in $A$'s column space, since as a multiple of $\vec{q}$, it is orthogonal to everything $\vec{q}$ is orthogonal to. (This is what was missing from your argument, although you intuited it). This means that $c\vec{p}$ is the orthogonal projection of $c\vec{b}$ into $A$'s column space. Since $A(c\vec{k})=cA\vec{k}=c\vec{p}$ as you note, this means that $c\vec{k}$ is a least-squares solution to $A\vec{x}=c\vec{b}$.

share|improve this answer

$\bf k$ is a least squares solution means it is the value of $\bf x$ that minimizes the norm of $A{\bf x}-{\bf b}$. There is no reason why the norm of $Ac{\bf x}-{\bf b}$ should equal that of $A{\bf x}-{\bf b}$ (and every reason to believe it shouldn't), so no reason to think $c{\bf k}$ should be a least squares solution.

share|improve this answer
    
I think I missed out a $c$ in my equation just now. It should be if $\vec{k}$ is the least squares solution, it is also one to $A\vec{x}=c\vec{b}$. So when proving, do I just say $Ac{\bf x}-{\bf cb}$ is the same as $A{\bf x}-{\bf b}$? –  xenon Aug 4 '11 at 13:15
    
But $Ac{\bf x}-c{\bf b}$ isn't the same as $A{\bf x}-{\bf b}$ (unless $c$ is 1 or $A{\bf x}-{\bf b}$ is $\bf 0$) since it is $(c)(A{\bf x}-{\bf b})$. –  Gerry Myerson Aug 4 '11 at 22:43

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.