least squares problem SVD consider the least squares problem $$\min_{x\in \mathbb{R}^n} \|Ax - b \|_2^2 + \|Lx \|_2^2, L \in \mathbb{R}^{n\times n}.$$ I am asked to show that the solution of this least squares problem is the same as the solution to
$$(A^TA + L^TL)x = A^Tb$$
My attempt: for the least squares problem $$\|A\hat{x} -b \|_2 = \min_{x \in \mathbb{R}^n} \|Ax - b \|_2 $$ have previously shown that the condition $$A^TA\hat{x} = A^Tb$$ is a necessary and sufficient condition for the minimiser $\hat{x}$ and I have been trying to apply it here, but to no avail.
 A: The problem can be posed in $\mathbb{R}^{n}\times\mathbb{R}^{n}$. If $(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$, the norm is
$$
                   \|(x,y)\| = \sqrt{\|x\|^2+\|y\|^2}.
$$
Define $M : \mathbb{R}^{n}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}\times\mathbb{R}^{n}$ by $M(x,y)=(Ax,Ly)$. The problem of minimizing
$$
        \|Ax-b\|^2+\|Lx\|^2,\;\;\; x \in \mathbb{R}^{n},
$$
becomes one of finding the closest point to $(b,0)\in\mathbb{R}^{n}\times\mathbb{R}^{n}$ in $\mathcal{M}=\{ M(x,x) = (Ax,Lx) : x \in \mathcal{R}^{n} \}$. This is the same as the orthogonal projection of $(b,0)$ onto the subspace $\mathcal{M}$. Such an orthogonal projection $(Ax_0,Lx_0)\in\mathcal{M}$ exists and is unique because the spaces are finite-dimensional. That does not mean $x_0$ is unique--only that $(Ax_0,Lx_0)$ is unique. The non-uniqueness of $x_0$ happens only if there is a non-zero element in the kernel of both $A$ and $L$; that is, $x_1$ is another solution $x_0$ iff $x_0-x_1 \in\mathcal{N}(A)\cap\mathcal{N}(L)$.
The orthogonal projection is uniquely determined by the orthogonality condition
$$
       \langle M(x_0,x_0)-(b,0),M(x,x)\rangle_{\mathbb{R}^{n}\times\mathbb{R}^{n}}=0 \\
       \langle (Ax_0-b,Lx_0),(Ax,Lx)\rangle_{\mathbb{R}^{n}\times\mathbb{R}^{n}}=0 \\
        \langle Ax_0-b,Ax\rangle_{\mathbb{R}^{n}}+\langle Lx_0,Lx\rangle_{\mathbb{R}^{n}} = 0 \\
      \langle A^{T}(Ax_0-b),x\rangle+\langle (L^{T}Lx_0,x\rangle = 0 \\
      \langle (A^{T}A+L^{T}L)x_0-A^{T}b, x\rangle = 0
$$
Because this must hold for all $x$, then the above is equivalent to solving for $x_0$ such that
$$
                (A^{T}A+L^{T}L)x_0 = A^{T}b \tag{$*$}.
$$
By the arguments given above, $x_0$ exists. The value of $(A^{T}A+L^{T}L)x_0$ is unique. This is confirmed by noting that
$$
          \mathcal{N}(A^{T}A+L^{T}L)=\mathcal{N}(A)\cap\mathcal{N}(L).
$$
There always exists a solution of $(*)$.
A: Let $\tilde{A}= \begin{bmatrix} A \\ L\end{bmatrix}$,
$\tilde{b}= \begin{bmatrix} b \\ 0 \end{bmatrix}$, then the problem reduces
to $\min {1 \over 2} \| \tilde{A} x - \tilde{b} \|$ for which you know the
necessary & sufficient condition for a minimum to be
$\tilde{A}^T (\tilde{A} x- \tilde{b}) = 0$.
Since $\tilde{A}^T  \tilde{A} = A^T A + L^T L$ and
$\tilde{A}^T  \tilde{b} = A^T b$, you have the desired result.
