Differentiating Gram Schmidt

Gram-Schmidt orthogonalization is a well-known technique where an non-orthogonal set of column vectors ${\bf q}_i\in\mathbb{R}^D$ is made orthogonal via

$\begin{align*} {\bf w}_i = {\bf q}_i - \sum_{j=1}^{i-1}\left(\frac{{\bf w}_j^T{\bf q}_i}{{\bf w}_j^T{\bf w}_j}\right){\bf w}_j, \quad i = 1,\cdots, d. \end{align*}$

We have developed a simple recurrence relation to compute the derivatives of ${\bf w}_i$ with respect to ${\bf q}_i$ :

$\boxed{\begin{align*} \frac{\partial{\bf w}_1}{\partial{\bf q}_1} =: D_{11} = I_D \\ \frac{\partial{\bf w}_i}{\partial{\bf q}_i} =: D_{ii} = D_{i-1,\, i-1} - \frac{{\bf w}_{i-1}{\bf w}_{i-1}^T}{{\bf w}_{i-1}^T{\bf w}_{i-1}},\quad i > 1, \\ \frac{\partial{\bf w}_i}{\partial{\bf q}_k} = \sum_{j=1}^{i-1}D_{ij}\frac{\partial{\bf w}_j}{\partial{\bf q}_k},\quad i\neq k, \quad i > k, \\ D_{ij}:= -\frac{\partial}{\partial{\bf w}_j}\left[\left(\frac{{\bf w}_j^T{\bf q}_i}{{\bf w}_j^T{\bf w}_j}\right){\bf w}_j\right] = -\left[\frac{1}{{\bf w}_j^T{\bf w}_j}\;{\bf w}_j{\bf q}_i^T - \frac{2{\bf w}_j^T{\bf q}_i}{({\bf w}_j^T{\bf w}_j)^2}\;{\bf w}_j{\bf w}_j^T + \frac{{\bf w}_j^T{\bf q}_i}{{\bf w}_j^T{\bf w}_j}\; I_D\right],\quad i\neq j,\quad i > j. \end{align*}}$

Gram-Schmidt vectors are often normalized in practice, to obtain the set:

$\begin{align*} W = \bigg\{\frac{{\bf w}_1({\bf q}_1)}{\lVert{\bf w}_1({\bf q}_1)\rVert_2},\;\;\frac{{\bf w}_2({\bf q}_1, {\bf q}_2)}{\lVert{\bf w}_2({\bf q}_1, {\bf q}_2)\rVert_2},\;\;\cdots\;\;,\frac{{\bf w}_d({\bf q}_1,{\bf q}_2\,\cdots,{\bf q}_d)}{\lVert{\bf w}_d({\bf q}_1,{\bf q}_2\,\cdots,{\bf q}_d)\rVert_2}\bigg\}. \end{align*}$

The derivatives of these normalized vectors are obtained by premultiplying the unnormalized derivative with a matrix that only depends upon ${\bf w}_i$ :

$\begin{align*} \boxed{\frac{\partial}{\partial{\bf q}_k}\left(\frac{{\bf w}_i}{\lVert{\bf w}_i\rVert_2}\right) = \left[\frac{I_D}{\lVert{\bf w}_i\rVert_2} - \frac{{\bf w}_i{\bf w}_i^T}{\lVert{\bf w}_i\rVert^3_2}\right]\frac{\partial{\bf w}_i}{\partial{\bf q}_k}.} \end{align*}$

Contents repository

The following files are present in the repository:

gram_schmidt_derivatives.py: a Python3 class for computing Gram-Schmidt vectors and the derivatives.
derivation.pdf: a document which details the derivation of the derivative expressions.
check_derivatives.ipynb: a Jupyter notebook which verifies the validity of the derivative expressions, and which verifies the Python3 implementation of gram_schmidt_derivatives.py. Also acts as a tutorial for the Python3 class.

Development was funded by the EU Horizon 2020 project VECMA.

Gram Schmidt Derivatives

Repository for computing the derivatives of Gram-Schmidt vectors

Differentiating Gram Schmidt

Contents repository