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

6 Responses to Completing the square in N dimensions

1. david says:

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

2. edward says:

love it! Many thanks.

3. lynn says:

Decompose the matrix in the quadratic term as C = S + K, where S is symmetric and K is skew.

Since x’Kx = 0, without loss of generality you can replace C with S = (C + C’) / 2
in the function definition .

Then the formulae for the symmetric case apply for any matrix, after substituting S for C.

4. rdguerrerom says:

In your formula for v the factor should be 1/4 and not 1/2, right?

5. rdguerrerom says: