# Wigner type laws for structured random matrices

Tapesh Yadav

###### Abstract.

For a sufficiently nice 2 dimensional shape, we define its approximating
matrix (or patterned matrix) as a random matrix with iid entries arranged
according to a given pattern. For large approximating matrices, we observe
that the eigenvalues roughly follow an underlying distribution. This
phenomenon is similar to the classical observation on Wigner matrices. We
prove that the moments of such matrices converge asymptotically as the size
increases and equals to the integral of a combinatorially-defined function
which counts certain paths on a finite grid. We also consider the case of
several independent patterned matrices. Under a specific set of conditions,
these matrices admit asymptotic freeness with respect to full-filled
independent square random matrices. In our conclusion, we present several open
problems.

##  1\. Introduction

We begin with a classical result by Wigner. Let
$Z_{N}=(1/\sqrt{N})\\{Z_{i,j}\\}_{i,j=1}^{N}$ be a random matrix such that
$\\{Z_{i,j}\\}_{1\leq i\leq j\leq N}$ are iid standard Gaussian random
variables and $Z_{i,j}=Z_{j,i}$ for all $i>j$. Such random matrices are
referred to as the Gaussian orthogonal ensemble (GOE). For a matrix $A$ of
size $N$, let $tr(A)=\frac{1}{N}Tr(A)$ denote normalized trace of the matrix
$A$. The Wigner semicircle law ([1]) states that for a sequence
$\\{Z_{N}\\}_{N=1}^{\infty}$ of GOE random matrices, and for all non negative
integers $k$,

$\lim_{N\to\infty}E(tr(Z_{N}^{k}))=\frac{1}{2\pi}\int_{-2}^{2}t^{k}\sqrt{4-t^{2}}dt$

In other words, the moments of $Z_{N}$ goes to the moments of the semicircular
distribution. This tells us that for large $N$, the eigenvalue distribution of
the random matrix $Z_{N}$ converges to the semicircular law with perhaps one
exceptional large eigenvalue (Figure 1).

Figure 1. a histogram of 5000 by 5000 Gaussian self adjoint (real) random
matrix (GOE) with non zero mean. Each entry has mean 4/N and standard
deviation $\frac{1}{\sqrt{N}}$, N=5000. Note that there is one exceptional
large eigenvalue, while the rest follow a semi-circular distribution.

In recent years, attempts have been made to understand the behaviour of large
random, not necessarily be self adjoint, matrices of different types. In
particular, Dykema and Haagerup in [2] looked at the distribution limits of
the upper triangular random matrices with iid complex standard Gaussian
entries in the strictly upper triangular part and iid random variables
distributed according to a compactly supported measure $\mu$ on the main
diagonal. They showed that their upper triangular matrices converge in
distribution to an element in a tracial Von Neumann algebra. The limiting
element is called a DT-element or a DT-operator. These operators form an
important class of non normal operators for which the Brown measure is
explicitly known. The DT-operators include Voiculescu’s circular operator and
the circular free Poisson operators. Star moments of of these operators show
interesting combinatorial properties (see work by Sniady [3]). Dykema and
Haagerup in [4] proved that every DT operator has a nontrivial, closed,
hyperinvariant subspace. Furthermore, every DT-operator generates the Von
Neumann algebra $L(\mathbb{F}_{2})$ of the free group on two generators.

The moment method is a very useful tool in random matrix theory and free
probability (see [1],[5]). The method refers to a variety of ways through
which we can understand a measure $\mu$ through the integral of the form
(called moments of the measure $\mu$),

$\int x^{n}d\mu(x).$

As a classical example, the moments of the GOE random matrices converges to
the moments of the semi circular law asymptotically, where the moments of an
$N$ by $N$ random matrix $X_{N}$ is given by $E[tr(X_{N}^{n})]$. In general,
given a random matrix $X_{N}$ of size $N$, we define a unital state $\phi_{N}$
on $\mathbb{C}\langle x,x^{*}\rangle$ called the moment map given by
$\phi_{N}(p(x,x^{*}))=E[tr(p(X_{N},X_{N}^{*}))]$ for every non commutative
polynomial $p\in\mathbb{C}\langle x,x^{*}\rangle$. Given a non commutative
probability space $(\mathcal{A},\phi)$ and $X\in\mathcal{A}$, we say that the
sequence of random matrices $X_{N}$ goes to $X$ in distribution asymptotically
if $\phi_{N}(p(x,x^{*}))\to\phi(p(X,X^{*}))$ as $N\to\infty$.

Figure 2. Union of three discs pattern in $[0,1]^{2}$

Our main theorem states that a class of random matrices called the patterned
matrices have a limit in distribution. To state the main theorem, we give some
definitions. Let $S$ be a pattern i.e. $S\subset[0,1]\times[0,1]$ with
boundary of $S$ having Lebesgue measure on $[0,1]^{2}$ equal to zero (for
example, Figure 2). We denote by $B_{N}(i_{1},i_{2},...,i_{m})\in[0,1]^{m}$
the $m$ dimensional cube given by the set
$(i_{1}/N,(i_{1}+1)/N)\times...\times(i_{m}/N,(i_{m}+1)/N)$, where
$i_{k}\in\\{0,...,N-1\\}$ and $k\in\\{1,...,m\\}$. Let $X_{N,S}$ be the
approximating matrix ($N$ by $N$) of the given pattern $S$ (Figure 3). We
define approximating matrix (also called the patterned random matrix) of a
pattern by letting $(X_{N,S})_{ij}=X_{ij}/\sqrt{N}$, if $B_{N}(j-1,N-i)\cap S$
has non empty interior. Otherwise make it zero. Here $\\{X_{ij}\\}$ is a
collection of iid random variables given beforehand, with the assumption that
they have finite moments of all orders with mean 0 and variance 1. Mean zero
is essential in our analysis of random matrices, while variance is restricted
to 1 for simplification.

Let $C$ be a configuration, which is a finite sequence in $x$ and $x^{*}$. The
$k^{th}$ element of this sequence is denoted $C(k)$ and length of the sequence
is called the length of the configuration. For example, $C=xx^{*}x^{*}xxx^{*}$
is of length 6 and $C(3)=x^{*}$. For a matrix $X$, we denote by $X^{C}$ the
product of matrix with itself and its complex conjugate given by the
configuration $C$. For example, if $C=x^{*}xxx^{*}$, then
$X^{C}=X^{*}XXX^{*}$, where $X^{*}$ represent adjoint of matrix $X$. Given a
configuration $C$ and a pair of random variables, $X_{i,j}$ and $X_{j,i}$, we
denote by $X_{i,j}^{C(k)}$ the random variable $X_{j,i}$ if $C(k)=x^{*}$. If
$C(k)=x$, $X_{i,j}^{C(k)}$ denotes the random variable $X_{i,j}$. Notation
$X_{i,j}^{*}$ is also used to denote the random variable $X_{j,i}$.

Figure 3. The figure above gives a solid triangular pattern. The approximating
matrix for this shape is a lower triangular matrix.

We will show that for a pattern $S$, the moments of the approximating matrix
under the configuration $C$ converges as the size goes to infinity. The
limiting moments are given by the scaled integral of a (combinatorial)
function $f_{S,C}^{n+1}:[0,1]^{n+1}\to\mathbb{Z}_{+}$ called the path counting
function, which will be defined later. We state the main theorem below and
will prove the same as Theorem 3.5.

######  Theorem 1.1 (Main Theorem).

Given a configuration C of length $2n$ and a pattern S, asymptotic starred
moment for the approximating matrix of pattern S with configuration C exists
and is equal to $lim_{N\to\infty}E[tr(X_{N,S}^{C})]$
$=\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C}^{n+1}(x_{1},x_{2},...,x_{n+1})d\mathbf{x}$.

The proof relies on basic combinatorics and counting methods. We will see that
only the second moment of the underlying random variables contribute to the
asymptotic moment calculation for the random matrices, which has been a common
theme recently in the area [6]. Another observation is that the moments do not
depend on whether the underlying random variables are real or complex which is
a consequence of something what we refer to as polar pairing of paths (see
Remark 5). We will start with the definitions in Section 2. We will state and
prove the Main Theorem (Theorem 3.5) in Section 3. Section 4 generalizes the
results from section 3 to several independent patterned matrices. In the same
section, we will show that independent patterned matrices are free from
independent fully filled square matrices. We will conclude with Section 5,
giving further results and mentioning some open problems. That section
includes discussion on the relation of the pattern with its moments, the
moments of triangular and fully filled square matrices, affect of base change
on the moments and the relation of distribution limits of patterned matrices
to finite Von Neumann algebras. We leave open the problem of generalizing our
method to patterns with non zero measure boundary.

Von Neumann algebras have been central in the understanding of free
probability (see [4], [7]), and our results suggest that the distribution
limits of patterned matrices live in finite Von Neumann algebra. In the same
spirit as DT operators introduced by Dykema and Haagerup (see [2]), the
limiting non normal operators for the patterned matrices can help in
understanding the spectral properties of operators and their Brown measure.

##  2\. Preliminaries and Definitions

For $n\in\mathbb{N}$, let $[n]$ denote the set $\\{1,...,n\\}$. Consider an
$m+1$ by $N$ rectangular grid,
$[m+1]\times[N]\subset\mathbb{Z}\times\mathbb{Z}$ (Figure 4). Each point in
the set $[N]$ is referred to as a color and every point in the set $[m+1]$ is
referred to as an index. A path on such a grid is a function $i:[m+1]\to[N]$
such that $i(1)=i(m+1)$ (see Figure 4). We sometimes use notation $i_{l}$ to
represent $i(l)$. For a path $i:[m+1]\to[N]$, we define its length to be equal
to $m$.

######  Remark 1.

Note that our definition of a path is different from the literature as we
restrict our paths to have the same end points.

The starred moment under the configuration $C$ of an $N$ by $N$ random matrix
$X_{N,S}$ is given by
$E[tr(X_{N,S}^{C})]=\frac{1}{N^{\frac{m}{2}+1}}E[\sum_{i_{1},..,i_{m}=1}^{N}X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{m},i_{1}}^{C(m)}]$.
To each product term of the form
$X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{m},i_{1}}^{C(m)}$, we
associate a unique path $i:[m+1]\to[N]$ given by $i(k)=i_{k}$ for all
$k\in[m]$ and setting $i(m+1)=i(1)$. We call this path $i$ to be the path
derived from the product term
$X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{m},i_{1}}^{C(m)}$ in the
trace expansion of $X_{N,S}^{C}$. Conversely, given a pattern $S$ and
configuration $C$ and a path $i:[m+1]\to[N]$ such that $i(1)=i(m+1)$, we can
uniquely reconstruct the product term
$X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{m},i_{1}}^{C(m)}$ by
setting $i_{k}=i(k)$ for all $k\in[m]$. This gives a unique correspondence
between paths and the product terms in trace expansion of the matrix
$X_{N,S}^{C}$.

Figure 4. A polar constraint path $i:[8+1]\to[5]$ corresponding to the product
term $X_{21}X^{*}_{13}X_{34}X^{*}_{45}X_{54}X^{*}_{43}X_{31}X^{*}_{12}$ in the
trace expansion of $X_{N,S}^{C}$ where the configuration
$C=xx^{*}xx^{*}xx^{*}xx^{*}$, pattern $S=[0,1]^{2}$ and N=5. We have marked
the wedge.

Here we define some specific type of paths. Let $C$ be a configuration of
length $m$ and $S$ be a pattern. We define the $k^{th}$ edge of a path
$i:[m+1]\to[N]$ to be the set $\\{i(k),i(k+1)\\}$ for $k\in[m]$ . Note that
the $k^{th}$ edge corresponds to $k^{th}$ random variable in the product term
derived from the given path in trace expansion of $X_{N,S}^{C}$. We call an
edge $\\{i(k),i(k+1)\\}$ starred if $C(k)=x^{*}$ and unstarred otherwise. A
path $i:[m+1]\to[N]$, is said to be social if for all $k\in[m]$, there exists
$l\neq k$ such that edge $\\{i(k),i(k+1)\\}$ equals the edge
$\\{i(l),i(l+1)\\}$. We call a social path a pairing if each edge is paired in
the above sense an even number of times. We have strict pairing if each edge
is paired with exactly one other edge. A Polar paired path is a paired path
with the constraint that it has an equal number of starred and unstarred
edges. If $m=2n$, we call a path a (polar) constraint path (see Figure 4)
under a configuration $C$ and pattern $S$ if the path,

  1. (1)

