1

We know from linear algebra, the least square solution of linear equation system : $$Ax=b$$ always exists. That is, the equation $$A^TAx=A^Tb$$ always has at least one solution. $\bar x$ is the solution of the equation. I want to prove that $\forall r \in\mathbb R^n$ $$\|A \bar x - b\|_2 \leq \|Ar - b\|_2$$ Any hints on how to approach this problem would be helpful. Thanks!

Michael Hardy
  • 1
  • 31
  • 294
  • 591
Art of Juking
  • 73
  • 8
  • 1
    See [here](https://math.stackexchange.com/questions/187335/prove-existence-of-solution-of-ax-b-by-least-squares?rq=1). – Dietrich Burde Apr 21 '21 at 13:45
  • $$ \begin{align} Ar-b & = (Ar-A\overline x) + (A\overline x - b) \\ {} \\ \|Ar-b\|^2 & = \|Ar-A\overline x\|^2 + (Ar-A\overline x)\cdot(A\overline x - b) + \|A\overline x-b\|^2. \end{align} $$ Can you show that the dot-product is zero? $\qquad$ – Michael Hardy Apr 21 '21 at 14:10
  • I am not sure how to, is there something orthogonal that I can use? – Art of Juking Apr 21 '21 at 14:29

1 Answers1

0

Let $b \in \mathbb{R}^m$ and $A \in \mathbb{R}^{m\times n}$. The least squares solution $\bar{x}$ solves the problem $$\min_{r\in \mathbb{R}^n}\|Ar-b\|^2_2$$ Indeed $$\|Ar-b\|^2_2=(Ar-b)^T(Ar-b)=r^TA^TAr-r^TA^Tb-b^TAr+b^Tb=r^TA^TAr-2r^TA^Tb+b^Tb$$ By taking the derivative with respect to $r$ and setting it equal to zero we obtain $$2A^TAr-2A^Tb=0$$ $$\bar{x}=r^*=(A^TA)^{-1}A^Tb$$ Therefore $$\|A\bar{x}-b\|^2_2\leq\|Ar-b\|^2_2, \ \forall r \in \mathbb{R}^n$$

Snoop
  • 12,871
  • 4
  • 8
  • 29
  • You took the derivative wrt r, but we don't know if the value $\ bar x$ is minimum or maximum. In order to determine minimum or maximum, we should also take a second-order derivative, right? – Art of Juking Apr 22 '21 at 13:54
  • 1
    See [here](https://math.stackexchange.com/questions/483339/proof-of-convexity-of-linear-least-squares) – Snoop Apr 22 '21 at 13:58