Constructing an Explicit, Always-Invertible Matrix

构造一个显式的、总是可逆的矩阵 苏剑林 · 2019-03-01 · Mathematics matrix determinant

From the post Appreciating the identity det(exp(A)) = exp(Tr(A)), we learned that the matrix $\exp(\boldsymbol{A})$ is always invertible, with inverse given by $\exp(-\boldsymbol{A})$. The problem is that $\exp(\boldsymbol{A})$ is only a theoretical definition — writing it down like this isn't of much practical value, since it requires computing $\boldsymbol{A}^n$ for every case.

Is there a concrete example we could use? Yes there is, and in this post we'll construct an explicit, always-invertible matrix.

The idea is actually very simple. Suppose $\boldsymbol{x},\boldsymbol{y}$ are two column vectors of dimension $k$. Then $\boldsymbol{x}\boldsymbol{y}^{\top}$ is a $k\times k$ matrix, and we consider

\begin{equation}\begin{aligned}\exp\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)=&\sum_{n=0}^{\infty}\frac{\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)^n}{n!}\\ =&\boldsymbol{I}+\boldsymbol{x}\boldsymbol{y}^{\top}+\frac{\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}}{2}+\frac{\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}\boldsymbol{x}\boldsymbol{y}^{\top}}{6}+\dots\end{aligned}\end{equation}more

Notice that

\begin{equation}\boldsymbol{y}^{\top}\boldsymbol{x}=\langle \boldsymbol{x},\boldsymbol{y}\rangle\end{equation}

is actually just a scalar, so we can simplify further:

\begin{equation}\begin{aligned}\exp\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)=&\boldsymbol{I}+\boldsymbol{x}\boldsymbol{y}^{\top}\left(1+\frac{\langle \boldsymbol{x},\boldsymbol{y}\rangle}{2}+\frac{\langle \boldsymbol{x},\boldsymbol{y}\rangle^2}{6}+\dots\right)\\ =&\boldsymbol{I}+\boldsymbol{x}\boldsymbol{y}^{\top}\left(\frac{e^{\langle \boldsymbol{x},\boldsymbol{y}\rangle}-1}{\langle \boldsymbol{x},\boldsymbol{y}\rangle}\right) \end{aligned}\end{equation}

Now this matrix is fully concrete and can be computed easily, since it only involves scalar exponentiation. The expression in the parentheses, $(e^x - 1)/x$, has a removable discontinuity at $x=0$, where its value equals 1 when $x=0$.

By the identity $\det(\exp(\boldsymbol{A})) = \exp(\text{Tr}(\boldsymbol{A}))$, the determinant of this matrix is

\begin{equation}\det\left(\exp\left(\boldsymbol{x}\boldsymbol{y}^{\top}\right)\right)= e^{\langle \boldsymbol{x},\boldsymbol{y}\rangle}\end{equation}

and its inverse is

\begin{equation}\exp\left(-\boldsymbol{x}\boldsymbol{y}^{\top}\right)=\boldsymbol{I}-\boldsymbol{x}\boldsymbol{y}^{\top}\left(\frac{1 - e^{-\langle \boldsymbol{x},\boldsymbol{y}\rangle}}{\langle \boldsymbol{x},\boldsymbol{y}\rangle}\right)\end{equation}

which is also an explicit result.

Of course, a general matrix has $k^2$ independent parameters, whereas the matrix constructed here from two vectors has only $2k$ parameters — so in terms of expressive power, it's clearly insufficient. To boost expressiveness, we could consider multiplying several such matrices together:

\begin{equation}\exp\left(\boldsymbol{x}_1\boldsymbol{y}_1^{\top}\right)\exp\left(\boldsymbol{x}_2\boldsymbol{y}_2^{\top}\right)\exp\left(\boldsymbol{x}_3\boldsymbol{y}_3^{\top}\right)\dots\end{equation}

Note that this is generally not equal to

\begin{equation}\exp\left(\boldsymbol{x}_1\boldsymbol{y}_1^{\top}+\boldsymbol{x}_2\boldsymbol{y}_2^{\top}+\boldsymbol{x}_3\boldsymbol{y}_3^{\top}+\dots\right)\end{equation}

Well, after all this derivation, what's it actually good for?

Uh... honestly I don't know what it's good for either. Let's just appreciate it for what it is.

(Actually, my original intention was to use this kind of constructive approach to directly build invertible neural networks. Following this ready-made matrix, it isn't hard to construct an invertible fully-connected network, but I haven't yet figured out how to generalize it to convolutional layers. Once I've worked that out, I'll come back and discuss further applications of this matrix.)