0
$\begingroup$

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.

  • 0
    "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?2011-08-04
  • 0
    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.2011-08-04
  • 0
    @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).2011-08-04
  • 0
    @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...2011-08-04
  • 0
    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.2011-08-04
  • 0
    FWIW: if you already have (multivariate) calculus machinery available to you, then you have a simple way of determining the "least solution" (at least for the case of $A$ having full rank). (If $A$ is rank-deficient, things are not as straightforward...)2011-08-04
  • 0
    @xEnOn: By your own argument, you are trying to find an $\vec{x}$ such that $A\vec{x}$ will equal $\vec{p}$, which is the closest point to $\vec{b}$ in the column space of $A$; but when you plug in $c\vec{x}$ instead of $\vec{x}$, **you don't get $\vec{p}$, you get something else unles $\vec{p}=\vec{0}$**. So $c\vec{x}$ cannot, in general, also be a least squares solution.2011-08-04
  • 0
    The question has now changed! Sure, with $cb$ on the right, the result is correct. But you did not change the description of a proof. That can be easily done by minor editing.2011-08-04
  • 0
    With the new attempt at phrasing, note that "still" is incorrect ("it's still a least squares solution to $A\vec{x}=c\vec{b}$"). There is no "still" because $c\vec{x}$ was not a least squares solutions *before*.2011-08-04

3 Answers 3

0

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

  • 0
    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}$?2011-08-04
  • 0
    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})$.2011-08-04
2

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

1

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.