follows the pattern and configuration of the matrix $X_{N,S}$, i.e. it is a
path derived from a product term in the trace expansion of $X_{N,S}^{C}$ with
none of the random variables identically 0 in the product term from which the
path is derived.

  2. (2)

passes through $n+1$ colors (i.e. cardinality of the range of the path is
$n+1$).

  3. (3)

is strictly (polar) paired

Note that social paths are the only paths contributing to the asymptotic
moments. Non social paths always have an unpaired random variable and hence
have mean zero due to independence, so they do not contribute in moment
calculations. We will show in the next Section that the product terms in the
trace expansion indexed by constraint paths are the only ones contributing to
the asymptotic moment calculation. The number of all other social paths goes
to 0 in proportion to constraint paths asymptotically.

The key tool for proving theorems here is the existence of a wedge in a
constraint path. We define a wedge (see Figure 4) as the upward or downward V
shape part of path. By V shape, we mean two consecutive edges
$\\{i(k),i(k+1)\\}$ and $\\{i(k+1),i(k+2)\\}$ having $i(k)=i(k+2)$. A strict
wedge is defined to be a wedge whose edges do not appear anywhere else in the
path other than the wedge itself.

##  3\. Asymptotic moment of Patterned Random matrices

Asymptotic moments of a random matrix under a pattern S and configuration C
refers to the limit $\lim_{N\to\infty}E[tr(X_{N,S}^{C})]$. When we say a path
$i:[m+1]\to[N]$ passes through $k$ colors, we mean that the cardinality of its
range is $k$. A point in the domain of a path is sometimes called an index of
the path. Let $\lceil x\rceil$ be the least integer greater than or equal to
$x$. We begin with certain properties of the paths.

######  Lemma 3.1.

The number of paths $i:[m+1]\to[N]$ normalized by ${1}/{(N^{\frac{m}{2}+1})}$
passing through at most $\lceil m/2\rceil$ colors, asymptotically goes to
zero.

###### Proof.

Passing through at most $\lceil m/2\rceil$ colors is the same as saying that
cardinality of the range of the function $i$ is at most $\lceil m/2\rceil$.
Total number of such functions $i:[m+1]\to[N]$ are of the order $O(N^{\lceil
m/2\rceil})$. Hence normalizing by $1/N^{\frac{m}{2}+1}$ gives us the lemma. ∎

######  Lemma 3.2.

The number of social paths $i:[(2n+1)+1]\to[N]$ normalized by
${1}/{(N^{\frac{(2n+1)}{2}+1})}$ asymptotically goes to 0. This gives that
given an odd length configuration C of length $2n+1$,
$\lim_{N\to\infty}E[tr(X_{N,S}^{C})]=0$.

###### Proof.

we will show that social paths in an odd length configuration of length $2n+1$
pass through at most $n+1$ colors, and apply lemma 3.1 to conclude the result.
We will do this by induction.

The base case is obvious. For a social path of length $2n+1$, we know that an
edge appears at least thrice. We proceed by analysing two cases. For the first
case, assume we do not have any strict wedge in the path. In this case, the
inverse image of every point in the range of the path $i:[2n+2]\to[N]$ has
cardinality at least two. Since one of the edges appears at least thrice, we
have that the function $i$ takes the same value at three distinct points. Thus
the range of the path $i$ has cardinality at most $n+1$; i.e. the path passes
through at most $n+1$ colors.

Suppose that the path has a strict wedge. In this case, we remove the wedge
and join the endpoints together to create a new path of length $2(n-1)+1$.
More precisely, suppose $i:[2n+1]\to[N]$ is a path with wedge at point $k$ in
the domain. We create a new path $i^{\prime}:[2n-1]\to[N]$ defined by
$i^{\prime}(j)=i(j)$ for all $1\leq j\leq(k-1)$, and $i^{\prime}(j)=i(j+2)$
for $k\leq j\leq 2n-1$. This new path satisfies the induction hypothesis, and
hence passes through at most $n$ colors. The wedge adds at most one new color
to the path $i$, and hence the maximum colors it passes through is $n+1$. This
concludes the proof for claim about paths.

To see that $\lim_{N\to\infty}E[tr(X_{N,S}^{C})]=0$ for odd length
configuration of length $2n+1$, we note that only the social paths contribute
to asymptotic moment. We observe that the in the trace expansion, we get a
normalization of ${1}/{N^{\frac{(2n+1)}{2}+1}}$, and hence number of social
paths asymptotically goes to 0. Also, mean of every term corresponding to a
social path is bounded uniformly. Therefore, we get that
$\lim_{N\to\infty}E[tr(X_{N,S}^{C})]=0$.

∎

######  Remark 2.

The method used in the proof of lemma 3.2 is a fundamental method that we
adopt whenever we try to analyse paths. This boils down to inferring property
of the paths by dividing them in two cases: the case where we do have a wedge
and the other, where we don’t. The case without wedge is usually straight
forward. In the case of a wedge, we remove the wedge to get a smaller path of
the same nature and conclude using induction.

######  Remark 3.

Using the same technique as in proof of Lemma 3.2, we can infer that for a
configuration of length $2n$, a social path can pass through at most $n+1$
colors.

From now on, all configurations are of even length.

######  Lemma 3.3 (Existence of a wedge for a social path with n+1 colors).

Let $i:[2n+1]\to[N]$ be a social path and passing through $n+1$ colors. Such a
path has a strict wedge.

###### Proof.

This is true because if there is no strict wedge, each color has to appear at
at least two indices as each edge is at least paired. And there are $2n+1$
indices. We observe that one of the colors appear on at least three indices,
as there are odd number of indices $2n+1$. Thus, the path passes through at
most $n$ colors if there is no strict wedge. ∎

######  Remark 4.

In order for a path of length $2n$ to pass through $n+1$ colors, the path has
to be strict pairing. The reason being, by Lemma 3.3, there has to be a strict
wedge in the path. Remove the strict wedge and join its endpoints to get a
social path of length $2(n-1)$ with $n$ colors. By an induction argument, this
new path is strictly paired and hence the original path is strictly paired.

We will prove an important lemma below which characterizes the paths which
contribute to asymptotic moments.

######  Lemma 3.4.

Amongst all paths in the trace expansion of approximating matrix (of pattern
$S$) of size $N$ with configuration $C$ (of length 2n), only the polar
constraint paths contribute to asymptotic moment as $N\to\infty$.

###### Proof.

From Lemma 3.1, we know that amongst all the paths in trace expansion of
$X_{N,S}^{C}$, only social paths passing through $n+1$ colors contribute to
asymptotic moment (see Remark 3). We will show, using induction on length of
the configuration (which equals $2n$), that social paths passing through $n+1$
colors with non zero mean (i.e.
$E[X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{m},i_{1}}^{C(m)}]\neq
0$ for the path $i(k)=i_{k}$) have to be polar constraint paths.

Base case (for $n=1$) is obvious as there are only two possible paths that can
pass through 2 colors and they have to be polar constraint for non zero mean.
For general $n>1$, we note that there has to be a strict wedge by Lemma 3.3.
We remove this wedge and join the endpoints to get a new path of length $2n$.
The new path is still social but with one less color, and hence the new path
is a social path of length $2(n-1)$ passing through $n$ colors. If the reduced
path is polar constraint, then by the induction hypothesis, this path will
have non zero mean. Hence, adding the wedge back makes the original path of
length $n$ to have non zero mean only if the wedge represents polar paired
random variables. Therefore, the whole path has to be polar paired for non
zero mean in this case.

In the case when the reduced path is not polar paired and therefore has zero
mean, the original path will have zero mean because the removed wedge is a
strict wedge. ∎

######  Remark 5.

Remark 4 gives that in the asymptotic moment calculation, information about
the second moment is enough (as constraint paths have strict pairing). Lemma
3.4 gives that complex and real matrices both have the same moments (due to
‘polar’ pairing).

######  Definition 3.1.

Given a pattern $S\subset[0,1]\times[0,1]$, and a configuration C of length
$2n$, we define a function in $n+1$ variables, called the path counting
function, $f_{S,C}^{n+1}:[0,1]^{n+1}\to\mathbb{N}$ as follows. For distinct
$x_{1},...,x_{n+1}\in[0,1]$, $f_{S,C}^{n+1}(x_{1},...,x_{n+1})$ counts the
number of paths $i:[2n+1]\to[n+1]$, with the following constraints,

  1. (1)

path $i$ is strictly polar paired and passes through $n+1$ colors.

  2. (2)

for $k\in\\{1,...,2n\\}$, the ordered pair $(x_{i(k)},x_{i(k+1)})\in S$ if
$C(k)=x$, and $(x_{i(k+1)},x_{i(k)})\in S$ if $C(k)=x^{*}$.

We set $f_{S,C}^{n+1}(x_{1},...,x_{n+1})=0$ if $x_{i}=x_{j}$ for $i\neq j$.

######  Theorem 3.5 (Main Theorem).

Given a configuration C of length $2n$ and a pattern S, asymptotic starred
moment for the approximating matrix of pattern S with configuration C exists
and is equal to $lim_{N\to\infty}E[tr(X_{N,S}^{C})]$
$=\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C}^{n+1}(x_{1},x_{2},...,x_{n+1})d\mathbf{x}$.

(a) Union of three discs pattern in $[0,1]^{2}$ with discs centered at
(0.5,0.33), (1/4,1/6) and (5/6,4/6) of radius $\frac{1}{\sqrt{8}}$,
$\frac{1}{6}$ and $\frac{1}{6}$

(b) Spectrum for approximating matrix of union of three discs pattern of size
3000

(c) Graph of the moments of (a realization of) approximating matrices under
configuration $xx^{*}$ as size increases. X axis represents $\frac{1}{10}$ the
size of approximating matrix and Y axis gives the corresponding moment of the
approximating matrix of given size. From the graph, moments can be seen
converging to 0.5508

Figure 5. Spectrum and moments of union of three discs pattern

###### Proof.

For each $N\in\mathbb{N}$, we construct simple function $s_{N}$ on
$[0,1]^{n+1}$ by partitioning $[0,1]^{n+1}$ into $n+1$ dimensional disjoint
cubes of edge length $1/N$, $B_{N}(i_{1},...,i_{n+1})$ for all
$i_{k}\in\\{0,...,N-1\\}$. On $B_{N}(i_{1},...,i_{n+1})$, define simple
function’s value to be equal to the number of polar constraint paths
$l:[2n+1]\to[N]$ such that $l(k)\in\\{i_{1}+1,...,i_{n+1}+1\\}$ for all
$k\in[2n+1]$ in the trace expansion of $X_{N,S}^{C}$. By construction, we get
that $s_{N}$ converges almost surely to $f_{S,C}^{n+1}$. The functions,
$s_{N}$ and $f_{S,C}^{n+1}$ are dominated by the total number of distinct
paths from $[2n+1]\to[n+1]$. Hence by dominated convergence Theorem, we get
that $\int_{[0,1]^{n+1}}s_{N}\to\int_{[0,1]^{n+1}}f_{S,C}^{n+1}$ under the
Lebesgue measure. We know,
$\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}s_{N}=E[tr(X_{N,S}^{C})]-\varepsilon_{N}$,
where $\varepsilon_{N}$ represents normalised number of paths with non zero
mean which are not polar constraint, and hence $\varepsilon_{N}\to 0$ as
$N\to\infty$ by Lemma 3.4. We have to normalize $\int_{[0,1]^{n+1}}s_{N}$ by
$\frac{1}{(n+1)!}$ because the function $s_{N}(x_{1},...,x_{n+1})$ takes the
same value on any permutation of the input variables
$\\{x_{1},...,x_{n+1}\\}$, which amounts to over counting of constraint paths
by a multiplicative factor of $(n+1)!$. Hence,
$E[tr(X_{N,S}^{C})]\to\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C}^{n+1}$. ∎

