In this post, I shall first describe a new word embedding algorithm that I came up with called a matrix product optimized (MPO) word embedding, and I will prove a theorem that completely interprets this word embedding in the simplest case. While it is probably infeasible to mathematically characterize a word embedding with a mathematical proof when the corpus is something that one encounters in practice, this theorem should be a signal that such a word embedding (or a similar word embedding) should be interpretable and mathematical in other ways as well. This theorem also illustrates the way that MPO word embeddings should behave.

Unlike most word embedding algorithms, MPO word embeddings are matrix-valued so that they map tokens to matrices instead of simply mapping tokens to vectors. In our case, the matrices are not necessarily real matrices as they may be complex or even quaternionic matrices. MPO word embeddings also differ from other word embedding algorithms in that they are not constructed using neural networks though we still use gradient ascent.

Why MPO word embeddings?

Since tokens often have many meanings depending on context, it seems better to represent a token in a form where it is easy or easier to separate the individual meanings of a token. While vectors may be good for representing individual meanings of tokens, it is better to represent a polysemantic token as a matrix instead of a vector. If someone were to give me a task of interpreting a word embedding, I would be much happier if the word embedding were a matrix-valued word embedding that neatly organized each of the meanings of a polysemantic token into a matrix than if the word embedding were a vector-valued word embedding where each of the individual meanings of the token were awkwardly smushed together in a vector.

Spaces of matrices have additional structure that is lacking in vector spaces, and one can use this additional structure to analyze or interpret our word embedding. This additional structure also means that matrix-valued word embeddings should behave more mathematically than vector-valued word embeddings.

MPO word embeddings also satisfy some interesting properties. Let ${\chi }_A$ denote the fitness level of a random MPO word embeddings that we obtain from the set $A$ where $A$ consists of the corpus that we are training our word embedding on along with a couple of hyperparameters. Then the random variable ${\chi }_A$ will often have very low entropy or even zero entropy. Since ${\chi }_A$ often has zero/low entropy, trained MPO word embeddings will not contain any/much random information that was not already present in the training data. It will be easier to interpret machine learning models when the trained model only depends on the training data and hyperparameters and which does not depend on random choices such as the initialization. Quaternionic and complex MPO word embeddings will often become real word embeddings after a change of basis. This means that MPO word embeddings behave quite mathematically, and it seems like machine learning models that behave in ways that mathematicians like would be more interpretable and understandable than other machine learning models.

Quaternionic matrices:

In this section, we shall go over the basics of quaternionic matrices. I assume that the reader is already familiar with ideas in linear algebra up through the singular value decomposition. Much of the basic theory of quaternionic matrices is a straightforward generalization of the theory of complex matrices. I hope you are also familiar with the quaternions, but if you are not, then I will remind you the definition and basic facts about quaternions. We refer the reader to [1] for facts about quaternions. You may skip this section if you simply care about the real and complex cases.

If $A$ is a square real, complex, or quaternionic matrix, then the spectral radius of $A$ is

$\rho \left(A\right)={lim}_{n\to \infty }\parallel A^n{\parallel }^{1/n}$ where $\parallel \cdot \parallel$ is any matrix norm (since we are taking the limit, it does not matter which matrix norm we choose). If $A$ is a real or complex matrix, then

$\rho \left(A\right)=max\{|\lambda |:\lambda \text{is an eigenvalue of}A\}$. The same fact holds for quaternionic matrices, but we have to be careful about how we define the eigenvalues of quaternionic matrices due to non-commutativity.

The division ring $H$ of quaternions is the 4-dimensional associative but non-commutative algebra over the field of real numbers spanned by elements $1,i,j,k$  (so $H=\{a+bi+cj+dk:a,b,c,d\in R\}$) where quaternionic multiplication is the unique associative (but non-commutative) bilinear operation such that $i^2=j^2=k^2=ijk=-1$. We observe that if $\lambda \in R,\mu \in H$, then $\lambda \mu =\mu \lambda$. It is easy to show that $ij=k,jk=i,ki=j,ji=-k,kj=-i,ik=-j$.

