Completing the square for quadratic forms
Suppose you have a quadratic form \(f\) defined on \(\mathbb{R}^p\) :
$$ f(\mathbf{x}) \triangleq \mathbf{x}^\mathsf{T}\mathbf{A}\mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x} + c $$
“Completing the square” is mapping this expression to a factorized, simpler one:
$$ f(\mathbf{x}) \triangleq (\mathbf{x} – \bar{\mathbf{x}})^\mathsf{T}\mathbf{Q}\,(\mathbf{x} – \bar{\mathbf{x}}) + d $$
where \(\bar{\mathbf{x}}\) is the position of the ellipsoïd characterized by the eigenvalues of \(\mathbf{Q}\).
Algebraïc manipulations
Completing the square is analogous to the scalar case: first expand the candidate expression:
$$ f(\mathbf{x}) \triangleq \mathbf{x}^\mathsf{T}\mathbf{Q}\mathbf{x} + \bar{\mathbf{x}}^\mathsf{T}\mathbf{Q}\bar{\mathbf{x}} – 2 \bar{\mathbf{x}}^\mathsf{T} \mathbf{Q}^\mathsf{T}\mathbf{x} + d $$
Then, proceed by identifying the main terms, yielding the system
$$ \mathbf{Q} = \mathbf{A} \qquad \text{and} \qquad – 2\mathbf{Q}\bar{\mathbf{x}} = \mathbf{b} $$ assuming \(\mathbf{A}\) is invertible, we get \(\bar{\mathbf{x}} = -\frac12\mathbf{A}^{-1}\mathbf{b}\). Thus, we can proceed by adding and substracting the necessary terms:
\begin{align} f(\mathbf{x}) &= \mathbf{x}^\mathsf{T}\mathbf{A}\mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x} + c \\ &= \mathbf{x}^\mathsf{T}\mathbf{Q}\mathbf{x} – 2 \bar{\mathbf{x}}^\mathsf{T} \mathbf{Q}^\mathsf{T}\mathbf{x} + c \\ &= \mathbf{x}^\mathsf{T}\mathbf{Q}\mathbf{x} – 2 \bar{\mathbf{x}}^\mathsf{T} \mathbf{Q}^\mathsf{T}\mathbf{x} + \bar{\mathbf{x}}^\mathsf{T}\mathbf{Q}\bar{\mathbf{x}} – \bar{\mathbf{x}}^\mathsf{T}\mathbf{Q}\bar{\mathbf{x}} + c \\ &= \mathbf{x}^\mathsf{T}\mathbf{Q}\mathbf{x} + \bar{\mathbf{x}}^\mathsf{T}\bar{\mathbf{x}} – 2 \bar{\mathbf{x}}^\mathsf{T} \mathbf{Q}^\mathsf{T}\mathbf{x} + d \end{align}
finally yielding \(d = c\, – \,\bar{\mathbf{x}}^\mathsf{T}\mathbf{Q}\bar{\mathbf{x}} = c\, – \,\frac14\mathbf{b}^\mathsf{T}\mathbf{A}^{-1}\mathbf{b}\).
Writing this in a single equation, we get:
\begin{align} \mathbf{x}^\mathsf{T}\mathbf{A}\mathbf{x} + \mathbf{b}^\mathsf{T}\mathbf{x} + c = &\left(\mathbf{x}-\frac12\mathbf{A}^{-1}\mathbf{b}\right)^\mathsf{T}\mathbf{A}\left(\mathbf{x}-\frac12\mathbf{A}^{-1}\mathbf{b}\right)\\ &+ c\, – \,\frac14\mathbf{b}^\mathsf{T}\mathbf{A}^{-1}\mathbf{b} \end{align}
An example
Let's take an example of a quadratic form: we generate randomly our parameters \(\mathbf{A}, \mathbf{b}, c\) and obtain:
$$\mathbf{A} = \begin{bmatrix} 7.722 & 2.774 \\ 2.774 & 1.078 \end{bmatrix} \quad \mathbf{b} = \begin{bmatrix} 0.651 \\ -0.319 \end{bmatrix} \quad c = -0.848 $$
the snippet to generate this quadratic form in python is:
import jax.numpy as jnp
import numpy as np
from jax import vmap
_seed = 11
np.random.seed(_seed)
num_points = 2500
xgrid = ygrid = np.linspace(-10,10, num_points)
meshx, meshy = np.meshgrid(xgrid, ygrid)
points = np.vstack([meshx.ravel(), meshy.ravel()]).T
A = np.random.randn(2,2)
A = A @ A.T
A = np.round(A,3)
b = np.random.randn(2,1)
b = np.round(b, 3)
c = np.round(np.random.randn(1), 3)
A,b,c = jnp.array(A), jnp.array(b), jnp.array(c)
def quadratic_form(x):
return x.T @ A @ x + b.T @ x + c
qfvals = vmap(quadratic_form)(points)
the contours of this quadratic form are plotted below:
now let us plot the countours of the factorized version of \(f\):
they are the same, as expected. The snippet to reproduce this second experiment is:
def factorized_form(x):
x = x.reshape(-1,1)
xbar = 0.5 * jnp.linalg.inv(A) @ b
d = c - 0.25 * b.T @ jnp.linalg.inv(A @ A.T) @ b
return (x - xbar).T @ A @ (x - xbar) + d
qfvals = vmap(factorized_form)(points)