######  Remark 6.

In the proof of the Corollary 3.6, for a term of the form
$X_{i_{1},i_{2}}^{C(1)}...X_{i_{2n},i_{1}}^{C(2n)}-E[X_{i_{1},i_{2}}^{C(1)}...X_{i_{2n},i_{1}}^{C(2n)}]$,
we will refer to $i_{1},...,i_{2n}$ as its colors.

######  Corollary 3.6.

Given a configuration C of length $2n$ and a pattern S, asymptotic starred
moments for the approximating matrix of pattern S with configuration C exists
and are equal to $lim_{N\to\infty}tr(X_{N,S}^{C})$
$=\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C}^{n+1}(x_{1},x_{2},...,x_{n+1})d\mathbf{x}$
almost surely.

###### Proof.

Note that the variance of $tr(X_{N,S}^{C})$ is given by
$\frac{1}{N^{2n+2}}E[(\sum_{1\leq i_{1},...,i_{2n}\leq
N}X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{2n},i_{1}}^{C(2n)}-E[X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{2n},i_{1}}^{C(2n)}])^{2}]$.
Expanding square will give sum over product of the terms of the form
$(X_{i_{1},i_{2}}^{C(1)}...X_{i_{2n},i_{1}}^{C(2n)}-E[X_{i_{1},i_{2}}^{C(1)}...X_{i_{2n},i_{1}}^{C(2n)}])$
and
$(X_{j_{1},j_{2}}^{C(1)}...X_{j_{2n},j_{1}}^{C(2n)}-E[X_{j_{1},j_{2}}^{C(1)}...X_{j_{2n},j_{1}}^{C(2n)}])$
(we refer to product of two terms as a biproduct). We will show that the
number of biproducts with non zero mean is $O(N^{2n})$. Since the mean of each
biproduct is bounded above uniformly, we will get that the variance of
$tr(X_{N,S}^{C})$ decreases on order of $N^{2}$, which is summable. Hence
first Borel Cantelli lemma will give that the convergence of $tr(X_{N,S}^{C})$
is in a.s. sense.

To prove our claim, we note that the mean of biproduct of two terms is zero if
there is no random variable in common between the two terms. So, we count only
the biproducts having at least one random variable in common.

Case 1: biproducts with both the terms social
Each term in biproduct passes through at most $n+1$ colors. Both the terms
together can have at most $2n+2$ colors. Since we have a random variable in
common, we have at least two colors appearing in both the product terms.
Hence, the number of distinct colors appearing is at most $2n$. Total number
of ways we can fill $2n$ colors is bounded above by $N^{2n}$. In each fixed
color configuration, we can have at most $(2n)^{4n}$ distinct biproducts.
Thus, total number of such biproducts is bounded above by $(2n)^{4n}N^{2n}$
which is $O(N^{2n})$.

Case 2: biproducts with at least one non social term
In this case, we have at least one unpaired random variable in one of the
terms in the biproduct. If a term (in the biproduct) of length $2n$ has even
number of unpaired random variables, say $2k$, then the number of distinct
colors in the term is upper bounded by $(n-k)+l$, $l\leq 2k$, where at most
$(n-k)$ distinct colors are added by paired random variables and exactly $2l$
distinct colors (distinct from the colors added by paired ones) are added by
unpaired random variables (Adding color by a random variable
$X_{i_{k},i_{k+1}}$ appearing in the term
$X_{i_{1},i_{2}}^{C(1)}X_{i_{2},i_{3}}^{C(2)}...X_{i_{2n},i_{1}}^{C(2n)}$
refers to the color $i_{k+1}$ ).

In the biproduct of two terms, let the first term has $2k_{1}$ unpaired random
variables adding $l_{1}$ colors and the other term has $2k_{2}$ unpaired
random variables adding $l_{2}$ colors, with $l_{2}\geq l_{1}$. So, the first
term has at most $(n-k_{1})+l_{1}$ colors and the other one has at most
$(n-k_{2})+l_{2}$ colors. All the unpaired random variables in the second term
have to appear in the first term so that the mean of the biproduct do not
vanish. So, each of the color appearing in unpaired random variables of second
term appear in the first term. There are at least $l_{2}$ such colors. So, we
get that total number of distinct colors in unpaired terms is upper bounded by
$([(n-k_{1})+l_{1}]+[(n-k_{2})+l_{2}])-(l_{2})$, which equals,
$2n-(k_{1}+k_{2})+l_{1}-1$ which is less than or equal to $2n$ colors. An
argument similar to case 1 will show that sum of such product terms is of the
order $O(N^{2n})$. A Similar estimate works for odd number of unpaired random
variables as well. Hence, we are done. ∎

##  4\. Generalization to Several independent pattern matrices and freeness

We will use the term fully filled square matrix to refer to the approximating
matrix of appropriate size corresponding to the square pattern $S=[0,1]^{2}$.
We will observe that the moments of several independent pattern matrices
converge asymptotically. We also get that fully filled independent square
matrices are free from independent patterned matrices. We will directly carry
forward some results from one variable case (section 3) without proof. We
start with definitions for several variable case.

Define a generalized configuration
$C^{q}(x_{1},x_{1}^{*},...,x_{q},x_{q}^{*})$ (denoted by $C^{q}$) as a finite
sequence in formal variables $\\{x_{1},x_{1}^{*},...,x_{q},x_{q}^{*}\\}$. An
example would be
$C^{4}=x_{2}x_{2}x_{2}x_{4}^{*}x_{1}x_{3}x_{3}x_{3}x_{1}^{*}x_{1}^{*}$. Let
$C_{1},...,C_{d}$ be configurations (as defined in Section 2) of length
$n_{1},...,n_{d}$. Let $n=n_{1}+...+n_{d}$. We call the tuple
$(C_{1},...,C_{d})$ a multi-configuration of length $n$.

Let $S=(S_{1},...,S_{q})$ be a tuple of patterns. Let
$X=(X_{N,S_{1}},X_{N,S_{2}},...,X_{N,S_{d}})$ be the tuple of approximating
matrices (as defined in Section 2) such that all the underlying random
variables are independent. We define mixed moment of a tuple of random
matrices $X$ under the generalized configuration $C^{q}$ to be equal to
$E[tr(X_{N,S}^{C^{q}})]$. Here
$X_{N,S}^{C^{q}}=C^{q}(X_{N,S_{1}},X_{N,S_{1}}^{*},...,X_{N,S_{q}},X_{N,S_{q}}^{*})$
is the matrix that we get after substituting every formal variable $x_{j}$ by
the corresponding random matrix $X_{N,S_{j}}$ and multiplying them
accordingly. We claim that the mixed moments converge as $N\to\infty$ for any
choice of generalized configuration (Theorem 4.1). The proof of this claim
works exactly the same way as one variable. The sketch of proof is given
below.

Let $C^{q}$ be a generalized configuration. Then the trace expansion for mixed
moments under $C^{q}$ is given by
$E[tr(X_{N,S}^{C^{q}}]=E[\sum_{i_{1},...,i_{d}=1}^{N}X_{i_{1},i_{2}}^{C^{q}(1)}......X_{i_{n},i_{1}}^{C^{q}(n)}]$,
where each term of the form
$X_{i_{1},i_{2}}^{C^{q}(1)}......X_{i_{n},i_{1}}^{C^{q}(n)}$ corresponds to a
unique path say $i:[n+1]\to[N]$, and vise versa. Just like one variable case,
only the terms corresponding to social path contribute to the mixed moment
(i.e. $E[tr(.)]=0$ for non social paths). Using Lemma 3.2, we get that if the
length of multi-configuration is odd, the asymptotic moment equals 0. If the
length of multi-configuration is even say $2n$, then we can infer using lemma
3.1 that only the social paths that pass through exactly $n+1$ colors
contribute to the asymptotic mixed moment. Lemma 3.3 and Remark 4 gives us
that such a path should have a strict wedge and should be strict pairing.

We will omit the details, but after minor modification of Lemma 3.4, we can
show that in the trace expansion for the mixed moments, only polar paired
paths contribute to asymptotic mixed moment. By polar pairing here, we mean
that a random variable which appear in a random matrix $X_{N,S_{k}}$ should be
paired to its complex conjugate appearing in the adjoint matrix
$X_{N,S_{k}}^{*}$. With this information, we claim that the mixed moments do
converge asymptotically, and similar to the one variable case, the moments
converge to an integral of a (combinatorial) function. This function will be
called the generalized path counting function (it counts polar constraint
paths in generalized sense), and is defined almost the same way as the path
counting function introduced in Section 3.

######  Definition 4.1.

Given a tuple of patterns $S=(S_{1},...,S_{q})$ and generalized configuration
$C^{q}$ of length $2n$, we define a function in $n+1$ variables called the
generalized path counting function,
$f_{S,C^{q}}^{n+1}:[0,1]^{n+1}\to\mathbb{N}$ as follows. For distinct
$x_{1},...,x_{n+1}\in[0,1]$, $f_{S,C^{q}}^{n+1}(x_{1},...,x_{n+1})$ counts the
number of paths $i:[2n+1]\to[n+1]$, with the following constraints,

  1. (1)

path $i$ is strictly polar paired and passes through $n+1$ colors.

  2. (2)

for $k\in[2n]$, if $C^{q}(k)=x_{j}$ or $C^{q}(k)=x_{j}^{*}$, the ordered pair
$(x_{i(k)},x_{i(k+1)})\in S_{j}$ if $C^{q}(k)$ is not starred, and
$(x_{i(k+1)},x_{i(k)})\in S_{j}$ otherwise.

We set $f_{S,C}^{n+1}(x_{1},...,x_{n+1})=0$ if $x_{i}=x_{j}$ for $i\neq j$.

With generalized path counting function defined, we can infer that mixed
moments converge asymptotically to the normalized integral of the generalized
path counting function, using exactly the same method that we used to prove
the main theorem, Theorem 3.5. We state this as Theorem 4.1 below without
proof.

######  Theorem 4.1 (Generalization of the Main Theorem).

Given a generalized configuration $C^{q}$ (length $2n$) and tuple of patterns
$S=(S_{1},..,S_{q})$. The asymptotic mixed starred moments for a square random
matrix with generalized configuration $C^{q}$ and pattern tuple $S$ exists and
is equal to $lim_{N\to\infty}E[tr(X_{N,S}^{C^{q}})]$
$=\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C^{q}}^{n+1}(x_{1},x_{2},...,x_{n+1})d\mathbf{x}$.

In the development of free probability, asymptotic freeness has been studied
extensively (see [8], [9]). We have found that the patterned random matrices
also admit asymptotic freeness under certain conditions. To state and prove
our result, we shall start with a definition.

######  Definition 4.2.

Given two paths $i_{1}:[n_{1}+1]\to[N]$ and $i_{2}:[n_{2}+1]\to[N]$ such that
$i_{1}(k)=i_{2}(1)=i_{2}(n_{2}+1)$, we define join of the two paths at index
$k\in[n_{1}]$ to be a new path $i_{1}\wedge_{k}i_{2}:[n_{1}+n_{2}+1]\to[N]$
given by

$i_{1}\wedge_{k}i_{2}(j)=\begin{cases}i_{1}(j),&\text{ if }1\leq j\leq k\\\
i_{2}(j-k+1),&\text{ if }k+1\leq j\leq k+n_{2}\\\ i_{1}(j-n_{2}),&\text{ if
}k+n_{2}+1\leq j\leq n_{1}+n_{2}+1\\\ \end{cases}$

######  Remark 7.