Recall that the conjugate and the absolute value of a quaternion are defined by

$\overline{a+bi+cj+dk}=a-bi-cj-dk$ and $|a+bi+cj+dk|=\sqrt{a^2+b^2+c^2+d^2}$ whenever $a,b,c,d\in R$. If $u,v\in H$, then $\overline{u}\cdot \overline{v}=\overline{v\cdot u}$ and $|u|\cdot |v|=|u\cdot v|$. Observe that the field of complex numbers $C=\{a+bi:a,b\in R\}$ is a subring of $H$.

If $A=(a_{i,j}{)}_{i,j}$ is a quaternionic matrix, then define the adjoint of $A$ to be $A^{\ast }=(\overline{a_{j,i}}{)}_{i,j}$. While the adjoint of a quaternionic matrix is well-behaved, the transpose of a quaternionic matrix is not very well behaved since we typically have $A^T{B}^T\ne (BA{)}^T$ but $A^{\ast }{B}^{\ast }=(BA{)}^{\ast }$ for quaternionic matrices $A,B$.

We shall now associate $m\times n$-quaternionic matrices with $2m\times 2n$-complex matrices.

Suppose that $A_1,A_2$ are $m\times n$-complex matrices. Then the associated quaternionic complex matrix  of the quaternionic matrix $A=A_1+A_2\cdot j$ is the complex matrix 

${\chi }_A=\left[\begin{array}{cc}{A}_1& A_2\\ -\overline{A_2}& \overline{A_1}\end{array}\right]$. We observe that ${\chi }_{A+B}={\chi }_A+{\chi }_B$, and ${\chi }_{AB}={\chi }_A{\chi }_B$, and ${\chi }_{A^{\ast }}=({\chi }_A{)}^{\ast }$ whenever $A,B$ are quaternionic matrices and the operations are defined.

An eigenvalue of a quaternionic matrix $A$ is a quaternion $\lambda$ such that $Ax=x\cdot \lambda$ for some non-zero vector $x$.

Observation: If $\lambda$ is an eigenvalue of a quaternionic matrix $A$ corresponding to the eigenvector $x$  and $\mu$ is an eigenvalue of a quaternionic matrix $B$ corresponding to the same eigenvector $x$, then $ABx=Ax\mu =x\lambda \mu$, so $\lambda \mu$ is an eigenvector of the quaternionic matrix $AB$.

Observation: If $\lambda$ is an eigenvalue of a product of quaternionic matrices $AB$ and$ABx=x\lambda$, then $\left(BA\right)\left(Bx\right)=\left(Bx\right)\lambda$, so if $Bx\ne 0$, then $\lambda$ is also an eigenvalue of $BA$. In particular, $AB$ and $BA$ have the same non-zero eigenvalues.

Observation: If $A$ is a quaternionic matrix and $\lambda$ is an eigenvalue of $A$, then whenever $\mu$ is a non-zero quaternion, the value ${\mu }^{-1}\lambda \mu$ is also an eigenvalue of $A$.

Proof: If $\lambda$ is an eigenvalue of $A$, then there is some non-zero quaternionic vector $x$ with $Ax=x\lambda$. Therefore, set $y=x\mu$. Then $Ay=Ax\mu =x\lambda \mu =y\mu \lambda {\mu }^{-1}$, so ${\mu }^{-1}\lambda \mu$ is an eigenvalue of the quaternionic matrix $A$. $\square$

