Stuff I find slightly meaningful and close to achievable

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:

countours example

now let us plot the countours of the factorized version of \(f\):

factorized quadform

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)