Least Squares Problem - Show that $F(x) = (b - Ax)^T(b - Ax) + \alpha x^T x $...

Question

Consider the function $$F(x) = (b - Ax)^T(b - Ax) + \alpha x^T x $$ where $A$ is a real $ m \times n$ matrix and $\alpha$ is a positive real number. We want the minimum point of $F$ for given $A$, $b$, and $\alpha$. Show that $$F(x + h) - F(x) = (Ah)^T(Ah) + \alpha h^T h >= 0$$ for $h$ a vector of order $n$, provided that $$(A^T A + \alpha I)x = A^Tb$$ This means that any solution of this linear system minimizes $F(x)$; hence, this is the normal equation.

---

I'm not really sure how to show solve this problem using the method of Least Squares. I have $$f(x) = \underbrace{(b - Ax)^T(b- Ax)}_{||b - Ax||^2} + \alpha \underbrace{x^T x}_{||x||^2}$$ but from here I don't really know what to do. For $$ x = \frac{ A^Tb}{(A^T A + \alpha I)}$$, does that... minimize $$F(x + h) - F(x) = (Ah)^T(Ah) + \alpha h^T h$$ ?

I'm confused

Answer 1

You can expand the terms directly, and the solution falls out fairly straightforwardly.

\begin{eqnarray} F(x+h) & = & (b - A(x+h))^T(b - A(x+h)) + \alpha(x+h)^T(x+h) \\ & = & ((b - Ax) - Ah)^T((b-Ax)-Ah) + \alpha( x^Tx + x^Th + h^Tx + h^Th) \\ & = & (b-Ax)^T(b-Ax) -(Ah)^T(b-Ax) - (b-Ax)^T(Ah) + (Ah)^T(Ah) + \alpha (x^Tx + x^Th + h^Tx + h^Th) \\ & = & (b-Ax)^T(b-Ax) + \alpha x^Tx - 2h^TA^T(b-Ax) + (Ah)^T(Ah) + 2\alpha h^Tx + \alpha h^Th \\ \\ F(x+h) - F(x) & = & (Ah)^T(Ah) + \alpha h^Th - 2h^TA^T(b-Ax) + 2\alpha h^Tx \\ & = & (Ah)^T(Ah) + \alpha h^Th - 2h^t(A^Tb - (A^TA + \alpha I)x) \\ & = & (Ah)^T(Ah) + \alpha h^Th \end{eqnarray}

Answer 2

Use Taylor polynomial of degree $2$ to expand $$ F(x+h)-F(x) = F'(x)h + \frac 12 F''(x)(h,h) + r. $$ Check that $r=0$ and $F'(x)=0$ for the given point $x$.