Let $G$ denote the group of all quaternions $\lambda$ with $|\lambda |=1$. Let $\text{SU}\left(n\right)$ denote the group of all $n\times n$-unitary matrices with determinant $1$. Let $\text{O}\left(n\right)$ denote the group of all $n\times n$- orthogonal matrices. Then the mapping $\lambda \mapsto {\chi }_{\lambda }$ is an isomorphism from $G$ to $\text{SU}\left(2\right)$. Let $V$ be the vector subspace of $H$ consisting of all elements of the form $ai+bj+ck$ where $a,b,c$ are real numbers. Then $V$ is an inner product space where inner product is the standard dot product operation on $V$ where $⟨ai+bj+ck,ri+sj+tk⟩=ar+bs+ct$ and where $⟨\lambda ,\mu ⟩=-\text{Re}\left(\lambda \mu \right)$ for quaternions $\lambda ,\mu \in V$). Then we can identify $\text{O}\left(3\right)$ with the linear transformations that preserve this inner product. We may now define a group homomorphism $\varphi :G\to \text{O}\left(3\right)$ by letting $\varphi \left(\lambda \right)\left(\mu \right)=\lambda \mu {\lambda }^{-1}$. Then the homomorphism $\varphi$ is a surjective homomorphism. In fact, $\text{O}\left(3\right)$ is a connected Lie group with ${\pi }_1\left(\text{O}\right(3\left)\right)\simeq Z_2$, and the group $G$ is simply connected; $G$ is the universal cover of the lie group $\text{O}\left(3\right)$. From these facts about quaternions, we may make a few observations:

Observation: If ${\lambda }_1,{\lambda }_2$ are quaternions, then there is some $\mu$ with ${\lambda }_2=\mu {\lambda }_1{\mu }^{-1}$ if and only if $\text{Re}\left({\lambda }_1\right)=\text{Re}\left({\lambda }_2\right)$ and $|{\lambda }_1|=|{\lambda }_2|$.

Observation: Suppose that $A$ is a square quaternionic matrix and ${\lambda }_1,{\lambda }_2$ are quaternions with $\text{Re}\left({\lambda }_1\right)=\text{Re}\left({\lambda }_2\right)$ and $|{\lambda }_1|=|{\lambda }_2|$. Then ${\lambda }_1$ is an eigenvalue of $A$ if and only if ${\lambda }_2$ is an eigenvalue of $A$.

Observation: Suppose that $x$ is a quaternionic vector, and $x_1,x_2$ are complex vectors with $x=x_1+x_2\cdot j$. Suppose furthermore that $\lambda$ is a complex number. Then $Ax=x\lambda$ if and only if ${\chi }_A\left[\begin{array}{c}{x}_1\\ -\overline{x_2}\end{array}\right]=\lambda \left[\begin{array}{c}{x}_1\\ -\overline{x_2}\end{array}\right]$. In particular, $\lambda$ is an eigenvalue of $A$ if and only if $\lambda$ is an eigenvalue of ${\chi }_A$.

Observation: Let $A$ be a square quaternionic matrix. Then the following quantities are equivalent:

1. $\rho \left({\chi }_A\right)$
2. ${lim}_{n\to \infty }\parallel A^n{\parallel }^{1/n}$
3. $max\{|\lambda |:\lambda \text{is an eigenvalue of}A\}$.

We shall therefore define the spectral radius of a square quaternionic matrix $A$ to be $\rho \left({\chi }_A\right)$ (or any of the quantities in the above observation).

If $A$ is a quaternionic matrix, then we say that $A$ is Hermitian, normal, or unitary respectively if ${\chi }_A$ is Hermitian, normal, or unitary. If $A$ is an $n\times n$-quaternionic matrix, then $A$ is Hermitian iff $A=A^{\ast }$, and $A$ is normal iff $A{A}^{\ast }=A^{\ast }A$, and $A$ is unitary iff$1_n=A{A}^{\ast }=A^{\ast }A$.

