Optimization closed formsolution

Question

Hi I've tried this question, but doesn't have a clue about how to approach this. Here is the question, and thank you in advance for your help.

Suppose A ∈ $R^{m×n}$ is full column rank, and b ∈ $R^m$. Derive a closed-form solution (meaning a solution expressed involving the parameters A and b) to the optimization problem$$ (P) min ||Ax − b||_2 $$such that x ∈ $R^n$.

Be clear why your proposed solution is indeed the solution. [ Hint: $(A^T A)^{-1}$ exists since A is full column rank. Another hint: it doesn’t matter if the objective function is instead $||Ax − b||^2_2$]

I think we are trying to minimize an Euclidean norm, and to do that, I did:

$$|Ax−b|^2=(Ax−b)^t(Ax−b)=x^tA^tAx−2x^tA^tb+b^2$$ Am I on the right track?

Answer 1

$\newcommand\nsq[1]{{\left\lVert #1\right\rVert}^2}$I would suggest a different route. Notice that, as a map between vector spaces, we have $A:\mathbb{R}^n\longrightarrow\mathbb{R}^m$. We can decompose $\mathbb{R}^m$ as

$$\text{Im}(A)\oplus{\big(\text{Im}(A)\big)}^{\perp}.$$

Any $u\in\mathbb{R}^m$ can thus be uniquely written as $u_A+u_A^\perp$, where $u_A\in\text{Im}(A)$ and $u_A^\perp\in{\big(\text{Im}(A)\big)}^{\perp}$. Moreover, this decomposition satisfies $\nsq{u}=\nsq{u_A}+\nsq{u_A^\perp}$. Write then $b=b_A+b_A^{\perp}$.

Since $Ax\in\text{Im}(A)$ for all $x$, it follows that

$$\nsq{Ax-b}=\nsq{Ax-b_A-b_A^\perp}=\nsq{Ax-b_A}+\nsq{b_A^\perp}.$$

Notice that $\nsq{b_A^\perp}$ is independent of $x$, so that indeed the best we can do is minimize $\nsq{Ax-b_A}$. On the other hand, $b_A\in\text{Im}(A)$, so surely there is $x_0$ such that $Ax_0=b_A$. This guarantees a minimum, because the norm is non-negative.

Okay, but what about the closed form? Here is a general result of interest:

Let $\{u_1,\dots,u_n\}\subset\mathbb{R}^m$ be linearly independent and $M\in\mathbb{R}^{m\times n}$ be the matrix whose columns are given by the $u_i$. Then the orthogonal projection $P_M$ onto $\text{span}(u_1,\dots,u_n)=\text{Im}(M)$ is

$$P_M=M{\left(M^tM\right)}^{-1}M^t.$$

Do you think you can show this?

---

Using this, we find that $b_A=A{\left(A^tA\right)}^{-1}A^tb$, and at this point it's easy to check that

$$x_0={\left(A^tA\right)}^{-1}A^tb.$$