|
Assume that $0 \neq b \in \mathbb R^m$, and let $A \in \mathbb R^{m \times n}$. I am in search of a characterization of the minimizer of $F(x) = \| b - A x \|^2 + \| x \|^2$ One computes that at point $x$ we have $F'(\cdot) = -2\langle A^\ast b, \cdot \rangle + 2 \langle A^\ast Ax,\cdot \rangle + 2\langle x,\cdot \rangle$ We can conclude therefore: $(I + A^\ast A )x = A^\ast b$ What can be said about this system, and where are such systems relevant? |
|||
|
|
|
This doesn't anything more than other answers, but might be helpful from a details perspective. For any vector $v$, you can write $v^Tv=||v||_2^2$. Thus, \begin{align} ||b-Ax||^2+||x||^2=x^H{(I+A^TA)x-x^T(A^Tb)+||b||^2} \end{align} This is the standard unconstrained convex quadratic programming problem $f(x)=x^TQx-r^Tx+c$ and the solution is given by $x=Q^{-1}r$ where $Q$ is positive definite. Here $Q=I+A^TA$ (convince yourself why it should be positive definite) and $r=A^Tb$ |
|||
|
|
|
Solve this using least squares $$\pmatrix{A \\ I}x = \pmatrix{b \\ 0 }$$ and you minimize $$\left| \pmatrix{Ax - b \\ x}\right|^2 = \left| Ax-b\right|^2 +\left| x\right|^2$$ |
|||||||||||
|
|
Consider the matrix: $$A' = \left(\begin{matrix}A\\I\end{matrix}\right)$$ and let $$b'=\left(\begin{matrix}b \\ 0\end{matrix}\right)$$ Then $\|A'x-b'\|^2 = \|Ax-b\|^2 + \|x\|^2$ So you just need to be able to know how to solve the problem without the $\|x\|^2$ and general $A$. |
|||
|
|