If $u,v$ are quaternionic column vectors, then define the quaternionic inner product $⟨u,v{⟩}_H$ of $u,v$ by $⟨u,v{⟩}_H=v^{\ast }u$. We observe that the quaternionic inner product is real bilinear and conjugate symmetric $⟨u+v,w{⟩}_H=⟨u,w{⟩}_H+⟨v,w{⟩}_H$,$⟨u,v{⟩}_H=\overline{⟨v,u{⟩}_H}$. The quaternionic inner product preserves right scalar multiplication $⟨u\lambda ,v{⟩}_H=⟨u,v{⟩}_H\lambda$. We define the real inner product of two quaternionic vectors by setting$⟨u,v{⟩}_R=\text{Re}\left(v^{\ast }u\right)=\frac{1}{2}(u^{\ast }v+v^{\ast }u)=\text{Re}(⟨u,v{⟩}_H)=\frac{1}{2}(⟨u,v{⟩}_H+⟨v,u{⟩}_H)$. We may recover the quaternionic inner product from the real-valued inner product since $⟨u,v{⟩}_H=⟨u,v{⟩}_R-⟨ui,v{⟩}_{R}i-⟨uj,v{⟩}_{R}j-⟨uk,v{⟩}_{R}k$ for quaternionic vectors $u,v$.

Observation: If $u,v$ are quaternionic vectors, then $\rho \left(u{v}^{\ast }\right)=|v^{\ast }u|=|⟨u,v{⟩}_H|$ and $\parallel u{v}^{\ast }{\parallel }_p=\parallel u\parallel \cdot \parallel v\parallel$ for $1\le p\le \infty$.

Observation: Suppose $u,v$ are quaternionic vectors. Then $|⟨u,v{⟩}_H|\le \parallel u\parallel \cdot \parallel v\parallel$.

Observation: Suppose $u,v$ are non-zero quaternionic vectors. If $|⟨u,v{⟩}_H|=\parallel u\parallel \cdot \parallel v\parallel$, then $v\gamma =u$ for some quaternion $\gamma$.

Counterexample: In general, if $\alpha$ is a non-zero quaternion, and $u$ is a quaternionic vector, then $\parallel (\alpha u{)}^{\ast }u\parallel \ne \parallel \alpha u\parallel \cdot \parallel u\parallel$.

Observation: Let $A$ be an $m\times n$ quaternionic matrix, and let $B$ be an $n\times m$-quaternionic matrix. Then the following are equivalent:

1. $A=B^{\ast }$
2. $⟨Au,v{⟩}_H=⟨u,Bv{⟩}_H$ for all quaternionic vectors $u,v$.
3. $⟨Au,v{⟩}_R=⟨u,Bv{⟩}_R$ for all quaternionic vectors $u,v$.

Proposition: Let $A$ be a quaternionic matrix. Then the following are equivalent:

1. $⟨Au,Av{⟩}_H=⟨u,v{⟩}_H$ for all quaternionic vectors $u,v$.
2. $⟨Au,Av{⟩}_R=⟨u,v{⟩}_R$ for all quaternionic vectors $u,v$.
3. $\parallel Au\parallel =\parallel u\parallel$ for all quaternionic vectors $u$.
4. $A^{\ast }A=I$
5. ${\chi }_A$ is an isometry.

If $A$ is a square quaternionic matrix, then the above statements are all equivalent to the following:

6. $A$ is unitary.

Theorem: (quaternionic singular value decomposition) If $A$ is a quaternionic matrix, then there exists quaternionic unitary matrices $U,V$ where $UAV$ is a diagonal matrix $D$ with non-negative real non-increasing diagonal entries.

In the above theorem, the diagonal entries in $D$ are called the singular values values of $A$ and they are denoted by ${\sigma }_1\left(A\right),\dots ,{\sigma }_n\left(A\right)$ where ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_n\left(A\right)$.

If $A$ is a real, complex, or quaternionic matrix, and $1\le p\le \infty$ then define the Schatten $p$-norm of $A$ to be $\parallel A{\parallel }_p=\parallel \left({\sigma }_1\right(A),\dots ,{\sigma }_n(A\left)\right){\parallel }_p$ where we define $\parallel (x_1,\dots ,x_n){\parallel }_p=(|x_1{|}^p+\cdots +|x_n{|}^p{)}^{1/p}$ for $1\le p<\infty$ and $\parallel (x_1,\dots ,x_n){\parallel }_{\infty }=max(|x_1|,\dots ,|x_n|)$.