Let $(C_{1},...,C_{d})$ be multi-configuration. We use the notation
$X_{N,S_{1}}^{C_{1}}...\widehat{X_{N,S_{k}}^{C_{k}}}...X_{N,S_{d}}^{C_{d}}$ to
denote the product of random matrices
$X_{N,S_{1}}^{C_{1}},...,X_{N,S_{k-1}}^{C_{k-1}},X_{N,S_{k+1}}^{C_{k+1}},...,X_{N,S_{d}}^{C_{d}}$
which excludes $X_{N,S_{k}}^{C_{k}}$.

######  Remark 8.

Given a fully filled square matrix $X_{N,S}$ and a configuration $C$, we have
that the number of polar constraint paths $i:[2n+1]\to[N]$ such that
$i(k_{1})=s_{1}$ is equal to the number of polar constraint paths with
$i(k_{2})=s_{2}$. This number is equal to the total number of constraint paths
divided by $N$.

######  Theorem 4.2 (Asymptotic Freeness).

Let $S^{1}=(S_{1}^{1},...,S_{q_{1}}^{1})$ and
$S^{2}=(S_{1}^{2},...,S_{q_{2}}^{2})$ be tuples of patterns in
$[0,1]^{2}\in\mathbb{R}^{2}$. Let $(C_{1},...,C_{d})$ be a multi-configuration
of length $2n_{1}+...+2n_{d}=2n$. Let
$m_{S_{i_{1}}^{g_{1}}}^{C_{1}},...,m_{S_{i_{d}}^{g_{d}}}^{C_{d}}$ be the
limits of
$E[tr(X_{N,S_{i_{1}}^{g_{1}}}^{C_{1}})],...,E[tr(X_{N,S_{i_{d}}^{g_{d}}}^{C_{d}})]$
respectively as $N\to\infty$, where $g_{k}\in\\{1,2\\}$ for all $k\in[d]$,
$g_{k}\neq g_{k+1}$, $i_{k}\in[q_{g_{k}}]$. If
$\\{X_{N,S_{i_{g}}^{g}}\\}_{g\in[2],i_{g}\in[q_{g}]}$ are independent, then,
$E[tr((X_{N,S_{i_{1}}^{g_{1}}}^{C_{1}}-m_{S_{i_{1}}^{g_{1}}}^{C_{1}})(X_{N,S_{i_{2}}^{g_{2}}}^{C_{2}}-m_{S_{i_{2}}^{g_{2}}}^{C_{2}})...(X_{N,S_{i_{d}}^{g_{d}}}^{C_{d}}-m_{S_{i_{d}}^{g_{d}}}^{C_{d}}))]\to
0$ as $N\to\infty$.

###### Proof.

We expand
$\lim_{N\to\infty}E[tr((X_{N,S_{1}^{g_{1}}}^{C_{1}}-m_{S_{1}^{g_{1}}}^{C_{1}})...(X_{N,S_{d}^{g_{d}}}^{C_{d}}-m_{S_{d}^{g_{d}}}^{C_{d}}))]$
as

(1)
$\lim_{N\to\infty}E[tr(\sum_{l=0}^{d}\sum_{A\subset[d],|A|=l}(-1)^{d-l}(\Pi_{i\in
A}X_{N,S_{i}^{g_{i}}}^{C_{i}})(\Pi_{j\in
A^{c}}m_{N,S_{j}^{g_{j}}}^{C_{j}}))].$

If we remove the term
$X_{N,S_{1}^{g_{1}}}^{C_{1}}X_{N,S_{2}^{g_{2}}}^{C_{2}}...X_{N,S_{d}^{g_{d}}}^{C_{d}}$
from the above sum, the remaining sum follows inclusion-exclusion principle.
We claim that the asymptotic moment of
$X_{N,S_{1}}^{C_{1}}X_{N,S_{2}}^{C_{2}}...X_{N,S_{d}}^{C_{d}}$ is equal to
negative of the asymptotic moment of remaining sum above.

To prove the above claim, note that only the polar constraint paths contribute
to the asymptotic moment of
$X_{N,S_{1}^{g_{1}}}^{C_{1}}X_{N,S_{2}^{g_{2}}}^{C_{2}}...X_{N,S_{d}^{g_{d}}}^{C_{d}}$.
We know that each polar constraint path has a wedge. This gives us that for
every polar constraint path $i:[2n+1]\to[N]$, we can decompose the path as
join of two polar constraint paths $i_{1}:[2n-2n_{k}+1]\to[N]$ and
$i_{2}:[2n_{k}+1]\to[N]$, i.e., $i=i_{1}\wedge_{2n_{1}+...+2n_{k-1}+1}i_{2}$
(because otherwise if we keep on removing the wedge recursively, we will reach
in finite steps to a polar constraint path which has no wedges, a
contradiction). Note that the path $i_{1}$ comes from trace expansion of the
product
$X_{N,S_{1}^{g_{1}}}^{C_{1}}...\widehat{X_{N,S_{k}^{g_{k}}}^{C_{k}}}...X_{N,S_{d}^{g_{d}}}^{C_{d}}$,
while $i_{2}$ comes from $X_{N,S_{k}^{g_{k}}}^{C_{k}}$. There are two cases,
either $X_{N,S_{k}^{g_{k}}}$ is a fully filled square matrix (i.e. $g_{k}=2$)
or $X_{N,S_{k}^{g_{k}}}$ is some other random matrix (i.e. $g_{k}=1)$.

Case 1: $X_{N,S_{k}^{g_{k}}}$ fully filled square matrix
We will count the total number of polar constraint paths in trace expansion of
$X_{N,S_{1}^{g_{1}}}^{C_{1}}X_{N,S_{2}^{g_{2}}}^{C_{2}}...X_{N,S_{d}^{g_{d}}}^{C_{d}}$
of the form $i=i_{1}\wedge_{(2n_{1}+...+2n_{k-1}+1)}i_{2}$ such that
$i_{1}:[2n-2n_{k}+1]\to[N]$ and $i_{2}:[2n_{k}+1]\to[N]$. For a polar
constraint path $i_{1}$ in trace expansion of
$X_{N,S_{1}^{g_{1}}}^{C_{1}}...\widehat{X_{N,S_{k}^{g_{k}}}^{C_{k}}}...X_{N,S_{d}^{g_{d}}}^{C_{d}}$,
we can join all polar constraint paths $i_{2}$ coming from the trace expansion
of $X_{N,S_{k}^{g_{k}}}^{C_{k}}$ with the restriction that
$i_{2}(1)=i_{2}(2n_{k}+1)=i_{1}(2n_{1}+...+2n_{k-1}+1)$. Using Remark 8, we
know that total number of such paths $i_{2}$ is given by the total number of
polar constraint paths in trace expansion of $X_{N,S_{k}^{g_{k}}}^{C_{k}}$
divided by N. So, the total number of polar constraint paths of the form
$i=i_{1}\wedge_{(2n_{1}+...+2n_{k-1}+1)}i_{2}$ is given by product of polar
constraint paths in
$tr(X_{N,S_{1}^{g_{1}}}^{C_{1}}...\widehat{X_{N,S_{k}^{g_{k}}}^{C_{k}}}...X_{N,S_{d}^{g_{d}}}^{C_{d}})$
multiplied with polar constraint paths in $tr(X_{N,S_{k}^{g_{k}}}^{C_{k}})$
divided by N. As $N\to\infty$, the total number of such paths after
normalizing by $\frac{1}{N^{n+1}}$ equals
$\lim_{N\to\infty}E[tr(X_{N,S_{1}^{g_{1}}}^{C_{1}}...\widehat{X_{N,S_{k}^{g_{k}}}^{C_{k}}}...X_{N,S_{d}^{g_{d}}}^{C_{d}})](m_{S_{i_{k}}^{g_{k}}}^{C_{k}})$.
This is one of the terms in (1).

Case 2: $X_{N,S_{k}^{g_{k}}}$ not fully filled square matrix
In this case, when the matrix at $k^{th}$ position is not a fully filled
square, we have that its neighbouring matrices have to be square. Using this
fact, we can again decompose the polar constraint path as join of two paths
$i=i_{1}\wedge_{(2n_{1}+...+2n_{k-1}+1)}i_{2}$ in the same way as in case 1,
and we get the same asymptotic estimate by using Remark 8.

From cases 1 and 2 combined, summing over all $k\in[d]$ for decomposed polar
constraint paths of the form $i=i_{1}\wedge_{(2n_{1}+...+2n_{k-1}+1)}i_{2}$
and taking the limit gives
$\lim_{N\to\infty}\sum_{k}E[tr(X_{N,S_{1}^{g_{1}}}^{C_{1}}...\widehat{X_{N,S_{k}^{g_{k}}}^{C_{k}}}...X_{N,S_{d}^{g_{d}}}^{C_{d}})(m_{S_{i_{k}}^{g_{k}}}^{C_{k}})]$.
Every polar constraint path has such a decomposition, but the decomposition is
not unique as the same path can be written as join of two paths at different
indices $k$. This leads to over counting. Hence, by using inclusion exclusion
principle, and using similar arguments as above, we get that the exact number
of polar constraint paths (normalized by $N^{n+1}$) ) is given,
asymptotically, by the negative of the sum of all the terms in (1) other than
the term
$\lim_{N\to\infty}E[tr(X_{N,S_{1}^{g_{1}}}^{C_{1}}X_{N,S_{2}^{g_{2}}}^{C_{2}}...X_{N,S_{d}^{g_{d}}}^{C_{d}})]$.
$\lim_{N\to\infty}E[tr(X_{N,S_{1}^{g_{1}}}^{C_{1}}X_{N,S_{2}^{g_{2}}}^{C_{2}}...X_{N,S_{d}^{g_{d}}}^{C_{d}})]$
counts all polar constraint paths asymptotically (normalized by $N^{n+1}$).
Therefore sum (1) equals 0 asymptotically.

∎

##  5\. Further results and Discussion

###  5.1. Relation between configuration and moments

Let $C$ be a configuration of length $m$. Lemma 3.2 shows that if $m$ is odd,
then the asymptotic moments of the approximating matrix under given
configuration are zero. For non zero asymptotic moments, the length of the
configuration has to be even, say $2n$. Remark 5 tells us that the moment is
non zero only if the star and non star entries in the configuration appear an
equal number of times (see Figure 6). We write it as theorem

Figure 6. Graph of the moments of (a realization of) approximating matrices of
union of three discs pattern (see Figure 5) under configuration $xx^{*}x$. X
axis represents $\frac{1}{10}$ the size of approximating matrix and Y axis
gives the corresponding moment of the approximating matrix of given size. From
the graph, moments can be seen to be converging to 0. This configuration has
unequal number of starred and unstarred entries.

######  Theorem 5.1.

Given a configuration and a pattern S with non empty interior, if the number
of star entries in the configuration is different from the unstarred entries,
then the asymptotic moment $\lim_{N\to\infty}E[tr(X_{N,S}^{C})]$ is zero.

If the pattern $S$ has non empty interior, then the asymptotic starred moment
corresponding to the configuration $xx^{*}$ is always non zero. For the proof,
pick an interior point say $z\in S$. There will be a non zero Lebesgue measure
rectangle $[a_{1},a_{2}]\times[b_{1},b_{2}]\subset S$ containing $z$. On this
rectangle, the path counting function $f_{S,xx^{*}}^{1+1}(x_{1},x_{2})$ is
bounded below by 1 for all $x_{1}\in[a_{1},a_{2}]$ and
$x_{2}\in[b_{1},b_{2}]$. Since, $f_{S,xx^{*}}^{1+1}(x_{1},x_{2})$ is non
negative on its domain, and is bounded below by 1 on a non zero measure set,
we have that
$\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,xx^{*}}^{1+1}(x_{1},x_{2})d\mathbf{x}$
is non zero, which is equal to the asymptotic moment by the main theorem.

###  5.2. Combinatorics: Triangular and fully filled square matrices

