Interpreting a dimensionality reduction of a collection of matrices as two positive semidefinite block diagonal matrices

post by Joseph Van Name (joseph-van-name) · 2023-08-19T19:52:23.060Z · LW · GW · 2 comments

Contents

  Application: Weighed graph/digraph dominant clustering.
  Maximizing the total weight of edges of an induced subgraph: 
  Why do LSRDRs behave this way?
  Conclusions:
  Edited: 1/10/2024
None
2 comments

Here are some empirical observations that I have made on August 14, 2023 to August 19, 2023 that are characteristics of the interpretability of my own matrix dimensionality reduction algorithm. These phenomena that we observe do not occur on all inputs (they sometimes occur partially); and it would be nice if there were a more complete mathematical theory with proofs that explains these empirical phenomena.

Given a (possibly directed and possibly weighed) graph with $n$ nodes represented as a collection of $n\times n$-matrices $A_1,\dots ,A_r$, we will observe that a dimensionality reduction $(X_1,\dots ,X_r)$ of $(A_1,\dots ,A_r)$ where each $X_i$ is a $d\times d$-matrix (I call this dimensionality reduction an LSRDR) is in many cases the optimal solution to a combinatorial problem for the graph. In this case, we have a complete interpretation of what the dimensionality reduction algorithm is doing.

For this post, let $K$ denote either the field of real numbers or the field of complex numbers (everything also works well when $K$ is the division ring of quaternions).

Notation: $\rho \left(A\right)={lim}_{n\to \infty }\parallel A^n{\parallel }^{1/n}=max\{|\lambda |:\lambda \text{is an eigenvalue of}A\}$ is the spectral radius of the matrix $A$. $A^T$ denotes the transpose of $A$ while $A^{\ast }$ denotes the adjoint of $A$.  We say that a tuples of matrices $(A_1,\dots ,A_r)$ is jointly similar to $(B_1,\dots ,B_r)$ if there is an invertible $C$ with $B_j=C{A}_j{C}^{-1}$ for $1\le j\le r$. $A\otimes B$ denotes the tensor product of $A$ with $B$.

Let $1\le d<n$. Suppose that $A_1,\dots ,A_r$ are $n\times n$-matrices with entries in $K$. Then we say that a collection $(X_1,\dots ,X_r)$ of $d\times d$-matrices with entries in $K$ is an $L_{2,d}$-spectral radius dimensionality reduction (abbreviated LSRDR) of $A_1,\dots ,A_r$ if the following quantity is locally maximized:$\frac{\rho (A_1\otimes (X_1^{\ast }{)}^T+\cdots +A_r\otimes \left(X_r^{\ast }{)}^T\right)}{\rho (X_1\otimes (X_1^{\ast }{)}^T+\cdots +X_r\otimes (X_r^{\ast }{)}^T{)}^{1/2}}$. LSRDRs may be computed using a variation of gradient ascent.

If $(X_1,\dots ,X_r)$ is an LSRDR of $(A_1,\dots ,A_r)$, then one will typically be able to find matrices $R,S,P$ and some $\lambda \in K$ where $X_j=R{A}_{j}S$ for $1\le j\le r$ and where $SR=\lambda P$and $P^2=P$. We shall call $P$ a $L_{2,d}$-SRDR projection operator of $(A_1,\dots ,A_r)$. $(X_1\oplus 0_{n-d},\dots ,X_r\oplus 0_{n-d})$ is jointly similar to $(\lambda P{A}_{1}P,\dots ,\lambda P{A}_{r}P)$ where $0_{n-d}$ is the $(n-d)\times (n-d)$-zero matrix. The $L_{2,d}$-SRDR projection operator $P$ is typically unique in the sense that if we run the gradient ascent to obtain another $L_{2,d}$-SRDR projection operator, then we will obtain the same $L_{2,d}$-SRDR projection operator that we originally had. If $B_1,\dots ,B_r$ are $n\times n$-matrices, then let $\Phi (B_1,\dots ,B_r):M_n\left(K\right)\to M_n\left(K\right)$ denote the completely positive linear operator defined by $\Phi (B_1,\dots ,B_r)\left(X\right)=B_{1}X{B}_1^{\ast }+\cdots +B_{r}X{B}_r^{\ast }$. Let $H$ denote the dominant eigenvector of $\Phi (B_1,\dots ,B_r)$ with $\text{Tr}\left(H\right)=1$, and let $G$ denote the dominant eigenvector of $\Phi (B_1,\dots ,B_r{)}^{\ast }$ with $\text{Tr}\left(G\right)=1$. Then the eigenvectors $H,G$ will typically be positive semidefinite matrices.