Observation: If $A$ is a quaternionic matrix with singular values $\left({\sigma }_1\right(A),\dots ,{\sigma }_n(A\left)\right)$, then ${\chi }_A$ has singular values $\left({\sigma }_1\right(A),{\sigma }_1(A),{\sigma }_2(A),{\sigma }_2(A),\dots ,{\sigma }_n(A),{\sigma }_n(A\left)\right)$. In particular,$\parallel A{\parallel }_{\infty }=\parallel {\chi }_A{\parallel }_{\infty }$ and $\parallel {\chi }_A{\parallel }_p=2^{1/p}\cdot \parallel A{\parallel }_p$, so $\parallel A{\parallel }_p=2^{-1/p}\cdot \parallel {\chi }_A{\parallel }_p$ whenever $1\le p<\infty$.

Observation: If $A$ is a quaternionic matrix, then $\parallel A{\parallel }_{\infty }=max\frac{\parallel Av\parallel }{\parallel v\parallel }$.

If $A$ is an $n\times n$-quaternionic matrix, then define the quaternionic trace of $A$ as

$\text{HTr}\left(A\right)={\sum }_{r=1}^n{a}_{r,r}$. In general, $\text{HTr}\left(AB\right)\ne \text{HTr}\left(BA\right)$, so the notion of the quaternionic trace is deficient.

If $A$ is an $n\times n$-quaternionic matrix, then define the real trace of $A$ as$\text{RTr}\left(A\right)={\sum }_{r=1}^n\text{Re}\left(a_{r,r}\right).$ We observe that $\text{Tr}\left({\chi }_A\right)=2\text{RTr}\left(A\right)$ and$\text{RTr}\left(AB\right)=\text{RTr}\left(BA\right)$ whenever $A,B$ are quaternionic matrices.

Observe that we can recover $\text{HTr}$ from $\text{RTr}$ by using the formula $\text{HTr}\left(A\right)=\text{RTr}\left(A\right)-i\cdot \text{RTr}(i\cdot A)-j\cdot \text{RTr}(j\cdot A)-k\cdot \text{RTr}(k\cdot A)$.

If $A,B$ are $n\times n$-quaternionic matrices, then define the real-valued Frobenius inner product $⟨A,B{⟩}_R$ as $⟨A,B{⟩}_R=\text{RTr}\left(A{B}^{\ast }\right)$.

If $A=(a_{r,s}+b_{r,s}i+c_{r,s}j+d_{r,s}k{)}_{r,s}$ and $B=(w_{r,s}+x_{r,s}i+y_{r,s}j+z_{r,s}k{)}_{r,s}$ where every $a_{r,s},b_{r,s},c_{r,s},d_{r,s},w_{r,s},x_{r,s},y_{r,s},z_{r,s}$ is real, then

$⟨A,B{⟩}_R={\sum }_{r,s}{a}_{r,s}{w}_{r,s}+b_{r,s}{x}_{r,s}+c_{r,s}{y}_{r,s}+d_{r,s}{z}_{r,s}$. Define $\parallel A{\parallel }_R=\sqrt{⟨A,A{⟩}_R}$.

We observe that if $U,V$ are unitary, then $\parallel UAV{\parallel }_R^2=⟨UAV,UAV⟩=\text{RTr}\left(UAV\right(UAV{)}^{\ast })$

$=\text{RTr}\left(UAV{V}^{\ast }{A}^{\ast }{U}^{\ast }\right)=\text{RTr}\left(AV{V}^{\ast }{A}^{\ast }{U}^{\ast }U\right)=\text{RTr}\left(A{A}^{\ast }\right)=\parallel A{\parallel }_R^2$.

