Take the 2-minute tour ×

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?

share|improve this question
add comment

3 Answers

up vote 0 down vote accepted

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$

share|improve this answer
add comment

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$$

share|improve this answer
And the only thing I can say about the system is that it is how I view ridge regression. It gives equal weighted importance to solving $Ax=b$ and to solving $x=0$. –  adam W Mar 7 '13 at 16:03
"Solve" is a bit of a misnomer, since you aren't finding an $x$ where equality is true. But maybe that's common language for people who do these sorts of problems regularly? –  Thomas Andrews Mar 7 '13 at 16:06
@Thomas I guess it depends on the dimensions, but either way if I knew of better terminology I would use it. Minimize the system with respect to $x$? Use $\approx$ symbol? It is all about context, since you are correct that there may not be an exact solution. –  adam W Mar 7 '13 at 16:10
The dimensions don't really matter - the only way for an exact solution is if $x=Ix=0$ and hence also $b=0$. –  Thomas Andrews Mar 7 '13 at 17:11
@Thomas yes the extended version will always be under-determined since $I$ necessarily has the conformable dimension to $x$. The original system of $Ax=b$ is the one to which I was referring regarding the dimensions and possible "solutions". –  adam W Mar 7 '13 at 17:54
add comment

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$.

share|improve this answer
add comment

Your Answer