Suppose now that $V_1,\dots ,V_q$ are finite dimensional $K$-inner product spaces. Let $V=V_1\oplus \cdots \oplus V_q$. Let $A_1,\dots ,A_r:V\to V$ be linear transformations. Suppose that for $1\le j\le r$, there are $u_j,v_j\in \{1,\dots ,q\}$ where if $x\in V_u,y\in V_v$ and $⟨Ax,y⟩\ne 0$, then$u=u_j,v=v_j$. Suppose that $P:V\to V$ is a $L_{2,d}$-SRDR projection operator for $(A_1,\dots ,A_r)$. Then we will typically be able to find linear operators $P_j:V_j\to V_j$ for $1\le j\le q$ where $P=P_1\oplus \cdots \oplus P_q$. Since $P=P^2$, we observe that $P_j=P_j^2$ for all $j$. As a consequence, there will be positive semidefinite operators $G_j,H_j:V_j\to V_j$ for $1\le j\le q$ where $G=G_1\oplus \cdots \oplus G_q,H=H_1\oplus \cdots \oplus H_q$.

Application: Weighed graph/digraph dominant clustering.

Let $V=\{1,\dots ,n\}$ be a vertex set. Suppose that $1\le d<n$. Let $f:V\times V\to K$ be a function. For example, the function $f$ could denote a weight matrix of a graph or neural network. For each $i,j$, let $A_{i,j}$ be the $n\times n$-matrix where the $(i,j)$-th entry is $f(i,j)$ and all the other entries are zero. Then we will typically be able to find an $L_{2,d}-$SRDR projection operator $P$ of $(A_{i,j}{)}_{i,j}$ along with a set $T\subseteq \{1,\dots ,n\}$ where $P$ is the diagonal matrix where the $i$-th diagonal entry is $1$ for $i\in T$ and $0$ otherwise. The set $T$ represents a dominant cluster of size $d$ in the set $V$. Let $A=(a_{i,j}{)}_{i,j}$ be the $n\times n$-matrix where $a_{i,j}=|f(i,j){|}^2$ for all $i,j$. If $S\subseteq V$, then set

$A{|}_S=(a_{i,j}\cdot {\chi }_S(i)\cdot {\chi }_S(j){)}_{1\le i\le n,1\le j\le n}$ where ${\chi }_S\left(i\right)=1$ whenever $i\in S$ and ${\chi }_S\left(i\right)=0$ otherwise. In other words, if $A{|}_s=(b_{i,j}{)}_{i,j}$, then $b_{i,j}=a_{i,j}$ whenever $i,j\in S$ and $b_{i,j}=0$ otherwise. Then the dominant cluster $T$ will typically be the subset of $V$ of size $d$ where the spectral radius $\rho \left(A{|}_T\right)$ is maximized.

We say that a square matrix $C$ with non-negative real entries is a primitive matrix if there is some $n$ where each entry in $C^n$ is positive. Suppose now that $C$ is the direct sum of a primitive matrix and a zero matrix. Then the spectral radius $\rho \left(C\right)$ is the dominant eigenvalue of $C$, and the root $\rho \left(C\right)$ of the characteristic polynomial of $C$ has multiplicity $1$. Furthermore, there is an vector $v$ with non-negative real entries with $Cv=\rho \left(C\right)v$. We shall call $v$ the Perron-Frobenius eigenvector of $C$.

For $T\subseteq \{1,\dots ,n\}$, let $v_T$ be the dominant eigenvector of $A{|}_T$ where the sum of the entries in $v_T$ is $1$, and let $w_T$ be the dominant eigenvector of $(A{|}_T{)}^{\ast }$ where the sum of the entries in $w_T$ is $1$. If $u$ is a vector, then let $\text{diag}\left(u\right)$ denote the matrix where $u$ is the list of diagonal entries in $u$. Then $H=\text{diag}\left(v_T\right),G=\text{diag}\left(w_T\right)$.

The problem of maximizing $\rho \left(A{|}_T\right)$ is a natural problem that is meaningful for adjacency matrices of (weighted) graphs/digraphs and Markov chains. If $f$ is the adjacency matrix of a graph or a digraph $G$, then the value $\rho \left(A{|}_T\right)$ is a measure of how internally connected the underlying graph is, and if the graph is undirected and simple, then $\rho \left(A{|}_T\right)$ is maximized when $T$ is a clique (recall that a subset of an simple undirected graph is a clique if all of the pairs of distinct nodes are connected to each other). More specifically, the number of paths in the induced subgraph $G\left[T\right]$ with $m$ edges will be about $\rho (A{|}_T{)}^m$. To make this statement precise, if there are $t_m$ paths in the induced subgraph $G\left[T\right]$ of length $m$, then ${lim}_{m\to \infty }{t}_m^{1/m}=\rho \left(A{|}_T\right)$. Therefore, the set $T$ maximizes the number of paths in the induced subgraph $G\left[T\right]$ of length $m$ for large $m$.