The function $f_{S,C}^{n+1}$ is constant on its domain for triangular and
fully filled square matrices. This means that the asymptotic moments converge
to $\frac{1}{(n+1)!}f_{S,C}^{n+1}$. The function $f_{S,C}^{n+1}$ counts the
number of constraint paths on $2n+1$ by $n+1$ grid. So, if we can calculate
the moments of the random matrix using alternate methods, like using methods
from free probability (see [2]), we can get hold on the combinatorial quantity
given by the function $f_{S,C}^{n+1}$.

For triangular matrices, this combinatorial quantity has been explicitly
computed using tools from free probability ([2],[3]) for certain
configurations. For example, in [2], they count moments for configurations of
the form $xx^{*}xx^{*}xx^{*}..xx^{*}$, where $xx^{*}$ repeats $n$ times. This
number turns out to be $n^{n}/(n+1)!$. In [3], we see that for configuration
of the form $(x...xx^{*}...x^{*})...(x...xx^{*}...x^{*})$, where the block
$x...xx^{*}...x^{*}$ appears $n$ times, and the block consists of $x$
appearing $k$ times consecutively followed by same number of appearances of
$x^{*}$, the value of the path counting function turns out to be
$n^{nk}/(nk+1)!$.

For fully filled square matrices, it is well known that under the
configuration $(xx^{*})^{n}$, the moments equals $n^{th}$ moment of
Marchenko–Pastur law. We explicitly know the limiting empirical spectral
distribution (ESD) in case of iid entries for such matrix (see[6]).

###  5.3. Pattern and base change

We call a pattern $S_{1}$ to be similar to pattern $S_{2}$ if the
approximating matrices for $S_{1}$ are similar to the approximating matrices
for pattern $S_{2}$ infinitely often as the size of matrices increases. Since
trace is basis independent, we get the same moments for similar matrices.
Hence, the moments corresponding to similar patterns are the same.

A natural question is to characterize similar patterns (for example, existence
of kernel functions relating two patterns) without going to the level of
approximating matrices. Another question would be to understand if similar
shapes produce a unique collection of starred moments. That is, if two
patterns are not similar, do we always get non identical starred moments.

###  5.4. Approximating matrices for patterns with non zero measure boundary

Our construction for approximating matrix using interior points works well for
patterns with zero measure boundary. If the boundary has non zero measure, our
main theorem (as stated in this paper) will not hold true. This is because the
approximating matrix will not be a good representation of the given pattern if
we follow our method. It remains an open problem to find a way to create more
sensible approximating matrix out of the given pattern, which may have non
zero measure boundary. One possibility is to use the theory of fractals in
this context.

###  5.5. Moment reconstruction

The number of paired paths from $[2n+1]$ to $[n+1]$ is bounded above by
$K(n+1)^{n+1}$, where $K$ is a universal constant. This tells us that the path
counting function is bounded by $k(n+1)^{n+1}$ for a configuration of length
$2n$. Using the Stirling approximation, and the fact that the moments are
given by $\frac{1}{(n+1)!}\int_{[0,1]^{n+1}}f_{S,C}^{n+1}$, we conclude that
the moments of random matrix under configuration of length $2n$ increases
exponentially i.e. moments are bounded by $Ce^{n}$, for some constant $C$.
This gives us that the moments follow the Carleman’s condition, and hence we
have a unique measure with those moments. Also, the growth rate gives us that
the measure has a bounded support. This tells us that we can find an operator
in a type II1 factor with the same starred moments as of the limiting moments
of the random matrix. These limiting operators are referred to as distribution
limits of the given sequence of random matrix. In Dykema’s work (see [2]),
they showed the existence of such operators concretely for triangular matrices
and called them the DT operators.

## References

  * [1] James A Mingo and Roland Speicher.  Free probability and random matrices, volume 35.  Springer, 2017.
  * [2] Ken Dykema and Uffe Haagerup.  DT-operators and decomposability of Voiculescu’s circular operator.  American Journal of Mathematics, 126(1):121–189, 2004.
  * [3] Piotr Śniady.  Multinomial identities arising from free probability theory.  Journal of Combinatorial Theory, Series A, 101(1):1–19, 2003.
  * [4] Ken Dykema and Uffe Haagerup.  Invariant subspaces of the quasinilpotent dt-operator.  Journal of Functional Analysis, 209(2):332–366, 2004.
  * [5] Arup Bose and Arnab Sen.  Another look at the moment method for large dimensional random matrices.  Electronic Journal of Probability, 13:588–628, 2008.
  * [6] Terence Tao and Van Vu.  Random matrices: Universality of esds and the circular law.  The Annals of Probability, 38(5):2023–2065, 2010.
  * [7] Alice Guionnet, Vaughan FR Jones, and Dimitri Shlyakhtenko.  Random matrices, free probability, planar algebras and subfactors.  Quanta of maths, 11:201–239, 2010.
  * [8] Dan Voiculescu.  Free probability theory: random matrices and von neumann algebras.  In Proceedings of the International Congress of Mathematicians, pages 227–242. Springer, 1995.
  * [9] James A Mingo and Mihai Popa.  Freeness and the transposes of unitarily invariant random matrices.  Journal of Functional Analysis, 271(4):883–921, 2016.


11institutetext:  Friedrich–Alexander University Erlangen–Nürnberg, DE
11email<EMAIL_ADDRESS>22institutetext: Imperial College
London, SW7 2AZ, London, UK

# Resource-efficient Medical Image Analysis with Self-adapting Forward-Forward
Networks

Johanna P. Müller 11 0000-0001-8636-7986 Bernhard Kainz 1122
0000-0002-7813-5023

###### Abstract

We introduce a fast Self-adapting Forward-Forward Network (_SaFF-Net_) for
medical imaging analysis, mitigating power consumption and resource
limitations, which currently primarily stem from the prevalent reliance on
back-propagation for model training and fine-tuning. Building upon the
recently proposed Forward-Forward Algorithm (FFA), we introduce the
Convolutional Forward-Forward Algorithm (CFFA), a parameter-efficient
reformulation that is suitable for advanced image analysis and overcomes the
speed and generalisation constraints of the original FFA. To address hyper-
parameter sensitivity of FFAs we are also introducing a self-adapting
framework _SaFF-Net_ fine-tuning parameters during warmup and training in
parallel. Our approach enables more effective model training and eliminates
the previously essential requirement for an arbitrarily chosen Goodness
function in FFA. We evaluate our approach on several benchmarking datasets in
comparison with standard Back-Propagation (BP) neural networks showing that
FFA-based networks with notably fewer parameters and function evaluations can
compete with standard models, especially, in one-shot scenarios and large
batch sizes.

###### Keywords:

Forward-Forward Algorithm, Goodness Function, Efficiency

##  1 Introduction

Efficient neural networks are becoming tremendously important for effective
impact on real clinical workflows. This is particularly important as the need
to fine-tune models on compute and power-constrained clinical devices becomes
increasingly prevalent. Additionally, the concentration of resources in only a
few specialised institutions highlights the importance of creating models that
can operate efficiently in various low-resource settings, ensuring widespread
access to advanced healthcare technologies. Moreover, the lack of
computational infrastructure in areas that could benefit the most from
population-fine-tuned deep learning models due to the scarcity of experts
underscores the urgency of developing compute and energy-efficient neural
networks that can transcend such limitations and make a meaningful impact on
global healthcare disparities. This paper addresses the pressing need to
develop neural architectures that not only perform well but also operate with
optimal energy consumption during training and application. To this end, we
introduce a fast self-adapting Forward-Forward Network without using Back-
Propagation (BP) for medical imaging analysis to mitigate power consumption
and enable training if computational resources are limited, contributing to
the larger discourse on responsible AI development.

Based on preliminary work on the Forward-Forward Algorithm (FFA) [13], we know
that FFAs can be slightly slower than BP and seem not to generalize as well on
several simplified example datasets. In this paper, we address the remaining
issues of FFAs and provide comprehensive insights into the advancement of
FFAs. To ensure reproducibility and adoption, we also suggest and share an
automatically self-configuring FFA framework for medical imaging analysis
considering the limitations of energy and resources.

Contributions.  (1) We present the Convolutional Forward-Forward Algorithm as
an extension to the Forward-Forward Algorithm by [13]. (2) We show that the
(Convolutional) Forward-Forward Algorithm can be utilised fully without
backpropagation for classification and pretraining of Multi-Layer-Perceptrons
and other Convolutional Neural Networks even without the use of domain-limited
goodness functions. (3) We propose the backpropagation-free self-adaptive
Forward-Forward Framework (SaFF-Net) and show its advantages, evaluating the
numbers of function evaluations and parameters, and its general performance.

Related Work. The Forward-Forward Algorithm (FFA) [13] diverges from the
traditional Backpropagation (BP) algorithm similar to Evolutionary Algorithms
[28, 26], Predictive Coding [27], Hebbian learning [16], Feedback Alignment
[18] and Reservoir Computing [3]. These alternatives to BP exhibit challenges
such as elevated computational demands, sensitivity to noise, a lack of
explainability, and difficulties in training and global optimisation.

[13, 19, 9, 34, 15, 25] explore the FFA, offering insights into its behaviour,
strengths, and limitations. These works also propose incremental extensions
for enhancing FFA performance. From a biological perspective, FFA demonstrates
potential superiority over BP algorithms [29, 9]. [13] presents FFA as a
biological model, notably for modelling sleep deprivation [13, 17].

Eliminating the need for computationally intensive BP, the transition to
analogue hardware, such as microcontroller architectures [7], and the
application of FFA in Spiking Neural Networks [22, 21], appear promising. The
integration of FFA within Recurrent Neural Networks (RNNs) has been explored
[22] and the application of FFA in Graph Neural Networks (GNNs) has gained
attention for handling complex relationships in graph-structured data
efficiently [23]. For Self-Supervised Learning (SSL), [5] discusses data
augmentation techniques in training FFAs. They propose self-supervised FFAs as
a superior approach compared to the unsupervised approach presented by [13].

[1] explores FFA pretraining, presenting a framework with two stages of local
and global contrastive representation learning, and subsequent BP-based image
classification with binary-cross-entropy. They replace the MLP with a ResNet18
architecture. Other works also investigate the synergy between FFA and BP
techniques, aiming to leverage the strengths of both approaches for enhanced
learning and overall energy efficiency [10, 5].

FFA Limitations. The FFAs goodness function is important for layer-wise
training in a contrastive learning setting. The positive pass adjusts weights
on real data to increase goodness, while the negative pass handles counter-
examples, adjusting weights to decrease goodness. However, this idea poses
three major problems. (1) It requires an additional dataset-specific
hyperparameter, $\theta$, for thresholding. This hyperparameter is dataset-
specific and needs independent optimisation. (2) For prediction, assessing
goodness for each possible label limits applications to classification. A
mitigation is presented in [22], using FFAs in Recurrent Neural Networks for
generative and reconstructive tasks. There, the goodness function only
regulates neuron activity, resulting in the last layer’s output containing no
spatial information; only the sum of goodness over all layers determines the
result. (3) Based on preliminary experiments and results from [19], adding
more than two layers does not positively contribute to FFA performance. The
consequent dependence on Multi-Layer Perceptron (MLP) architectures and
heuristic designs for the goodness function limits FFA significantly for
practical applications. To the best of our knowledge, only [1] pretrains a
CNN, specifically a ResNet18 [12] backbone, for classification. In parallel to
our work another convolutional approach was proposed by [24] including a
complex channel-wise competitive learning strategy. However, the primary
constraint of these methods lies in their extensive need for hyperparameter
tuning, encompassing a wide array of parameters such as threshold settings,
the iteration count per layer, the total number of epochs, the architecture
depth (number of layers), learning rate, batch size, the choice of loss and
activation functions. Specifically for convolutional feature extraction, this
extends to configuring the number of input and output channels, stride
lengths, padding types, and kernel dimensions.

##  2 Method

Figure 1: The Forward-Forward Multi-Layer Perceptron (left), the Forward-
Forward Convolutional Neural Network (right). The networks are optimised
layer-wise. The positive and negative samples are fed into the first layer and
via layer normalisation, we obtain orientation and length of the activation
vector. The orientation is forwarded to the next layer as its input. The
length is used for the computation of the goodness. Each layer is optimised so
that positive samples have high goodness (> threshold) and negative samples
have low goodness (< threshold). For inference, the sum of the goodness of all
layers, excluding the first layer, needs to be determined for every possible
label.

