Completing the square in N dimensions « Justin Domke’s Weblog

Completing the square in N dimensions

Another one of those things that I’ve had to re-derive 100 times, and so I am posting here for future reference.

Take a quadratic equation for a vector $\bf x$ .

$a+{\bf b}^T{\bf x} + \frac{1}{2}{\bf x}^T C {\bf x}$ .

You want to convert this into the form

$\frac{1}{2}({\bf x}-{\bf m})^T M ({\bf x}-{\bf m})+v$ .

What are $M$ , ${\bf m}$ , and $v$ ?

First, assume $C$ is symmetric. Then we have, in decreasing order of obviousness,

$M=C$

${\bf m}=-C^{-1}{\bf b}$

$v = a-\frac{1}{2} {\bf b}^T C^{-1} {\bf b}$

Now, suppose $C$ is non-symmetric. (Of course, still being symmetric is okay, but you would be using a needlessly complicated formula…) Then,

$M = C$

${\bf m} = -(\frac{1}{2} C + \frac{1}{2}C^T)^{-1} {\bf b}$

$v = a - \frac{1}{2} {\bf m}^T M {\bf m}$

$= a - \frac{1}{2} {\bf b}^T (\frac{1}{2} C + \frac{1}{2} C^T)^{-1} C (\frac{1}{2}C + \frac{1}{2}C^T)^{-1} {\bf b}$

david Says:

November 2, 2009 at 11:26 pm
I like this. Seems like all of numerics is reducing nonlinear problems to linear ones. Always wondered if there was a generalization of the quadratic equation to operators but never got this far..