In particular, if $A=UDV$ where $U,V$ are unitary and $D$ is diagonal with diagonal entries ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_n\left(A\right)$, then $\parallel A{\parallel }_R^2=\parallel D{\parallel }_R^2={\sigma }_1(A{)}^2+\cdots +{\sigma }_n(A{)}^2=\parallel A{\parallel }_2^2$. 

MPO word embeddings

Let $K$ denote either the field of real numbers, complex numbers, or the division ring of quaternions. Let $A$ be a finite set (in our case, $A$ will denote the set of all tokens). Let $Q_d(K;A)$ be the set of all functions $f:A\to M_d\left(K\right)$ such that ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$. Observe that $Q_d(K;A)$ is compact. Define a function $L_{d,K}:A^{\ast }\times Q_d(K;A)\to [0,\infty )$ by letting $L_{d,K}(a_1\dots a_n,f)=\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}$. We say that $f$ is an MPO word pre-embedding for the string of tokens $a_1\dots a_n$ if the quantity $L_{d,K}(a_1\dots a_n,f)$ is locally maximized. To maximize $L_{d,K}(a_1\dots a_n,f)$, the function $f$ must simultaneously satisfy two properties. Since ${\sum }_{a\in A}f\left(a\right)f(a{)}^{\ast }=1_d$, the matrices $\left(f\right(a){)}_{a\in A}$ must be spread out throughout all the $d$ dimensions. But we also need for the matrices $f\left(a_r\right)$ to be compatible with $f\left(a_{r-1}\right)$ and $f\left(a_{r+1}\right)$ and more generally with $f\left(a_s\right)$ for $s$ near $r$.

We say that a collection of vectors $(v_1,\dots ,v_n)$ is a tight frame if$v_1{v}_1^{\ast }+\cdots +v_n{v}_n^{\ast }=\lambda \cdot 1_d$ for some necessarily positive constant $\lambda$. We say that a tight frame $(v_1,\dots ,v_n)$ is an equal norm tight frame if $\parallel v_1\parallel =\cdots =\parallel v_n\parallel$.

Theorem: Suppose that $d\le n$. Let $K$ denote either the field of real numbers or complex numbers. Let $S$ denote the unit sphere in $K^d$. Then the local minimizers of the frame potential $FP:S^n\to [0,\infty )$ defined by $FP(v_1,\dots ,v_n)={\sum }_{j=1}^n{\sum }_{k=1}^n|⟨v_j,v_k⟩{|}^2$ are global minimizers which are tight frames for $K^d$. In particular, there exists an equal norm tight frame $v_1,\dots ,v_n\in R^d$ whenever $d\le n$.

See [2, Thm 6.9] for a proof.

Theorem: Suppose that $K$ is the field of real numbers, complex numbers, or the division ring of quaternions. Let $|A|=n,A=\{a_1,\dots ,a_n\}$. Then $L_{d,K}(a_1\dots a_n,f)\le \sqrt{d/n}$ and $L_{d,K}(a_1\dots a_n,f)=\sqrt{d/n}$ if and only if there is an equal norm tight frame $(u_1,\dots ,u_n)$ with $\parallel u_1\parallel =\cdots =\parallel u_r\parallel =1$ and ${\alpha }_1,\dots ,{\alpha }_n\in K$ with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ where $f\left(a_r\right)=u_r(u_{r+1}{\alpha }_{r+1}{)}^{\ast }$ for all $r$ (where addition in the subscripts is taken modulo $r$).

Proof: In order to not repeat ourselves, our proof shall apply to all three cases: $K=R,K=C,K=H$, but for accessibility purposes, the proof shall be understandable to those are only familiar with real and/or complex matrices.

Suppose that $(u_1,\dots ,u_n)$ is an equal norm tight frame with $\parallel u_1\parallel =\cdots =\parallel u_n\parallel =1$, ${\alpha }_1,\dots ,{\alpha }_n\in K$ are elements with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ and $v_r=u_{r+1}{\alpha }_{r+1}$ for all $r$. Since $\text{RTr}(1_d\cdot (n/d\left)\right)=n$ and  $\text{RTr}(u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })=\parallel u_1{\parallel }^2+\cdots +\parallel u_n{\parallel }^2=n$, we have $u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast }=\left(n/d\right)\cdot 1_d$. Therefore,