The Forward-Forward Algorithm [13] (Fig. 1, left) is a multi-layer learning
approach influenced by Boltzmann machines [14] and Noise Contrastive
Estimation [11]. Unlike traditional BP, it employs two forward passes (instead
of forward and backward) operating similarly but on different data with
opposing objectives. The positive pass operates on real data $x^{+}$ and
adjusts the weights to increase the goodness. The negative pass operates on
counter-examples $x^{-}$ and adjusts the weights to decrease the goodness. The
goodness function

$g(x)=\sum_{j}y_{j}(x^{+/-})^{2}-\theta$ (1)

can be defined as the (negative) sum of the squared neural activities of
$y(x)$, where $y_{j}$ is the output of hidden unit $j$ and $x^{+/-}$ is the
input. The probability $p(x)$ that an input vector $x$ is real (true) is given
by $p(x)=\sigma(g(x))$, where $\sigma$ is the logistic function. However, if
the activities of the first hidden layer are used as input for the second
hidden layer, distinguishing between positive and negative data becomes
straightforward. This can be achieved by simply measuring the length of the
activity vector from the first hidden layer, without the need to learn any new
features. To mitigate this issue, the FFA employs a normalisation on the
length of the hidden vector before feeding it as input to the subsequent
layer. It follows, that only the length of $y^{+/-}$ is used for goodness and
the orientation derived from the (layer) normalisation is forwarded to the
next hidden layer. [13]

Convolutional Forward-Forward Algorithm. We propose the Convolutional Forward-
Forward Algorithm (CFFA) and extend the application of the FFA to
Convolutional Neural Networks (CNNs), see Fig. 1, right. Given the two-
dimensional convolution in an arbitrary convolutional layer

$y_{i,j}=\alpha\left(\sum_{m=1}^{M}\sum_{n=1}^{N}x_{m,n}\cdot
w_{i,j,m,n}+b_{i,j}\right),$ (2)

where $y_{i,j}$ is the output feature at position $(i,j)$, $x_{m,n}$ is the
input feature at position $(m,n)$, $w_{i,j,m,n}$ is the weight at position
$(i-m+\lfloor\frac{K}{2}\rfloor,j-n+\lfloor\frac{K}{2}\rfloor)$ in the kernel
with size $K$, $b_{i,j}$ is the bias term at position $(i,j)$, and
$\alpha(\cdot)$ is the activation function. The same applies to three-
dimensional convolutions. Consequently, we can also use the goodness and the
probability function for a given hidden layer with input
$x\in\mathbb{R}^{MxN}$. Therefore, we can take the length of $y^{+/-}_{i,j}$
for goodness and the orientation derived from the (layer) normalisation can be
forwarded to the next hidden layer, maintaining spatial dependencies. At this
point, we want to emphasise that convolutional layers in CFFAs do not impede
potential on-chip training for tiny devices, see exemplarily [30, 31].

Objective. Given the goodness function $g(x)$ (Eq. 1), we can formulate the
optimisation problem with an arbitrary contrastive loss function
$F(x^{+},x^{-})$

$\min_{x}F(x)=\min_{x}\frac{1}{B}\sum_{i=1}^{B}\log(G(x_{i}))$ (3)

where $B$ is the dimension of the input batch and goodness matrix
$G_{i}=(-g(x_{i}^{+})\mathbin{\|}g(x_{i}^{-}))$ with concatenation operator
$(\mathbin{\|})$. The objective function can be easily replaced by any
contrastive loss function for contrastive pretraining.

Self-adapting SaFF-Net. We propose an FFA-based framework (see Appendix for an
overview). Related to energy-based neural networks as the FFA itself, it is
able to minimise the energy for training and necessary for inference
additionally leading to a resource-efficient model optimisation framework.
Initially, we fine-tuned hyperparameters such as learning rate, batch size,
number of layers, and sizes of filters and weights for task-specific
optimization, settling on a configuration that delivered optimal average
performance across all datasets. In a warm-up stage, these configuration sets
can be pre-evaluated and selected based on preceding statistical tests. We use
Early Stopping, where the training process is halted based on the model’s
performance on a validation set. This not only prevents overfitting but also
expedites convergence by recognizing when further iterations yield diminishing
returns. We apply Early Stopping not only on layer iterations and epochs but
also on the number of layers, hence, restricting the depth of the network. We
also include network pruning [4] and incorporate Peer-Normalisation and Batch-
Normalisation Loss as an additional loss term during training. Additionally,
we introduce a trainable threshold parameter $\theta$ for the goodness
function for reducing the number of hyperparameters. For training, each
dataset is Z-score normalised within the framework by default but other
normalisations or augmentation functions can be easily added through
customised experiment files. Finally, SaFF dynamically selects an optimised
architecture during the warm-up phase based on prior statistical analysis of
dataset characteristics and during training based on model performance.

Implementation. We use Python and PyTorch. All models were trained on NVIDIA
A100 $80$GB. The average training time for a model with maximum batch size
depends on the number of layer iterations and/or epochs and is $<30$ min for
one-shot learning and $<2$ h for others.

##  3 Evaluation

Classification. We can use FFA and CFFA for the classification of closed-set
problems. We produce positive and negative samples through label encodings in
the image data. For a $n$-class problem, we take, _e.g._ , the first $n$
pixels for the label encoding, setting position $i=0...n$ with the maximum
intensity value according to the true label for positive samples. For negative
samples, we set, _e.g._ , a random label encoding position with the maximum
intensity value in an unsupervised setting. We investigate different self- and
semi-supervised tasks to show the generalizability of our method. We evaluate
the performance on an independent test set with Accuracy, Area Under the
Receiver Operating characteristic (AUC) and mean Average Precision (mAP).

Pretraining. We can contrastively pretrain in unsupervised, self-supervised
and supervised settings. In the pretraining phase, the focus lies on training
solely the encoder, subsequently freezing it and learning the decoder with the
input of the encoder. This approach ensures the preservation of the encoder’s
weights, shielding them from any alteration induced by BP during the
subsequent downstream task. We test pretraining with FFA, CFFA and ResCFFA on
three downstream tasks, Classification, Reconstruction, and Segmentation. For
segmentation, we evaluate the performance on an independent test set with
Accuracy and Intersection over Union (IoU). Mean Structural Similarity Index
(MSSI) and Peak Signal-to-Noise Ratio (PSNR) are applied to evaluate
reconstruction.

Datasets. For baseline comparisons we evaluate on
http://yann.lecun.com/exdb/mnist/MNIST [8] and https://medmnist.com/MedMNIST
[33]. To test real-world scalability, we use
https://vindr.ai/datasets/cxrVinDr-CXR [20], part of the
https://vindr.ai/datasetsVinDr. VinDr consists of 100,000 thoracic chest X-ray
images and annotations provided by 17 radiologists. We focus on the binary
classification, healthy and unhealthy, and the segmentation of Cardiomegaly.

##  4 Results

Table 1: Ablation study for _SaFF-Net_ self-configuration on MNIST and
MedMNIST (Supervised). The FFA Baseline consists of 4 layers with 1000 neurons
each. _One-shot_ means the network is trained on one single-batch. Networks
are trained max. 10 epochs with 1,000 layer iterations. The optimised number
of parameters for _SaFF-Net_ is given in the last row. number of function
evaluations (NFE) - Forward and Backward passes $\times 1e^{3}$, ES - Early
Stopping

| MNIST | MedMNIST Pneumonia
---|---|---
(lr)2-7 (lr)8-13 | FFA (_One-shot_) | FFA | FFA (_One-shot_) | FFA
| ACC$\uparrow$ | AUC$\uparrow$ | NFE$\downarrow$ | ACC$\uparrow$ | AUC$\uparrow$ | NFE$\downarrow$ | ACC$\uparrow$ | AUC$\uparrow$ | NFE$\downarrow$ | ACC$\uparrow$ | AUC$\uparrow$ | NFE$\downarrow$
(lr)2-4 (lr)5-7 (lr)8-10 (lr)11-13 Baseline | 0.24 | 0.83 | 8.0 | 0.95 | 0.99 | 80.0 | 0.84 | 0.84 | 8.0 | 0.87 | 0.90 | 80.0
ES Iterations | 0.93 | 0.99 | 7.3 | 0.11 | 0.55 | 9.3 | 0.87 | 0.91 | 1.5 | 0.83 | 0.89 | 2.0
ES Layers | 0.24 | 0.83 | 8.0 | 0.96 | 1.00 | 60.0 | 0.84 | 0.85 | 8.0 | 0.87 | 0.90 | 60.0
ES Epoch | - | - | - | 0.95 | 1.00 | 80.0 | - | - | - | 0.84 | 0.89 | 56.0
Pruning (0.4) | 0.22 | 0.82 | 8.0 | 0.85 | 0.99 | 80.0 | 0.85 | 0.84 | 8.0 | 0.82 | 0.83 | 80.0
w/ Retraining | 0.22 | 0.82 | 8.8 | 0.85 | 0.99 | 80.8 | 0.85 | 0.84 | 8.8 | 0.81 | 0.83 | 80.8
Warm-Up | 0.01 | 0.42 | 32.0 | 0.64 | 0.93 | 104.0 | 0.80 | 0.86 | 32.0 | 0.83 | 0.91 | 80.0
Train. Thresh. | 0.84 | 0.97 | 8.0 | 0.97 | 1.00 | 80.0 | 0.83 | 0.72 | 8.0 | 0.89 | 0.94 | 80.0
Peer-Norm | 0.23 | 0.83 | 8.0 | 0.95 | 1.00 | 80.0 | 0.83 | 0.86 | 8.0 | 0.85 | 0.89 | 80.0
_SaFF-Net_ | 0.97 | 1.00 | 29.9 | 0.97 | 1.00 | 29.9 | 0.87 | 0.91 | 15.8 | 0.87 | 0.91 | 15.7
(lr)2-4 (lr)5-7 (lr)8-10 (lr)11-13 #Par. | 1,144,004 | 893,503 | 3,788,004 | 2,787,003

Figure 2: Classification on MNIST. ACC - Accuracy, AUC - Area Under the
Receiver Operating characteristic, mAP - Mean Average Precision vs. Number of
Parameters Comparison for MLP and FFA (top) and CNN and CFFA (bottom) with
maximum batch size. Ours in orange. Table 2: Classification performance for
Semi-supervised (SemiSL), self-supervised (SSL), and average from established
methods for fully supervised (SL). SaFF-Net with FFA is used for 1D (flatten)
input data and CFFA is used for 2D/3D input data.

|  |  |  |  | MedMNIST | VinDr-CXR |
---|---|---|---|---|---|---|---
(lr)6-13 (lr)14-15 |  |  | MNIST | Pneumonia | OCT | OrganA | Synapse3D | Binary |
|  | #par. | ACC | AUC | ACC | AUC | ACC | AUC | ACC | AUC | ACC | AUC | ACC | AUC |
SL |  [6, 35, 32] $\diameter$ |  | 89.75 | 95.9 | 84.27 | 91.27 | 68.93 | 77.63 | 78.67 | 91.27 | 61.07 | 58.53 | - | - |
SemiSL | C-Mixer[35] | 6m | - | - | 56.6 | 79.9 | 72.8 | 69.9 | - | - | - | - | - | - |
FFA (OS)(_Ours_) | 2.8m | 91.0 | 99.0 | 51.0 | 52.6 | 19.2 | 44.2 | 33.3 | 72.1 | 73.0 | 74.8 | 75.7 | 81.5 |
CFFA (OS)(_Ours_) | 190k | 92.5 | 99.2 | 86.2 | 93.1 | 70.1 | 89.5 | 34.9 | 80.2 | 63.2 | 67.2 | 78.0 | 80.1 |
SSL | FFA (_Ours_) | 2.8m | 92.9 | 98.8 | 62.5 | 58.7 | 24.5 | 51.7 | 23.0 | 49.0 | 27.0 | 27.6 | 78.6 | 81.3 |
CFFA (_Ours_) | 190k | 92.1 | 91.2 | 85.7 | 84.9 | 44.5 | 63.7 | 58.2 | 79.2 | 33.7 | 64.0 | 99.2 | 99.6 |

