When performing a dimensionality reduction on tensors, the trace is often zero.

post by Joseph Van Name (joseph-van-name) · 2023-08-02T21:06:55.423Z · LW · GW · 1 comments

Contents

  Remark:
  Remark:
  Conclusion: 
  Edited 1/10/2024
None
1 comment

In this post, we shall define my new dimensionality reduction for tensors in $V^{\otimes n}$ where $n\ge 3$, and we shall make an empirical observation about the structure of the dimensionality reduction. There are various simple ways of adapting this dimensionality reduction algorithm to tensors in $V_1\otimes \cdots \otimes V_n$ and even mixed quantum states (mixed states are just positive semidefinite matrices in $V_1\otimes \cdots \otimes V_n$ which trace 1), but that will be a topic for another post.

This dimensionality reduction shall represent tensors in $V^{\otimes n}$ as tuples of matrices $A_1,\dots ,A_r$. Computer experiments indicate that, in many cases, we have $\text{Tr}(A_{i_1}\dots A_{i_m})=0$ whenever $m\ne 0\mathrm{mod}n$.

If $X$ is a matrix, then the spectral radius of $X$ is the value

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

If $X$ is a matrix, then define the conjugate matrix $\overline{X}=(X^{\ast }{)}^T=(X^T{)}^{\ast }$; this is the matrix obtained from $X$ by replacing each entry with its complex conjugate. 

If $(X_1,\dots ,X_r)$ is a tuple of real or complex matrices, then define the $L_2$-spectral radius by setting 

${\rho }_2(X_1,\dots ,X_r)=\rho (X_1\otimes \overline{X_1}+\cdots +X_r\otimes \overline{X_r}{)}^{1/2}$.

Suppose that $K$ is either the field of real numbers or the field of complex numbers. Suppose that $p(x_1,\dots ,x_r)$ is a non-commutative homogeneous of degree $n$ polynomial with coefficients in $K$ (it is easier to define the dimensionality reduction in terms of homogeneous non-commutative polynomials than tensors). 

Then define a fitness function $M_p:M_d(K{)}^r\to [0,\infty )$ by setting

$M_p(A_1,\dots ,A_r)=\frac{\rho \left(p\right(A_1,\dots ,A_r){)}^{1/n}}{{\rho }_2(A_1,\dots ,A_r)}$.

This function $M_p$ is bounded, and it has a maximum value, but to prove that it attains its maximum value, we need to use quantum channels.

We shall call a tuple $(A_1,\dots ,A_r)$ where $M_p(A_1,\dots ,A_r)$ is maximized an

$L_{2,d}$-spectral radius dimensionality reduction (LSRDR) of the non-commutative polynomial $p(x_1,\dots ,x_r)$. The motivation behind the notion of an LSRDR is that it is easier to represent the variables $x_1,\dots ,x_r$ as the matrices $A_1,\dots ,A_r$ than it is to work with the non-commutative polynomial $p(x_1,\dots ,x_r)$. The $d\times d$-matrices $A_1,\dots ,A_r$ have $d^2\cdot r$ parameters while the non-commutative polynomial could have up to $r^n$ parameters where $n$ is the degree of the polynomial $p(x_1,\dots ,x_r)$.

We observe that if $p$ is a quadratic non-commutative homogeneous polynomial, then $max{M}_p(A_1,\dots ,A_r)=\parallel p{\parallel }_2^{1/2}$ where $\parallel \cdot {\parallel }_2$ refers to the Frobenius norm. In other words, we already have a well-developed theory of matrices, and LSRDRs do not improve the theory of matrices, but LSRDRs help us analyze tensors of order 3 in several different ways.

Given square matrices $A_1,\dots ,A_r\in M_d\left(K\right)$, define a completely positive superoperator$\Phi (A_1,\dots ,A_r):M_d\left(K\right)\to M_d\left(K\right)$ by setting$\Phi (A_1,\dots ,A_r)\left(X\right)=A_{1}X{A}_1^{\ast }+\cdots +A_{r}X{A}_r^{\ast }$. The operator $\Phi (A_1,\dots ,A_r)$ is similar to the matrix $A_1\otimes \overline{A_1}+\cdots +A_r\otimes \overline{A_r}$.

Observation: Suppose that $p$ is a non-commutative homogeneous polynomial of degree $n$ with random complex coefficients. Let $(A_1,\dots ,A_r)$ be an $L_{2,d}$-spectral radius dimensionality reduction of $p$. Then we often have $\text{Tr}\left(q\right(A_1,\dots ,A_r\left)\right)=0$ whenever $q$ is a homogeneous non-commutative homogeneous polynomial with degree $m$ where $m\mathrm{mod}n\ne 0$. Furthermore, the set of eigenvalues of $\Phi (A_1,\dots ,A_r)$ is invariant under rotations by $2\pi /n$. Said differently, $\text{Tr}\left(\Phi \right(A_1,\dots ,A_r{)}^m)=0$ whenever $m\mathrm{mod}n\ne 0$.