$f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast }=u_1{v}_1^{\ast }(u_1{v}_1^{\ast }{)}^{\ast }+\cdots +u_n{v}_n^{\ast }(u_n{v}_n^{\ast }{)}^{\ast }$$=u_1{v}_1^{\ast }{v}_1{u}_1^{\ast }+\cdots +u_n{v}_n^{\ast }{v}_n{u}_n^{\ast }=u_1{u}_1^{\ast }\cdot \parallel v_1{\parallel }^2+\cdots +u_n{u}_n^{\ast }\parallel v_n{\parallel }^2$

$=\parallel v_1{\parallel }^2\cdot (u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })$$=\left(d/n\right)\cdot (u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })$$=\left(d/n\right)\cdot \left(n/d\right)\cdot 1_d=1_d.$

Therefore, $f\in Q_d(K;A)$.

Now, $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })=\rho (v_1^{\ast }{u}_2\dots v_{n-1}^{\ast }{u}_n{v}_n^{\ast }{u}_1)$

$=|v_1^{\ast }{u}_2|\dots |v_n^{\ast }{u}_1|=(\sqrt{d/n}{)}^n\cdot |u_2^{\ast }{u}_2|\dots |u_1^{\ast }{u}_1|=(\sqrt{d/n}{)}^n$. Therefore, we have 

$L_{d,K}(a_1,\dots ,a_r,f)=\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}=\sqrt{d/n}$.

Suppose now that $f\in Q_d(K;A)$. By the arithmetic-geometric mean inequality, we have $\rho \left(f\right(a_1)\dots f(a_n){)}^{2/n}\le \parallel f(a_1)\dots f(a_n){\parallel }_{\infty }^{2/n}\le \parallel f(a_1){\parallel }_{\infty }^{2/n}\dots \parallel f(a_n){\parallel }_{\infty }^{2/n}$

$\le \parallel f\left(a_1\right){\parallel }_2^{2/n}\dots \parallel f\left(a_n\right){\parallel }_2^{2/n}\le \frac{\parallel f\left(a_1\right){\parallel }_2^2+\cdots +\parallel f\left(a_n\right){\parallel }_2^2}{n}$

$=\frac{\text{RTr}(f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast })}{n}=\frac{\text{RTr}\left(1_d\right)}{n}=d/n.$

Suppose now that $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=d/n$. We observe that $\parallel f\left(a_r\right){\parallel }_{\infty }=\parallel f\left(a_r\right){\parallel }_2$ precisely when $\text{Rank}\left(f\right(a_r\left)\right)\le 1$. From the arithmetic-geometric mean inequality, we have $\parallel f\left(a_1\right){\parallel }_2^{1/n}\dots \parallel f\left(a_n\right){\parallel }_2^{1/n}=\frac{\parallel f\left(a_1\right){\parallel }_2+\cdots +\parallel f\left(a_n\right){\parallel }_2}{n}$ precisely when $\parallel f\left(a_1\right){\parallel }_2=\cdots =\parallel f\left(a_n\right){\parallel }_2$. Therefore, each $f\left(a_r\right)$ has rank at most $1$ and  $\parallel f\left(a_r\right){\parallel }_2=\sqrt{d/n}$ for $1\le r\le n$, so we can set $f\left(a_r\right)=u_r{v}_r^{\ast }$ where $\parallel u_r\parallel =1$ and$\parallel v_r\parallel =\sqrt{d/n}$.

Observe that $\rho \left(f\right(a_1)\dots f(a_n\left)\right)=\rho (u_1{v}_1^{\ast }\dots u_n{v}_n^{\ast })$$=|v_n^{\ast }{u}_1{v}_1^{\ast }\dots u_{n-1}{v}_{n-1}^{\ast }{u}_n|=|v_n^{\ast }{u}_1|\dots |v_{n-1}^{\ast }{u}_n|$. Therefore,