Classification. Prior experiments show that the optimised threshold value of
$\theta$ is correlated with the test performance. We tested this correlation
hypothesis and rejected the null hypotheses for all three metrics (p-values
for Accuracy: 0.061, AUC: 0.051, mAP: 0.065). This significance only exists
for threshold $\theta$ of the first layer if the first two layers were
trained. This enables us to use $\theta$ for selecting the number of neurons
per layer during warm-up. For evaluating the influence of all possible
components in our framework, we studied ablations for FFA LABEL:tab:abl-ffa
and CFFA (Suppl. Material, Tab. 4), for MNIST and an exemplary MedMNIST
dataset. Our largest FFA model configuration consists of $3,788,004$
parameters which is only necessary for one-shot learning. Based on the
ablation study the components with the highest impact are Early Stopping for
layer iterations and the trainable threshold parameter in FFA models,
especially, for epoch-wise learning. For one-shot learning, the trainable
parameter had less influence on the performance. For CFFA models, Early
Stopping for layer iterations was less conducive, on the contrary, the
trainable threshold parameter increased the performance.

All CFFA models have the same size of $194,432$ parameters similar to the
ResCFFA model with $148,933$ parameters. The ResCFFA is built of 5 2D-CFFA
(64-channel) layers with one residual connection between the first hidden
layer and the fourth. We test against three benchmark models an MLP with
$2,797,010$ (increases for multi-channel input) parameters (3 hidden layers à
1000 neurons plus 1 fully connected output layer), a CNN with $1,554,954$
parameters (4 hidden layers with [64,128,256,512] features plus 1 fully
connected output layer; it performed worse with same configuration as CFFA)
and ResNet18 with $11,183,694$ parameters. We present an extensive table
comparing networks with and without BP in Suppl. Material, Tab. 5. The
comparison between FFA and MLP models highlights that we can achieve in the
mean for the MedMNIST dataset an improvement by 22 % in accuracy with _SaFF-
Net_. For the 3D MedMNIST data, the MLP performed slightly better (7%). In
comparing CFFA models with CNNs, our results show an overall performance
increase when using CFFA for MedMNIST (10%), for 3D the CNN performed 37 %
better. We compare the results of our models with comparable SOTA methods and
show the performance for semi-supervised learning ($10\%$ labelled) and self-
supervised pretraining for SaFF-Net in Tab. LABEL:tab:sota.

Pretraining. We contrastively pre-train _SaFF-Net_ models exemplary with the
Triplet Margin Loss [2]. We investigated the different classification,
reconstruction, and segmentation heads for three datasets, see Tab.
LABEL:tab:pre. For segmentation, we test on the Cardiomegaly subset of VinDr-
CXR.

Table 3: Pretraining _SaFF-Net_ with FFA, CFFA and ResCFFA. ACC - Accuracy,
AUC - Area Under the Receiver Operating characteristic, AP - Mean Average
Precision, SSIM - Mean Structural Similarity Index, PSNR - Peak Signal-to-
Noise Ratio, IoU - Intersection over union.$*$ with Triplet Margin Loss

|  | Classification$*$ | Reconstruction | Segmentation
---|---|---|---|---
(lr)3-6(lr)7-10(lr)11-12 |  | MNIST | Pneumonia | Blood | Pneumonia | VinDr-CXR
|  $\\#$Par. | ACC$\uparrow$ | AUC$\uparrow$ | ACC$\uparrow$ | AUC$\uparrow$ | SSIM$\uparrow$ | PSNR$\uparrow$ | SSIM$\uparrow$ | PSNR$\uparrow$ | ACC$\uparrow$ | IoU$\uparrow$
FFA | 2.8m | 78.2 | 87.9 | 84.9 | 89.5 | $\underline{48.3}$ | $\underline{16.7}$ | 72.3 | $\underline{16.8}$ | 93.2 | 40.1
CFFA | 190k | 72.3 | $\underline{86.5}$ | 84.0 | 88.7 | $\underline{48.3}$ | $\underline{16.7}$ | $\underline{71.6}$ | 17.3 | 90.1 | 24.7
ResCFFA | 150k | $\underline{73.4}$ | 85.2 | $\underline{84.5}$ | $\underline{89.2}$ | 50.1 | 17.1 | 63.8 | 16.3 | $\underline{91.4}$ | $\underline{25.8}$

##  5 Conclusion

We presented a fast Self-adapting Forward-Forward Network (_SaFF-Net_) for
medical imaging analysis, mitigating power consumption and resource
limitations without reliance on back-propagation for model training and fine-
tuning. SaFF-Net shows remarkable performance with a notable $70$% reduction
in NFEs and $35$% in parameters.

_Acknowledgements_ : The authors gratefully acknowledge the scientific support
and HPC resources provided by the Erlangen National High Performance Computing
Center (NHR@FAU) of the Friedrich-Alexander-Universität Erlangen-Nürnberg
(FAU) under the NHR projects b143dc and b180dc. NHR funding is provided by
federal and Bavarian state authorities. NHR@FAU hardware is partially funded
by the German Research Foundation (DFG) – 440719683. Additional support was
also received by the ERC - project MIA-NORMAL 101083647, DFG KA 5801/2-1, INST
90/1351-1 and by the state of Bavaria.

## References

  * [1] Ahamed, M.A., Chen, J., Imran, A.A.Z.: Ffcl: Forward-forward contrastive learning for improved medical image classification. In: Medical Imaging with Deep Learning, short paper track (2023)
  * [2] Balntas, V., Riba, E., Ponsa, D., Mikolajczyk, K.: Learning local feature descriptors with triplets and shallow convolutional neural networks. In: Bmvc. vol. 1, p. 3 (2016)
  * [3] Bianchi, F.M., Scardapane, S., Løkse, S., Jenssen, R.: Reservoir computing approaches for representation and classification of multivariate time series. IEEE transactions on neural networks and learning systems 32(5), 2169–2179 (2020)
  * [4] Blalock, D., Gonzalez Ortiz, J.J., Frankle, J., Guttag, J.: What is the state of neural network pruning? Proceedings of machine learning and systems 2, 129–146 (2020)
  * [5] Brenig, J., Timofte, R.: A study of forward-forward algorithm for self-supervised learning. arXiv preprint arXiv:2309.11955 (2023)
  * [6] Cireşan, D.C., Meier, U., Gambardella, L.M., Schmidhuber, J.: Deep, Big, Simple Neural Nets for Handwritten Digit Recognition. Neural Computation 22(12), 3207–3220 (12 2010). https://doi.org/10.1162/NECO_a_00052, https://doi.org/10.1162/NECO_a_00052
  * [7] De Vita, F., Nawaiseh, R.M., Bruneo, D., Tomaselli, V., Lattuada, M., Falchetto, M.: $\mu$-ff: On-device forward-forward training algorithm for microcontrollers. In: 2023 IEEE International Conference on Smart Computing (SMARTCOMP). pp. 49–56. IEEE (2023)
  * [8] Deng, L.: The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine 29(6), 141–142 (2012)
  * [9] Gandhi, S., Gala, R., Kornberg, J., Sridhar, A.: Extending the forward forward algorithm. arXiv preprint arXiv:2307.04205 (2023)
  * [10] Giampaolo, F., Izzo, S., Prezioso, E., Piccialli, F.: Investigating random variations of the forward-forward algorithm for training neural networks. In: 2023 International Joint Conference on Neural Networks (IJCNN). pp. 1–7. IEEE (2023)
  * [11] Gutmann, M., Hyvärinen, A.: Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In: Proceedings of the thirteenth international conference on artificial intelligence and statistics. pp. 297–304. JMLR Workshop and Conference Proceedings (2010)
  * [12] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770–778 (2016)
  * [13] Hinton, G.: The forward-forward algorithm: Some preliminary investigations. arXiv preprint arXiv:2212.13345 (2022)
  * [14] Hinton, G.E., Sejnowski, T.J., et al.: Learning and relearning in boltzmann machines. Parallel distributed processing: Explorations in the microstructure of cognition 1(282-317), 2 (1986)
  * [15] Hopwood, M.: One-class systems seamlessly fit in the forward-forward algorithm. arXiv preprint arXiv:2306.15188 (2023)
  * [16] Lagani, G., Falchi, F., Gennaro, C., Amato, G.: Comparing the performance of hebbian against backpropagation learning using convolutional neural networks. Neural Computing and Applications 34(8), 6503–6519 (2022)
  * [17] Lică, M.T., Dinucu-Jianu, D.: Sleep patterns in the forward-forward algorithm (2023), https://openreview.net/forum?id=q_lJooPbX_
  * [18] Lillicrap, T.P., Cownden, D., Tweed, D.B., Akerman, C.J.: Random synaptic feedback weights support error backpropagation for deep learning. Nature communications 7(1), 13276 (2016)
  * [19] Lorberbom, G., Gat, I., Adi, Y., Schwing, A., Hazan, T.: Layer collaboration in the forward-forward algorithm. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 38, pp. 14141–14148 (2024)
  * [20] Nguyen, H.Q., Lam, K., Le, L.T., Pham, H.H., Tran, D.Q., Nguyen, D.B., Le, D.D., Pham, C.M., Tong, H.T.T., Dinh, D.H., Do, C.D., Doan, L.T., Nguyen, C.N., Nguyen, B.T., Nguyen, Q.V., Hoang, A.D., Phan, H.N., Nguyen, A.T., Ho, P.H., Ngo, D.T., Nguyen, N.T., Nguyen, N.T., Dao, M., Vu, V.: Vindr-cxr: An open dataset of chest x-rays with radiologist’s annotations (2020)
  * [21] Ororbia, A.: Learning spiking neural systems with the event-driven forward-forward process. arXiv preprint arXiv:2303.18187 (2023)
  * [22] Ororbia, A., Mali, A.: The predictive forward-forward algorithm. arXiv preprint arXiv:2301.01452 (2023)
  * [23] Paliotta, D., Alain, M., Máté, B., Fleuret, F.: Graph neural networks go forward-forward. arXiv preprint arXiv:2302.05282 (2023)
  * [24] Papachristodoulou, A., Kyrkou, C., Timotheou, S., Theocharides, T.: Convolutional channel-wise competitive learning for the forward-forward algorithm. arXiv preprint arXiv:2312.12668 (2023)
  * [25] Pardi, M., Tortorella, D., Micheli, A.: Entropy based regularization improves performance in the forward-forward algorithm
  * [26] Salimans, T., Ho, J., Chen, X., Sidor, S., Sutskever, I.: Evolution strategies as a scalable alternative to reinforcement learning. arXiv preprint arXiv:1703.03864 (2017)
  * [27] Spratling, M.W.: A review of predictive coding algorithms. Brain and cognition 112, 92–97 (2017)
  * [28] Stanley, K.O., Miikkulainen, R.: Evolving neural networks through augmenting topologies. Evolutionary computation 10(2), 99–127 (2002)
  * [29] Tosato, N., Basile, L., Ballarin, E., de Alteriis, G., Cazzaniga, A., Ansuini, A.: Emergent representations in networks trained with the forward-forward algorithm. arXiv preprint arXiv:2305.18353 (2023)
  * [30] Wang, Y., Xia, L., Tang, T., Li, B., Yao, S., Cheng, M., Yang, H.: Low power convolutional neural networks on a chip. In: 2016 IEEE International Symposium on Circuits and Systems (ISCAS). pp. 129–132. IEEE (2016)
  * [31] Yamazaki, K., Vo-Ho, V.K., Bulsara, D., Le, N.: Spiking neural networks and their applications: A review. Brain Sciences 12(7), 863 (2022)
  * [32] Yang, J., Shi, R., Ni, B.: Medmnist classification decathlon: A lightweight automl benchmark for medical image analysis. In: IEEE 18th International Symposium on Biomedical Imaging (ISBI). pp. 191–195 (2021)
  * [33] Yang, J., Shi, R., Wei, D., Liu, Z., Zhao, L., Ke, B., Pfister, H., Ni, B.: Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data 10(1), 41 (2023)
  * [34] Yang, Y.: A theory for the sparsity emerged in the forward forward algorithm. arXiv preprint arXiv:2311.05667 (2023)
  * [35] Zheng, Z., Jia, X.: Complex mixer for medmnist classification decathlon. CoRR abs/2304.10054 (2023), https://doi.org/10.48550/arXiv.2304.10054

