# Shae's Ramblings

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)

return x.T @ A @ x + b.T @ x + c



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)