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,


{\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. Pingback: About the ‘completing the square’ – Liming Shi's Homepage

  5. rdguerrerom says:

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s