Difference between objective function values of any feasible solution and optimal solution

Question

Suppose that $x^*$ is an optimal solution to the following least squares problem: $$ \min_{x\in R^n} f(x): = \frac{1}{2} \| Ax - b \|_2^2.$$
Clearly, we have $f(x) \ge f(x^*) \ \forall x \in R^n.$ Prove that the difference $[f(x) - f(x^*)]$ between the objective function values of any feasible solution and optimal solution is the following: $$ f(x) - f(x^*) = \frac{1}{2} \| Ax - Ax^*\|^2_2, \ \forall \ x \in R^n.$$

Answer 1

Let's expand the objective function $$\ f(x) = \frac{1}{2}\|Ax-b\|^2=\frac{1}{2}x^TA^TAx - b^TAx + \frac{1}{2}\|b\|^2 $$ Assume $x^*$ to be the minimum, $$\ \nabla f(x^*) = A^TAx^* - A^Tb = 0 \\ \implies A^Tb = A^TAx^* $$

Just plug this is in the below eqn to replace $b^TA$ and obtain the desired relation. $$\ f(x) - f(x^*) = \frac{1}{2}x^TA^TAx - b^TAx - \left( \frac{1}{2}{x}^{*T}A^TAx^* - b^TAx^* \right) $$