Table 4: Ablation Study for CFFA on MNIST and MedMNIST (Supervised). The CFFA network consists of 4 layers with [32,32,128,128] channels each (194,432 # Params). Unless otherwise noted, networks are trained max. 10 epochs with 10,000 layer iterations for CFFA(_One-shot_) and 1,000 layer iterations for CFFA. NFE - Forward and Backward passes $\times 1e^{3}$, ES - Early Stopping | MNIST | MedMNIST Pneumonia
---|---|---
(lr)2-7 (lr)8-13 | CFFA (_One-shot_) | CFFA | CFFA (_One-shot_) | CFFA
(lr)2-4 (lr)5-7 (lr)8-10 (lr)11-13 | ACC | AUC | NFE | ACC | AUC | NFE | ACC | AUC | NFE | ACC | AUC | NFE
(lr)2-2(lr)3-3(lr)4-4(lr)5-5(lr)6-6(lr)7-7(lr)8-8(lr)9-9(lr)10-10(lr)11-11(lr)12-12(lr)13-13(lr)14-14 Baseline | 0.94 | 0.99 | 80.0 | 0.86 | 0.98 | 80.0 | 0.86 | 0.90 | 80.0 | 0.85 | 0.90 | 80.0
ES Iterations | 0.87 | 0.99 | 65.2 | 0.86 | 0.98 | 80.0 | 0.87 | 0.92 | 20.0 | 0.83 | 0.88 | 14.1
ES Layers | 0.94 | 0.99 | 80.0 | 0.87 | 0.96 | 66.0 | 0.86 | 0.90 | 80.0 | 0.82 | 0.86 | 35.0
ES Epoch | - | - | - | 0.86 | 0.98 | 80.0 | - | - | - | 0.85 | 0.89 | 80.0
Pruning (0.05) | 0.91 | 0.99 | 80.0 | 0.85 | 0.99 | 80.0 | 0.84 | 0.89 | 80.0 | 0.85 | 0.90 | 80.0
w/ Retraining | 0.93 | 0.99 | 80.8 | 0.85 | 0.99 | 80.8 | 0.76 | 0.81 | 80.4 | 0.85 | 0.90 | 80.8
Train. Thresh. | 0.92 | 0.99 | 80.0 | 0.89 | 0.99 | 80.0 | 0.87 | 0.91 | 80.0 | 0.87 | 0.91 | 80.0
Batch-Norm | 0.87 | 0.98 | 80.0 | 0.86 | 0.98 | 80.0 | 0.85 | 0.89 | 80.0 | 0.86 | 0.89 | 80.0
_SaFF-Net_ | 0.90 | 0.99 | 71.8 | 0.90 | 0.99 | 80.0 | 0.87 | 0.93 | 37.9 | 0.87 | 0.91 | 80.8

Figure 3: Self-adapting _SaFF-Net_ framework. Key features of the training
data and the hardware components are used for self-configuration. The fixed
parameters for the pipeline are given by default or via an experiment file.
After self-configuration, the _SaFF-Net_ selects the best network
configuration and starts training. Inference, postprocessing, calibration and
pruning can be enabled.

Table 5: Supervised Classification (Batchsize 60,000/MAX; Early Stopping, max
100 Epochs, Seed). _SaFF-Net_ with FFA is used for 1D (flatten) input data and
CFFA is used for 2D/3D input data. Bin. CXR - Binary Classification
(Cardiomegaly) on VinDr-CXR, ACC - Accuracy, AUC - Area Under the Receiver
Operating characteristic, AP - Mean Average Precision.

|  |  |  |  |  |  |  |  |  |  | SaFF-Net _(Ours)_
---|---|---|---|---|---|---|---|---|---|---|---
(lr)12-20 |  | MLP | CNN | ResNet18 | FFA | CFFA | ResCFFA
(lr)3-5 (lr)6-8 (lr)9-11 (lr)12-14 (lr)15-17 (lr)18-20 |  | ACC | AUC | AP | ACC | AUC | AP | ACC | AUC | AP | ACC | AUC | AP | ACC | AUC | AP | ACC | AUC | AP
(lr)3-3(lr)4-4(lr)5-5(lr)6-6(lr)7-7(lr)8-8(lr)9-9(lr)10-10(lr)11-11(lr)12-12(lr)13-13(lr)14-14(lr)15-15(lr)16-16(lr)17-17(lr)18-18(lr)19-19(lr)20-20 | MNIST | 0.798 | 0.959 | 0.796 | 0.512 | 0.859 | 0.730 | 0.921 | 0.990 | 0.961 | 0.970 | 0.999 | 0.993 | 0.873 | 0.987 | 0.916 | 0.928 | 0.986 | 0.993
1-20  MedMNIST | Path | 0.414 | 0.787 | 0.359 | 0.405 | 0.771 | 0.428 | 0.623 | 0.922 | 0.599 | 0.451 | 0.808 | 0.407 | 0.463 | 0.712 | 0.278 | 0.410 | 0.837 | 0.407
Chest | 0.638 | 0.883 | 0.085 | 0.640 | 0.886 | 0.082 | 0.632 | 0.891 | 0.094 | 0.429 | 0.738 | 0.097 | 0.425 | 0.726 | 0.085 | 0.256 | 0.566 | 0.097
Derma | 0.695 | 0.897 | 0.195 | 0.695 | 0.904 | 0.254 | 0.743 | 0.933 | 0.332 | 0.620 | 0.839 | 0.346 | 0.236 | 0.558 | 0.184 | 0.253 | 0.735 | 0.253
OCT | 0.356 | 0.546 | 0.348 | 0.250 | 0.537 | 0.342 | 0.415 | 0.634 | 0.451 | 0.626 | 0.860 | 0.663 | 0.702 | 0.896 | 0.677 | 0.667 | 0.893 | 0.723
Pneum. | 0.677 | 0.828 | 0.902 | 0.633 | 0.472 | 0.345 | 0.789 | 0.846 | 0.811 | 0.886 | 0.912 | 0.886 | 0.870 | 0.900 | 0.840 | 0.851 | 0.930 | 0.914
Retina | 0.435 | 0.680 | 0.274 | 0.435 | 0.756 | 0.310 | 0.493 | 0.737 | 0.322 | 0.463 | 0.733 | 0.354 | 0.382 | 0.661 | 0.313 | 0.405 | 0.733 | 0.388
Breast | 0.731 | 0.820 | 0.677 | 0.731 | 0.773 | 0.577 | 0.859 | 0.887 | 0.805 | 0.750 | 0.809 | 0.762 | 0.743 | 0.784 | 0.674 | 0.686 | 0.748 | 0.730
Blood | 0.384 | 0.837 | 0.408 | 0.380 | 0.792 | 0.315 | 0.805 | 0.971 | 0.805 | 0.630 | 0.907 | 0.671 | 0.532 | 0.800 | 0.511 | 0.556 | 0.919 | 0.706
Tissue | 0.093 | 0.577 | 0.170 | 0.242 | 0.698 | 0.229 | 0.483 | 0.826 | 0.312 | 0.437 | 0.830 | 0.372 | 0.330 | 0.739 | 0.267 | 0.341 | 0.692 | 0.197
OrganA | 0.428 | 0.790 | 0.454 | 0.194 | 0.745 | 0.341 | 0.753 | 0.962 | 0.799 | 0.589 | 0.878 | 0.515 | 0.366 | 0.771 | 0.277 | 0.401 | 0.860 | 0.492
OrganC | 0.397 | 0.775 | 0.408 | 0.222 | 0.676 | 0.322 | 0.747 | 0.957 | 0.785 | 0.636 | 0.898 | 0.570 | 0.332 | 0.687 | 0.234 | 0.390 | 0.856 | 0.481
OrganS | 0.179 | 0.721 | 0.282 | 0.236 | 0.687 | 0.224 | 0.579 | 0.918 | 0.553 | 0.452 | 0.848 | 0.412 | 0.251 | 0.633 | 0.198 | 0.278 | 0.766 | 0.354
1-20  MedMNIST 3D | Organ | 0.213 | 0.665 | 0.474 | 0.138 | 0.626 | 0.163 | 0.615 | 0.913 | 0.652 | 0.232 | 0.674 | 0.270 | 0.195 | 0.605 | 0.145 | 0.281 | 0.762 | 0.273
Nodule | 0.794 | 0.834 | 0.639 | 0.794 | 0.758 | 0.465 | 0.809 | 0.841 | 0.606 | 0.790 | 0.819 | 0.660 | 0.553 | 0.576 | 0.575 | 0.573 | 0.635 | 0.609
Adrenal | 0.768 | 0.827 | 0.604 | 0.768 | 0.758 | 0.480 | 0.768 | 0.776 | 0.523 | 0.631 | 0.587 | 0.576 | 0.737 | 0.765 | 0.564 | 0.683 | 0.671 | 0.591
Fracture | 0.375 | 0.542 | 0.475 | 0.375 | 0.599 | 0.357 | 0.407 | 0.581 | 0.340 | 0.383 | 0.527 | 0.391 | 0.375 | 0.531 | 0.333 | 0.309 | 0.551 | 0.429
Vessel | 0.887 | 0.877 | 0.491 | 0.887 | 0.884 | 0.491 | 0.874 | 0.891 | 0.527 | 0.759 | 0.794 | 0.632 | 0.113 | 0.113 | 0.500 | 0.534 | 0.535 | 0.482
Synapse | 0.270 | 0.302 | 0.551 | 0.730 | 0.718 | 0.487 | 0.709 | 0.710 | 0.515 | 0.270 | 0.238 | 0.474 | 0.730 | 0.738 | 0.517 | 0.683 | 0.708 | 0.501
1-20 Bin. CXR | 0.999 | 0.999 | 0.500 | 0.986 | 0.978 | 0.500 | 0.898 | 0.895 | 0.500 | 0.899 | 0.961 | 0.500 | 0.999 | 0.999 | 0.500 | 0.999 | 0.999 | 0.500
(lr)3-5 (lr)6-8 (lr)9-11 (lr)12-14 (lr)15-17 (lr)18-20 | #Par. | 2,797,010 | 1,554,954 | 11,183,694 | max. 2,797,010 | 194,432 | 148,933


technique as Theorem 2, we can conclude that:

$d_{LP}(\mathcal{D}_{A_{n}}(F^{\prime\prime}_{n}),\mathcal{D}_{A}(F))\xrightarrow{n\to\infty}0,$
(221)

and thus
$\mathcal{S}_{k}(A)\subseteq\lim_{n}\overline{\mathcal{S}_{k,L(n)}(A_{n})}$.
For the other direction, recall that
$\overline{\mathcal{S}_{k}(A)}=\lim_{n}\overline{\mathcal{S}_{k}(A_{n})}$ and
that $\mathcal{S}_{k,L(n)}(A_{n})\subseteq\mathcal{S}_{k}(A)$. Together with
completeness of $d_{H}$, we conclude that

$\lim_{n}d_{H}(\mathcal{S}_{k}(A),\mathcal{S}_{k,L(n)}(A_{n}))=0.$

######  Conjecture 1 (Action convergence of graphop neural networks).

Let $(A_{n})_{n\in\mathbb{N}}$ be an action convergent sequence of graphops.
Then $(\Phi(h,A_{n},\cdot))_{n\in\mathbb{N}}$ is an action convergent sequence
of $P$-operators.