I have recently started to delve into someone else's code, and there is a part in there I don't quite understand. The authors of the code use some form of pre-conditioning to speed up the optimization. I wanted to inquire if you are familiar with this pre-conditioning, and could recommend some literature to read up on the method. Unfortunately, no name was provided, so I'll describe the author's approach in the following.
Assume we have a collection of $N$ points in some $D$-dimensional space $\mathbb{R}^D$. This space is defined in some polynomial basis, and we have an $N\times D$ matrix $\boldsymbol{B}$ containing the coordinates of the $N$ points in that basis. We now want to optimize some objective function $f(\theta,\boldsymbol{B})$ for a fixed $\boldsymbol{B}$ and variable $\theta$ (a vector of length $D$). We do this with a quasi-Newton optimizer, specifically BFGS.
For the pre-conditioning, the authors now first
- square the matrix $\boldsymbol{B}$ element-wise, then sum it along the rows ($N$-dimensions), and take the square root of the resulting vector. This yields a $D$-vector $\psi_n$.
- The authors then create a diagonal square matrix $\boldsymbol{D}^{-1}$ with $\frac{1}{\psi_n}$ as the diagonal entries.
- With the matrix $\bf{D}^{-1}$, the authors obtain a matrix $\boldsymbol{\Psi}=\boldsymbol{B} \cdot \boldsymbol{D}^{-1}$. I assume this normalizes the dimensions of $\boldsymbol{B}$.
- Then, the authors take the QR factorization of $\bf{\Psi}$ and only keep the $N\times D$ upper triangular matrix $\boldsymbol{R}$
- With this, we authors calculate a "preconditioning matrix" $\boldsymbol{A}=\boldsymbol{D}^{-1}\cdot \boldsymbol{R}^{-1}$. This matrix must be $D\times N$.
Apparently, this allows us to do a "regularized optimization" $f(\theta)$=$f(A\cdot\theta^\top)=g(\theta^\top)$. Their comments suggest that this somehow turns the optimization problem more 'spherical', reducing steep gradients in some dimensions. (Apparently, this makes it less difficult for the algorithm to walk up ridges, and then close in on the optimum.) After optimization, the results from the regularized objective $\theta^*_r$ can then be converted back by re-scaling it with $\theta^*=\boldsymbol{A}\cdot \theta^*_r$.
Do you know what method the authors are using here?
