Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

3 Answers 3

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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.