The problem of finding a clique of size $d$ in a graph is an NP-complete problem, so we should not expect for there to be an algorithm that always solves this problem efficiently. On the other hand, for many NP-complete problems, there are plenty of heuristic algorithms that give decent solutions in most cases. The use of LSRDRs to find the clique $T$ is another kind of heuristic algorithm that can be used to find the largest clique in a graph and solve more general problems. But the NP-completeness of the problem of finding a clique of size $d$ in a graph also indicates that LSRDRs most likely are unable to find produce cliques in exceptionally difficult graphs.

If $A$ is the transition matrix of an irreducible and aperiodic Markov chain $(X_m{)}_{m\ge 0}$, then the probability that $X_m,\dots ,X_{m+k}\in T$ will be approximately $\rho (A{|}_T{)}^k$. More precisely, ${lim}_{k\to \infty }P(X_0,\dots ,X_k\in T{)}^{1/k}=\rho (A{|}_T)$. In this case, the set $T$ maximizes the probability $P(X_0,\dots ,X_k\in T)$ for large values $k$.

Maximizing the total weight of edges of an induced subgraph: 

If $Y$ is a matrix, then let $\sum Y$ denote the sum of all the entries in $Y$.

Proposition: Suppose that $M_d$ is the $d\times d$ matrix where each entry of $M_d$ is $1/d$. Let $X$ be a real-valued matrix. Then ${}_{\delta \to 0}^{lim}\frac{\rho (M_d+\delta X)-\rho \left(M_d\right)}{\delta }=\sum X/d$.

Let $M_{n,d}$ be the $n\times n$-matrix where each entry of $M_{n,d}$ is $1/d$. Let $B$ be a real $n\times n$-matrix. For simplicity, assume that the value $\sum B{|}_T$ is distinct for each $T\subseteq \{1,\dots ,n\}$. Let $A=M_{n,d}+\delta B$. Then for sufficiently small $\delta$, the spectral radius $\rho \left(A{|}_T\right)$ is maximized (subject to the condition that $|T|=d$) precisely when the sum $\sum B{|}_T$ is maximized. LSRDRs may therefore be used to find the subset $T\subseteq \{1,\dots ,n\}$ with $|T|=d$ that maximizes $\sum B{|}_T$.

Why do LSRDRs behave this way?

Suppose that $(A_1,\dots ,A_r)$ are complex matrices that generate the algebra $M_n\left(C\right)$. Then there is some invertible $B$ and constant $\lambda$ where the operator $\Phi (\lambda B{A}_1{B}^{-1},\dots ,\lambda B{A}_r{B}^{-1})$ is a quantum channel (by a quantum channel, I mean a completely positive trace preserving superoperator), so LSRDRs should be considered to be dimensionality reductions of quantum channels $E:M_n\left(C\right)\to M_n\left(C\right)$. Primitive matrices can be associated with stochastic matrices in the same way; if $A$ is a primitive matrix, then there is a diagonal matrix $D$ and a constant $\lambda$ where $\lambda D^{-1}AD$ is a stochastic matrix. One should consider the LSRDR of $(A_{i,j}{)}_{i,j}$ to be a dimensionality reduction for Markov chains. The most sensible way to take a dimensionality reduction of an $n$-state Markov chain is to select $d$ states so that those $d$ states make a subset that is in some sense optimal. And, for LSRDRs, the best choice of a $d$ element subset $T$ of $\{1,\dots ,n\}$ is the option that maximizes $\rho \left(A{|}_T\right)$.

Conclusions:

The LSRDRs of $(A_{i,j}{)}_{i,j}$ have a notable combination of features of interpretability; these LSRDRs tend to converge to the same local maxima (up-to-joint similarity and a constant factor) regardless of the initialization, and we are able to give an explicit expression for these local maxima. We also have a duality between the problem of computing the LSRDR of $(A_{i,j}{)}_{i,j}$ and the problem of maximizing $\rho \left(A{|}_T\right)$ where $|T|=d$. With this duality, the LSRDR of $(A_{i,j}{)}_{i,j}$ is fully interpretable as a solution to a combinatorial optimization problem.

I hope to make more posts about some of my highly interpretable machine learning algorithms together with some of my tools that we can use to interpret AI.

Edited: 1/10/2024

2 comments

Comments sorted by top scores.