$|v_n^{\ast }{u}_1|\dots |v_{n-1}^{\ast }{u}_n|=\parallel f\left(a_1\right){\parallel }_{\infty }\dots \parallel f\left(a_n\right){\parallel }_{\infty }$$=\parallel u_1\parallel \dots \parallel u_n\parallel \cdot \parallel v_1\parallel \dots \parallel v_n\parallel$, so

$|v_r^{\ast }{u}_{r+1}|=\parallel u_{r+1}\parallel \cdot \parallel v_r\parallel$ for all $r$.

Therefore, there are quaternions ${\alpha }_1,\dots ,{\alpha }_n$ with $|{\alpha }_1|=\cdots =|{\alpha }_n|=\sqrt{d/n}$ and where$v_r=u_{r+1}\cdot {\alpha }_r$ for all $r$. 

We observe that $1_d=f\left(a_1\right)f(a_1{)}^{\ast }+\cdots +f(a_n\left)f\right(a_n{)}^{\ast }$$=u_1{v}_1^{\ast }(u_1{v}_1^{\ast }{)}^{\ast }+\cdots +u_n{v}_n^{\ast }(u_n{v}_n^{\ast }{)}^{\ast }=u_1{v}_1^{\ast }{v}_1{u}_1^{\ast }+\cdots +u_n{v}_n^{\ast }{v}_n{u}_n^{\ast }$

$=u_1{u}_1^{\ast }\parallel v_1{\parallel }^2+\cdots +u_n{u}_n^{\ast }\parallel v_n{\parallel }^2=(u_1{u}_1^{\ast }+\cdots +u_n{u}_n^{\ast })\cdot \left(d/n\right)$.

Therefore, $(u_1,\dots ,u_n)$ is an equal norm tight frame. $\square$

Some thoughts:

It seems easier to prove theorems about MPO word pre-embeddings than it is to prove theorems about other machine learning models simply because MPO word pre-embeddings are more mathematical in nature. Of course, neural networks with ReLU activation are mathematical too, so we can prove theorems about them, but MPO word pre-embeddings are more like the objects that mathematicians like to investigate. And it seems easier to mathematically prove theorems that interpret MPO word pre-embeddings than it is to prove theorems that interpret other machine learning models. On the other hand, we are making a tradeoff here. MPO word pre-embeddings behave more mathematically, but word embeddings are simply the first layer in natural language processing.

Why use the spectral radius?

The matrix $f\left(a_1\right)\dots f\left(a_n\right)$ is in general approximately a rank-1 matrix. This means that$\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}\approx \parallel f(a_1)\dots f(a_n){\parallel }^{1/n}\approx |u^{\ast }f(a_1)\dots f(a_n)v|$ whenever $u,v$ are unit vectors. One may be tempted to define the fitness of the $f$ as $\parallel f\left(a_1\right)\dots f\left(a_n\right){\parallel }^{1/n}$ or $|u^{\ast }f\left(a_1\right)\dots f\left(a_n\right)v|$. But mathematical objects are better behaved when taking limits. Instead of considering the string $a_1\dots a_n$ as our corpus, we may consider the similar corpus $(a_1\dots a_n{)}^m$ as $m\to \infty$, and in this case, the fitness of $f$ would be$\parallel \left(f\right(a_1)\dots f(a_n){)}^m{\parallel }^{1/m}$ or $u^{\ast }\left(f\right(a_1)\dots f(a_n){)}^{m}v$ which will both converge to $\rho \left(f\right(a_1)\dots f(a_n){)}^{1/n}$ as $m\to \infty$. The use of the spectral radius simplifies and improves the behavior of the machine learning model for the same reason that integrals such as ${\int }_1^x\frac{dt}{t}$ behave better than sums ${\sum }_{k=1}^n\frac{1}{k}$.