I currently do not have an adequately developed explanation for why $\text{Tr}\left(q\right(A_1,\dots ,A_r\left)\right)=0$ and $\text{Tr}\left(\Phi \right(A_1,\dots ,A_r{)}^m)=0$ so often (more experimentation is needed), but such an explanation is probably within reach. The observation $\text{Tr}\left(q\right(A_1,\dots ,A_r\left)\right)=0$ does not occur 100 percent of the time since we get $\text{Tr}\left(q\right(A_1,\dots ,A_r\left)\right)=0$ only when the conditions are right. 

If $A_1,\dots ,A_r\in M_d\left(K\right)$, then

$\text{Tr}\left(\Phi \right(A_1,\dots ,A_r\left)\right)=|\text{Tr}\left(A_1\right){|}^2+\cdots +|\text{Tr}\left(A_r\right){|}^2$. Therefore, $\text{Tr}\left(\Phi \right(A_1,\dots ,A_r\left)\right)=0$ precisely when $\text{Tr}\left(A_j\right)=0$ for $1\le j\le r$. Furthermore, 

$\text{Tr}\left(\Phi \right(A_1,\dots ,A_r{)}^m)={\sum }_{i_1,\dots ,i_m}|\text{Tr}(A_{i_1}\dots A_{i_m}){|}^2$, so $\text{Tr}\left(\Phi \right(A_1,\dots ,A_r{)}^m)=0$ precisely when $\text{Tr}(A_{i_1}\dots A_{i_m})=0$ whenever $i_1,\dots ,i_m\in \{1,\dots ,r\}$.

$\text{Tr}(\Phi (A_{1,1},\dots ,A_{1,r_1})\dots \Phi (A_{s,1},\dots ,A_{s,r_s}))$$={\sum }_{i_1\in \{1,\dots ,r_1\},\dots ,i_s\in \{1,\dots ,r_s\}}|\text{Tr}(A_{1,i_1}\dots A_{s,i_s}){|}^2$. Therefore,$\text{Tr}(\Phi (A_{1,1},\dots ,A_{1,r_1})\dots \Phi (A_{s,1},\dots ,A_{s,r_s}))=0$ precisely when $\text{Tr}(A_{1,i_1}\dots A_{s,i_s})=0$ whenever $i_1\in \{1,\dots ,r_1\},\dots ,i_s\in \{1,\dots ,r_s\}$.

Remark:

LSRDRs of tensors are well-behaved in other ways besides having trace zero. For example, if we train two LSRDRs $(A_1,\dots ,A_r),(B_1,\dots ,B_r)$ of a tensor multiple times with the same initialization, then we typically have $M_p(A_1,\dots ,A_r)=M_p(B_1,\dots ,B_r)$ (but this does not happen 100 percent of the time either). After training, the resulting LSRDR therefore does not have any random information left over from the initialization or the training, and any random information present in an LSRDR was originally in the tensor itself.

Remark:

We have some room to modify our fitness function while still retaining the properties of LSRDRs of tensors. For example, suppose that $p$ is a homogeneous non-commutative polynomial of degree $n$, and define $M_{p,s}:M_d(K{)}^r\to [0,\infty )$ by setting

$M_{p,s}(A_1,\dots ,A_r)=\frac{\rho \left(p\right(A_1,\dots ,A_r){)}^{1/n}}{\parallel A_1{A}_1^{\ast }+\cdots +A_r{A}_r^{\ast }{\parallel }_s^{1/2}}$. Then if $p$ is a random homogeneous non-commutative complex polynomial and $1<s\le \infty$ and $\parallel \cdot {\parallel }_s$ denotes the Schatten norm ($\parallel X{\parallel }_s=\left(\text{Tr}\right(\left(X{X}^{\ast }{)}^{s/2}\right){)}^{1/s}$ which is the ${\ell }_s$ norm of the singular values of $X$), and $(A_1,\dots ,A_r)$ maximizes $M_{p,s}(A_1,\dots ,A_r)$, then (if everything works out right), we still would have $\text{Tr}(A_{i_1}\dots A_{i_m})=0$ whenever $m\ne 0\mathrm{mod}n$.

Conclusion: 

Since LSRDRs of tensors do not leave behind any random information that is not already present in the tensors themselves, we should expect for LSRDRs to be much more interpretable than machine learning systems like neural networks that do retain much random information left over from the initialization. Since LSRDRs of tensors give us so many trace zero operators, one should consider LSRDRs of tensors as very well behaved systems, and well behaved systems should be much more interpretable than poorly behaved systems.

I look forward of using LSRDRs of tensors to interpret machine learning models and produce new highly interpretable machine learning models. I do not see LSRDRs of tensors replacing deep learning, but LSRDRs have properties that are hard to reproduce using deep learning, so I look forward to exploring the possibilities with LSRDRs of tensors. I will make more posts about LSRDRs of tensors and other objects produced with similar objective functions. 

Edits: (10/12/2023) I originally claimed that my dimensionality reduction does not work well for tensors in $V_1\otimes \cdots \otimes V_n$, but after reexperimentation, I was able to reduce random tensors in $V_1\otimes \cdots \otimes V_n$ to matrices, and such a dimensionality reduction performed well.

Edited 1/10/2024

1 comments

Comments sorted by top scores.