# Quivers of stylic algebras

Antoine Abram  ,  Christophe Reutenauer  and  Franco Saliola  Université du
Québec à Montréal

###### Abstract.

We construct a complete system of primitive orthogonal idempotents and give an
explicit quiver presentation of the monoid algebra of the stylic monoid
introduced by Abram and Reutenauer.

The authors acknowledge the support of the Natural Sciences and Engineering
Research Council of Canada (NSERC). This research was facilitated by computer
exploration using the open-source mathematical software system SageMath
[The22] and its algebraic combinatorics features developed by the Sage-
Combinat community [SCc08].

###### Contents

  1. 1 Introduction
  2. 2 Stylic monoid and algebra
    1. 2.1 Tableaux
    2. 2.2 Schensted’s column insertion procedure
    3. 2.3 Stylic monoid
    4. 2.4 Relationship with the plactic monoid
    5. 2.5 $N$-tableaux
    6. 2.6 The anti-automorphism $\theta$
    7. 2.7 Stylic algebra
  3. 3 Primitive idempotents of the stylic algebra
  4. 4 The quiver of the stylic algebra
    1. 4.1 A quiver
    2. 4.2 A lemma on edges and idempotents
    3. 4.3 A quiver map
    4. 4.4 Extended quiver
    5. 4.5 The surjectivity of the quiver map
    6. 4.6 The kernel of the quiver map
    7. 4.7 The quiver of the stylic algebra
    8. 4.8 Cartan invariants and Indecomposable Projective Modules

##  1\. Introduction

We study the monoid algebra of the stylic monoid $Styl(A)$ introduced by the
first two authors in [AR22]. We begin by recalling its definition.

Let $A$ be a totally ordered finite alphabet and $A^{*}$ the free monoid that
it generates. The _Robinson–Schensted–Knuth (RSK) correspondence_ associates
with each word $w\in A^{*}$ a semistandard tableau $P(w)$ with entries in $A$
called its _$P$ -symbol_. If $w$ is a decreasing word, then its $P$-symbol
$P(w)$ is a column, which allows us to identify the set of decreasing words on
$A$ with the set $\Gamma(A)$ of column-shaped tableaux with entries in $A$.
This induces a left action of $A^{*}$ on $\Gamma(A)$: for a word $x\in A^{*}$
and a column $\gamma\in\Gamma(A)$, take $x\cdot\gamma$ to be the first column
of the tableau $P(xw)$, where $w$ is the decreasing word corresponding to the
column $\gamma$. (This action can be defined using the Schensted column
insertion procedure; see §2.2.) The finite monoid of endofunctions of
$\Gamma(A)$ obtained by this action is the _stylic monoid $Styl(A)$_.

It turns out that $Styl(A)$ is canonically isomorphic to a quotient of the
celebrated plactic monoid. Recall that the plactic monoid has appeared in many
contexts in algebraic combinatorics and was used to give the first rigorous
proof of the _Littlewood–Richardson rule_ [Sch77, LS81, Lot02]. The monoid
algebra $\mathbb{K}Styl(A)$, where $\mathbb{K}$ is any field, is the first
example of a finite dimensional representation of the plactic monoid that does
not pass through the abelianisation (to our knowledge). This article is a
first step towards understanding the structure of this representation.

Stylic monoids are examples of $\mathscr{J}$-trivial monoids [AR22], which are
a ubiquitous class of monoids that arise naturally in algebraic combinatorics.
Other examples include the $0$-Hecke monoids associated with finite Coxeter
groups, and the monoids of regressive order-preserving functions on a poset;
see [DHST11] for many more examples. It follows that the monoid algebra
$\mathbb{K}Styl(A)$ admits a _quiver presentation_ : that is,
$\mathbb{K}Styl(A)$ is isomorphic to a quotient of the path algebra
$\mathbb{K}Q(A)$ of a canonical quiver $Q(A)$.

Obtaining a quiver presentation is an essential step towards applying the
tools and techniques from the modern representation theory of finite
dimensional algebras [ASS06]. One of our main results is an explicit
presentation of $\mathbb{K}Styl(A)$ as a _quiver with relations_. Our approach
is constructive in the sense that we explicitly identify a complete system of
primitive orthogonal idempotents in $\mathbb{K}Styl(A)$ (Theorem 3.1) that we
use to define a quiver $Q(A)$ together with a surjective map
$\varphi:\mathbb{K}Q(A)\xrightarrow{}\mathbb{K}Styl(A)$ (Corollary 4.12) whose
kernel is an admissible ideal (Theorem 4.14). General theory then implies that
$Q(A)$ is the quiver of $\mathbb{K}Styl(A)$ (Theorem 4.15).

We remark that the representation theory of finite monoids naturally occurring
in algebraic combinatorics, especially in connection with Markov chains, has
been investigated by many authors: [BD98, BHR99, BBD99, Bro00, Bro04, Sal07,
Sal09, BBBS11, GM11, MS11, MS12a, MS12b, HST13, GM14, ASST15, MSS15, MS18,
Ste20, MSS21]; see especially Steinberg’s recent book and the references
therein [Ste16]. Those most closely related to the present work are [DHST11],
[Ste16, Chapter 17] and [MS18], which describe the quiver of the algebra of a
$\mathscr{J}$-trivial monoid. While guided by this work, our approach is
complementary and completely self-contained as their techniques do not involve
constructing primitive orthogonal idempotents or a quiver presentation. In
fact, in [MS18] one reads _“It is notoriously difficult to write down explicit
primitive idempotents for monoids algebras (c.f.[BBBS11, Den11]) and often
they have complicated expressions in terms of the monoid basis, making it
virtually impossible to determine even the dimension of the corresponding
projective indecomposable module let alone construct a matrix representation
out of it.”_

##  2\. Stylic monoid and algebra

We consider a totally ordered finite set $A$, whose elements are called
letters, and the free monoid $A^{*}$ that it generates. Its elements are
called words. The alphabet of a word $x$ is the set of letters $Alph(x)$
appearing in $x$.

###  2.1. Tableaux

We call a tableau what is usually called a semistandard Young tableau: a
finite lower order ideal of the poset $\mathbb{N}^{2}$, ordered naturally
(that is, a finite subset $E\subset\mathbb{N}^{2}$ such that $x\leq y$ and
$y\in E$ implies $x\in E$), together with a weakly increasing mapping into
$A$, such that the restriction of this mapping to each subset with given
$x$-coordinate is injective. A tableau is usually represented as in Figure 1.
The conditions may be expressed by saying that the letters in $A$ are weakly
increasing from left to right in each row, and strictly increasing from the
bottom to top in each column.

d
b& b
aac

Figure 1. A tableau

A column is a tableau with only one column. The set of columns on $A$ is
denoted by $\Gamma(A)$. A column is identified naturally with a subset of $A$,
and also with the word in $A^{*}$ that is the decreasing product of its
elements.

###  2.2. Schensted’s column insertion procedure

Let us recall the Schensted column insertion algorithm. Let $\gamma$ be a
column, viewed here as a subset of $A$, and let $x\in A$. There are two cases:
if $\forall y\in\gamma,x>y$, then define $\gamma^{\prime}=\gamma\cup x$.
Otherwise, let $y$ be the smallest element in $\gamma$ with $y\geq x$; then
define $\gamma^{\prime}=(\gamma\setminus y)\cup x$. Then $\gamma^{\prime}$ is
the column obtained by column insertion of $x$ into $\gamma$, and in the
second case, $y$ is said to be bumped.

We define a left action of $A^{*}$ on $\Gamma(A)$, denoted $u\cdot\gamma$, for
each $u\in A^{*}$ and each column $\gamma$. Since $A^{*}$ is the free monoid
on $A$, it is enough to define the action for each letter $a\in A$. Define

$a\cdot\gamma=\gamma^{\prime}$

if $\gamma^{\prime}$ is obtained from $\gamma$ by column insertion of $a$ into
$\gamma$.

For further use, we note that if $\gamma$ is a column, then we have

$\gamma\cdot\emptyset=\gamma,$

where on the left-hand side, $\gamma$ is viewed as a decreasing word.

###  2.3. Stylic monoid

We denote by $Styl(A)$ the monoid of endofunctions of the set $\Gamma(A)$ of
columns obtained by the action defined above. Thus, a typical element of
$Styl(A)$ is a function

$\displaystyle\mu_{w}:\Gamma(A)$ $\displaystyle\to$ $\displaystyle\Gamma(A)$
$\displaystyle\gamma$ $\displaystyle\mapsto$ $\displaystyle w\cdot\gamma$

for some word $w\in A^{*}$. Since $\Gamma(A)$ is finite, $Styl(A)$ is finite.
Let $\mu:A^{*}\to Styl(A)$ be the canonical monoid homomorphism defined by
$\mu(w)=\mu_{w}$.

We denote by $\equiv_{styl}$ the corresponding monoid congruence of $A^{*}$,
called the stylic congruence:

$u\equiv_{styl}v\quad\Longleftrightarrow\quad\mu(u)=\mu(v)\quad\Longleftrightarrow\quad
u\cdot\gamma=v\cdot\gamma\text{~{}for all columns $\gamma$.}$

The monoid $Styl(A)$ acts naturally on the set of columns, and we take the
same notation: $m\cdot\gamma=w\cdot\gamma$ if $m=\mu(w)$.

###  2.4. Relationship with the plactic monoid

The Schensted $P$-symbol is a mapping that associates with each word $w$ on
$A$ a tableau $P(w)$, see [Sag01, Lot02]. The relation $\equiv_{plax}$ on
$A^{*}$, defined by

$u\equiv_{plax}v\quad\Longleftrightarrow\quad P(u)=P(v),$

is a congruence of the monoid $A^{*}$, called the plactic congruence. The
quotient monoid $A^{*}/{\equiv_{plax}}$ is called the plactic monoid.

The column-reading word of a tableau is the word obtained by reading the
columns from left to right, each column being read as a decreasing word. For
example, the column reading word of the tableau from Figure 1 is the word
$dbabac$. If $T$ is a tableau, with column-reading word $w$, then

(1) $P(w)=T$

by a theorem of Schensted.

The plactic relations, due to Knuth, are the following relations:

(2) $bac\equiv_{plax}bca,\qquad acb\equiv_{plax}cab$

for any choice of letters $a<b<c$ in $A$, and

(3) $bab\equiv_{plax}bba,\qquad aba\equiv_{plax}baa$

for any choice of letters $a<b$ in $A$. The plactic congruence is generated by
these relations.

By [AR22, Theorem 8.1], the stylic congruence is generated by the plactic
relations (2) and (3) together with the idempotent relations $a^{2}=a$ for any
letter $a$ in $A$. It then follows that if $B\subset A$, then there is a
natural embedding $Styl(B)\to Styl(A)$ [AR22, Corollary 8.4].

###  2.5. $N$-tableaux

According to [AR22, Theorem 7.1], there is a mapping from $A^{*}$ into the set
of tableaux that induces a bijection from the stylic monoid $Styl(A)$ onto the
set of $N$-tableaux on $A$. The image of $x\in A^{*}$ is denoted $N(x)$ and is
called the $N$-tableau of $x$. We also denote by $N$ the induced bijection
from the stylic monoid onto the set of $N$-tableaux. The precise definition of
$N$ is not needed here, rather we will make use of the following properties of
$N$.

######  Proposition 2.1.

  * [leftmargin=10pt]

  * •

The first column of $N(x)$ is equal to that of the $P$-symbol $P(x)$, and it
is $x\cdot\emptyset$, where $\emptyset$ denotes the empty column.

  * •

The set of $a\in A$ fixing $w\in Styl(A)$ on the left ($aw=w$) is equal to the
first column of $N(w)$.

  * •

If $x$ is in $Styl(A)$, then the column-reading word $w$ of $N(x)$ satisfies

(4) $x=\mu(w).$

###### Proof.

The first statement is [AR22, Lemma 7.2 (i)]. The second statement follows
from [AR22, Theorem 11.4] and definition of the left $N$-insertion. The third
statement follows from the analogous statement for row-reading words, which is
[AR22, Equation 5], and the fact that column-reading and row-reading words of
the same tableau are plactic-, hence stylic-, equivalent. ∎

###  2.6. The anti-automorphism $\theta$

Recall, from [AR22, Section 9], the involutive anti-automorphism $\theta$ of
the monoid $A^{*}$: when restricted to $A$, it reverses the order of $A$. It
extends to an endofunction of $\Gamma(A)$, if one identifies as we do columns
on $A$ and subsets of $A$. Since $\theta$ preserves the plactic relations, and
the idempotent relations, it induces an anti-automorphism of the monoids
$A^{*}$, $Plax(A)$ and $Styl(A)$.

###  2.7. Stylic algebra

We denote by $\mathbb{Z}Styl(A)$ the $\mathbb{Z}$-algebra of the stylic
monoid, and we call it the stylic algebra over $\mathbb{Z}$. We shall consider
also the stylic algebra over a field $\mathbb{K}$, which we denote by
$\mathbb{K}Styl(A)$.

######  Lemma 2.2.

Let $x\in\mathbb{Z}Styl(A)$ and let $a$ be a letter such that each letter
appearing in $x$ is larger or equal to $a$.

(i) $axa=xa$;

(ii) $(1-a)xa=0$

(iii) $(1-a)x(1-a)=(1-a)x$.

###### Proof.

(i) follows from Lemma 9.4 in [AR22]. Next, (ii) and (iii) follow by an
evident computation. ∎

The next lemma extends the plactic relations in (3).

######  Lemma 2.3.

Let $p,q\geq 1$. Consider letters in $A$ satisfying
$x_{1}<\cdots<x_{p}<y<z_{1}<\cdots<z_{q}$, then

$(x_{1}\cdots x_{p})(z_{1}\cdots z_{q})y\equiv_{styl}(z_{1}\cdots
z_{q})(x_{1}\cdots x_{p})y,$

and

$y(x_{1}\cdots x_{p})(z_{1}\cdots z_{q})\equiv_{styl}y(z_{1}\cdots
z_{q})(x_{1}\cdots x_{p}).$

###### Proof.

We prove the first identity by double induction. Suppose first that $q=1$. If
$p=1$, we are reduced to the plactic relation
$x_{1}z_{1}y\equiv_{styl}z_{1}x_{1}y.$ Suppose that $p\geq 2$. Then, by the
plactic relations, we have

$(x_{1}\cdots x_{p-1})x_{p}z_{1}y\equiv_{styl}(x_{1}\cdots
x_{p-1})z_{1}x_{p}y\equiv_{styl}z_{1}(x_{1}\cdots x_{p-1})x_{p}y$

by induction on $p$ applied to the product $(x_{1}\cdots x_{p-1})z_{1}x_{p}$.

Suppose now that $q\geq 2$. Then, using the congruences
$z_{q}y\equiv_{styl}z_{q}yy\equiv_{styl}yz_{q}y$ twice, we have

$\displaystyle x_{1}\cdots x_{p}z_{1}\cdots z_{q}y$
$\displaystyle\equiv_{styl}x_{1}\cdots x_{p}z_{1}\cdots z_{q-1}yz_{q}y$
$\displaystyle\equiv_{styl}z_{1}\cdots z_{q-1}x_{1}\cdots x_{p}yz_{q}y$ (by
induction on $q$) $\displaystyle\equiv_{styl}z_{1}\cdots z_{q-1}x_{1}\cdots
x_{p}z_{q}y$ $\displaystyle\equiv_{styl}z_{1}\cdots z_{q-1}z_{q}x_{1}\cdots
x_{p}y$ $\displaystyle\text{(case $q=1$)}.$

By applying the anti-automorphism $\theta$ to the first identity we obtain

$\theta(y)\theta(z_{q})\cdots\theta(z_{1})\theta(x_{p})\cdots\theta(x_{1})\equiv_{plax}\theta(y)\theta(x_{p})\cdots\theta(x_{1})\theta(z_{q})\cdots\theta(z_{1}).$

Note that

$\theta(z_{q})<\cdots<\theta(z_{1})<\theta(y)<\theta(x_{p})<\cdots<\theta(x_{1}).$

Hence we obtain the second identity of the lemma by a change of variables,
after exchanging $p$ and $q$. ∎

##  3\. Primitive idempotents of the stylic algebra

In this section, we construct a complete system of primitive orthogonal
idempotents in the stylic algebra $\mathbb{Z}Styl(A)$.

Recall that $\Gamma(A)$ denotes the set of columns on the totally ordered
finite alphabet $A$. Let $\gamma\in\Gamma(A)$ be a column and define

(5)
$e_{\gamma}=\prod^{\nearrow}_{a\notin\gamma}(1-a)\prod^{\searrow}_{a\in\gamma}a\in\mathbb{Z}Styl(A),$

where the arrows indicate that the first product is in increasing order of
letters, and the second in decreasing order.

For future use, we note that the second product in (5) is the image of
$\gamma$ (viewed as a word) in $Styl(A)$; since decreasing words are
idempotent in $Styl(A)$ [AR22, Theorem 12.1], we have

(6) $e_{\gamma}\gamma=e_{\gamma}.$

######  Theorem 3.1.

The idempotents $e_{\gamma}$, one for each $\gamma\in\Gamma(A)$, form a
complete system of primitive orthogonal idempotents of $\mathbb{Z}Styl(A)$.
Precisely, we have

  1. (1)

$e_{\gamma}^{2}=e_{\gamma}$ and $e_{\gamma}e_{\delta}=0$ for all
$\gamma,\delta\in\Gamma(A)$ with $\delta\neq\gamma$;

  2. (2)

$\sum_{\gamma\in\Gamma(A)}e_{\gamma}=1$;

  3. (3)

for every $\gamma\in\Gamma(A)$, the idempotent $e_{\gamma}$ cannot be written
as $e_{\gamma}=x+y$ with $x$ and $y$ nonzero orthogonal idempotents in
$\mathbb{Z}Styl(A)$.

###### Proof.

1\. We show that the elements $e_{\gamma}$ are orthogonal idempotents, by
induction on the cardinality of the alphabet $A$. We use the fact that
$Styl(B)$ embeds canonically in $Styl(A)$ if $B\subset A$, and similarly for
their monoid algebras.

Let $a$ be the smallest letter in $A$. Let $\gamma$ and $\delta$ be two
columns on $A$. For $\gamma^{\prime}\in\Gamma(A\setminus a)$, we denote by
$e^{\prime}_{\gamma^{\prime}}$ the elements (5) relative to the alphabet
$A\setminus a$. We distinguish four cases:

– If $a\in\gamma\cap\delta$, then by (5),
$e_{\gamma}=e^{\prime}_{\gamma\setminus a}a$ and
$e_{\delta}=e^{\prime}_{\delta\setminus a}a$. Note that $\gamma=\delta$ if and
only if $\gamma\setminus a=\delta\setminus a$, and so, by induction
$e^{\prime}_{\gamma\setminus a}e^{\prime}_{\delta\setminus
a}=e^{\prime}_{\gamma\setminus a}$ if $\gamma=\delta$, and
$e^{\prime}_{\gamma\setminus a}e^{\prime}_{\delta\setminus a}=0$ if
$\gamma\neq\delta$. Thus we have
$e_{\gamma}e_{\delta}=e^{\prime}_{\gamma\setminus
a}ae^{\prime}_{\delta\setminus a}a=e^{\prime}_{\gamma\setminus
a}e^{\prime}_{\delta\setminus a}a$ (by Lemma 2.2 (i)), and this is equal to
$e^{\prime}_{\gamma\setminus a}a=e_{\gamma}$ if $\gamma=\delta$, and to $0$ if
$\gamma\neq\delta$.

– Suppose now that $a\notin\gamma\cup\delta$. Then
$e_{\gamma}=(1-a)e^{\prime}_{\gamma}$ and
$e_{\delta}=(1-a)e^{\prime}_{\delta}$. By Lemma 2.2 (iii), we have
$e_{\gamma}e_{\delta}=(1-a)e^{\prime}_{\gamma}(1-a)e^{\prime}_{\delta}=(1-a)e^{\prime}_{\gamma}e^{\prime}_{\delta}$.
Thus, $e_{\gamma}e_{\delta}$ is $e_{\gamma}$ if $\gamma=\delta$, and it is $0$
if $\gamma\neq\delta$.

– Suppose that $a\in\gamma,a\notin\delta$. Then $\gamma\neq\delta$ and
$e_{\gamma}e_{\delta}=e^{\prime}_{\gamma\setminus
a}a(1-a)e^{\prime}_{\delta}=e^{\prime}_{\gamma\setminus
a}(a-a^{2})e^{\prime}_{\delta}=0$ since $a$ is idempotent.

– Suppose that $a\notin\gamma,a\in\delta$. Then $\gamma\neq\delta$ and
$e_{\gamma}e_{\delta}=(1-a)e^{\prime}_{\gamma}e^{\prime}_{\delta\setminus
a}a=0$ by Lemma 2.2 (ii).

2\. We show that the sum in $\mathbb{Z}Styl(A)$ of all $e_{\gamma}$ is equal
to 1. Actually we show that this equality holds in the algebra of
noncommutative polynomials. By inspection of (5), one sees that this sum is
equal to a linear combination of all multilinear (without repeated letter)
words on $A$ of the form $w=xy$, where $x$ is strictly increasing, and $y$ is
strictly decreasing. Let $w$ be such a nonempty word; then $w$ has a unique
factorization $w=uzv$, where $u$ is strictly increasing, $v$ is strictly
decreasing and $z$ is the largest letter in $w$. Denote by $U$ the alphabet of
$u$, and by $V$ that of $v$. Then the coefficient of $w$ in $e_{V}$ is
$(-1)^{|U|+1}$ and in $e_{V\cup z}$ it is $(-1)^{|U|}$, while in all other
$e_{\gamma}$ it is 0 (recall that we identify columns in $\Gamma(A)$ and
subsets of $A$). Thus the coefficient of $w$ in the sum is $0$, and therefore
the sum is equal to 1.

3\. We show that the idempotents are primitive. First note that since
$\mathbb{Z}Styl(A)\subset\mathbb{C}Styl(A)$, it suffices to prove it in
$\mathbb{C}Styl(A)$. Next, we make use of the following characteristisation:
an idempotent $e$ of a finite dimensional $\mathbb{C}$-algebra $X$ is
primitive if and only if $0$ and $e$ are distinct and are the only idempotents
in $eXe$ (see, for instance, [ARS97, Section I.4], [ASS06, Corollary 4.7], or
[Ste16, Proposition A.22]). Thus it is enough to prove that
$e_{\gamma}\mathbb{C}Styl(A)e_{\gamma}=\mathbb{C}e_{\gamma}$, which we do by
induction on the cardinality of $A$. Let $a=\min(A)$ and $w\in A^{*}$.

– Suppose $a\in\gamma$. Then
$e_{\gamma}we_{\gamma}=e^{\prime}_{\gamma\setminus
a}awe^{\prime}_{\gamma\setminus a}a=e^{\prime}_{\gamma\setminus
a}w^{\prime}e^{\prime}_{\gamma\setminus a}a$, by repeated application of Lemma
2.2 (i), where $w^{\prime}$ is obtained from $w$ by removing all occurrences
of $a$. Hence, $e^{\prime}_{\gamma\setminus
a}w^{\prime}e^{\prime}_{\gamma\setminus a}\in\mathbb{C}Styl(A\backslash a)$,
so by induction there exists $z\in\mathbb{C}$ such that
$e_{\gamma}we_{\gamma}=$ $(e^{\prime}_{\gamma\setminus
a}w^{\prime}e^{\prime}_{\gamma\setminus a})a=(ze^{\prime}_{\gamma\setminus
a})a=ze_{\gamma}$.

– Suppose $a\notin\gamma$. Then
$e_{\gamma}we_{\gamma}=(1-a)e^{\prime}_{\gamma\setminus
a}w(1-a)e^{\prime}_{\gamma\setminus a}$. This is equal to
$(1-a)e^{\prime}_{\gamma\setminus a}we^{\prime}_{\gamma\setminus a}$ by Lemma
2.2 (iii), and by induction there exists $z\in\mathbb{C}$ such that
$(1-a)(e^{\prime}_{\gamma\setminus a}we^{\prime}_{\gamma\setminus
a})=(1-a)(ze^{\prime}_{\gamma\setminus a})=ze_{\gamma}$.

To conclude, it is enough to show that the $e_{\gamma}$ are nonzero. For this,
it suffices to note that each $e_{\gamma}$ contains a unique element that is
minimal with respect to the $\mathscr{J}$-order on the monoid; we delay the
details to the proof of Proposition 4.11 (which will be proved independently),
in which we construct a basis of the monoid algebra of $Styl(A)$ that includes
these idempotents. ∎

##  4\. The quiver of the stylic algebra

In this section, we identify the quiver of $\mathbb{K}Styl(A)$ over a field
$\mathbb{K}$. We do this by defining a quiver $Q(A)$ in §4.1 together with a
$\mathbb{K}$-algebra morphism $\varphi:\mathbb{K}Q(A)\to\mathbb{K}Styl(Q)$ in
§4.3 that is surjective (proved in §4.5) and whose kernel is an _admissible
ideal_ (proved in §4.6). Such a morphism uniquely determines the quiver of an
algebra; see §4.7 for details. Most of the results hold over $\mathbb{Z}$, so
we work over $\mathbb{Z}$ whenever possible.

###  4.1. A quiver

We define a right action of the monoid $A^{*}$ on the set $\Gamma(A)$ of
columns on $A$. It is enough to define the action of each letter on each
column. Let $c$ be a letter and $\gamma$ a column. If $c<\min(\gamma)$, we let
$\gamma\cdot c=\gamma\cup c$. Otherwise, $c\geq\min(\gamma)$ and we let
$b=\max\\{x\in\gamma:x\leq c\\}$; then $\gamma\cdot c=c\cup(\gamma\setminus
b)$; we then say that $b$ is bumped. Compactly,

$\gamma\cdot c=\big{(}\gamma\setminus\max\\{x\in\gamma:x\leq
c\\}\big{)}\cup\big{\\{}c\big{\\}}.$

We say that the right action of $c$ on $\gamma$ is frank if
$c\geq\min(\gamma)$ and if $c\notin\gamma$. Note that in this case, $\gamma$
and $\gamma\cdot c$ have the same height.

We define a quiver $Q(A)$ with edges labelled in $A$: its set of vertices is
$\Gamma(A)$; and there is a labelled edge
$\gamma\xrightarrow{c}\gamma^{\prime}$ if $\gamma\cdot c=\gamma^{\prime}$ and
if the action is frank; see Figure 2. As usual, the label of a path is the
word in $A^{*}$ that is the product of the labels of the edges of the path.

$\epsilon$$a$$b$$ba$$b$

$\epsilon$$a$$b$$c$$ba$$ca$$cb$$cba$$b$$c$$c$$c$$b$

$\epsilon$$a$$b$$c$$d$$ba$$ca$$da$$cb$$db$$dc$$cba$$dba$$dca$$dcb$$dcba$$b$$c$$d$$c$$d$$d$$c$$d$$b$$d$$d$$b$$c$$c$$d$$c$$b$

Figure 2. The quivers for alphabets of cardinality $2,3,4$; the columns are
represented by decreasing words and the empty word is denoted $\epsilon$.

For later use, we note the following result relating the left and right
actions. The proof is left to the reader.

######  Lemma 4.1.

For two columns of the same height $\gamma,\delta$, and two letters $b,c$, the
two following conditions are equivalent:

(i) $b\cdot\delta=\gamma$ and $c$ is bumped;

(ii) $\gamma\cdot c=\delta$, and $b$ is bumped.

###  4.2. A lemma on edges and idempotents

We give a technical, but important, result on the idempotents of the stylic
algebra and the quiver introduced previously.

######  Lemma 4.2.

Let $\gamma\xrightarrow{c}\delta$ be an edge in the quiver $Q(A)$, and denote
by $b$ the bumped letter, so that $\delta=c\cup(\gamma\setminus b)$, and
$b\in\gamma,c\notin\gamma,b\notin\delta,c\in\delta$. Then in
$\mathbb{Z}Styl(A)$

$be_{\gamma}c=bce_{\delta}\qquad\text{and}\qquad
e_{\gamma}ce_{\delta}=e_{\gamma}c.$

###### Proof.

I. We prove the first identity. Let $a=\min(A)$. As in the proof of Theorem
3.1, denote by $e^{\prime}_{\gamma^{\prime}}$ the idempotents (5) relative to
the alphabet $A\setminus a$.

1\. Suppose that $a\in\gamma\cap\delta$. Since the action $\gamma\cdot c$ is
frank, and since $a$ cannot be bumped, we have $a<b<c$. Let
$\gamma^{\prime}=\gamma\setminus a$ and $\delta^{\prime}=\delta\setminus a$.
Then $\delta^{\prime}=\gamma^{\prime}\cdot c$ and the action is frank. By
induction, we deduce that
$be^{\prime}_{\gamma^{\prime}}c=bce^{\prime}_{\delta^{\prime}}$. Note that the
minimum of $\gamma^{\prime}$ is a letter $x$ such that $a<x<c$; thus $xac=xca$
and since $x$ is the last factor in the product (5) defining
$e^{\prime}_{\gamma^{\prime}}$, we have
$e^{\prime}_{\gamma^{\prime}}ac=e^{\prime}_{\gamma^{\prime}}ca$. We have
$e_{\gamma}=e^{\prime}_{\gamma^{\prime}}a$ and
$e_{\delta}=e^{\prime}_{\delta^{\prime}}a$. Thus
$be_{\gamma}c=be^{\prime}_{\gamma^{\prime}}ac=be^{\prime}_{\gamma^{\prime}}ca=bce^{\prime}_{\delta^{\prime}}a=bce_{\delta}$.

2\. Suppose that $a\notin\gamma\cup\delta$. Then $a<b<c$. Moreover
$\delta\xrightarrow{c}\delta^{\prime}$ is an edge in the quiver $Q(A\setminus
a)$ and $b$ is bumped. With notations similar to 1, we have
$e_{\gamma}=(1-a)e^{\prime}_{\gamma^{\prime}}$ and
$e_{\delta}=(1-a)e^{\prime}_{\delta^{\prime}}$. Since
$b(1-a)b=b^{2}-bab=b^{2}-ba=b(1-a)$ and $bac=bca$, we have
$be_{\gamma}c=b(1-a)e^{\prime}_{\gamma^{\prime}}c=b(1-a)be^{\prime}_{\gamma^{\prime}}c=b(1-a)bce^{\prime}_{\delta^{\prime}}$
(by induction)
$=b(1-a)ce^{\prime}_{\delta^{\prime}}=bc(1-a)e^{\prime}_{\delta^{\prime}}=bce_{\delta}$.

3\. Suppose that $a\in\gamma$ and $a\notin\delta$. Then the bumped letter is
$b=a$. We denote by $\gamma$ and $\delta$ the decreasing words associated with
these two columns. Since $c\in\delta$, we have $\delta=\delta_{1}c\delta_{2}$,
where each letter in $\delta_{1}$ is larger than $c$; hence
$c\delta\equiv_{styl}\delta$ by Lemma 2.2 (i). Moreover, $\delta
c\equiv_{styl}\delta$ since $c$ is the smallest, hence last, letter of
$\delta=\delta^{\prime}c$ and $c^{2}=c$.

We have

(7) $\gamma c\equiv_{styl}a\delta,$

since this holds even plactically as one sees by computing the image under $P$
of both sides (for $P(a\delta)$, Schensted left insert $a$ into $\delta$ and
use Lemma 4.1).

Let $y_{1},\ldots,y_{s},z_{1},\ldots,z_{t}$ be the letters in $A$ that do not
appear in $\gamma$ nor in $\delta$, ordered so that

$a~{}<~{}y_{1}<\cdots<y_{s}~{}<~{}c~{}<~{}z_{1}<\cdots<z_{t}.$

Then

$\displaystyle e_{\gamma}$
$\displaystyle=\prod_{j=1}^{s}(1-y_{j})(1-c)\prod_{k=1}^{t}(1-z_{k})\gamma$
$\displaystyle e_{\delta}$
$\displaystyle=(1-a)\prod_{j=1}^{s}(1-y_{j})\prod_{k=1}^{t}(1-z_{k})\delta.$

Thus, by (7),
$ae_{\gamma}c=a\prod_{j=1}^{s}(1-y_{j})(1-c)\prod_{k=1}^{t}(1-z_{k})a\delta$.
Note that $\prod_{j=1}^{s}(1-y_{j})$ is equal to $1$ plus a linear combination
of $uy$, with

$a<y<c<z_{1}<\cdots<z_{t}.$

Therefore, $ae_{\gamma}c$ is equal to $a(1-c)\prod_{k=1}^{t}(1-z_{k})a\delta$
plus a linear combination of $auy(1-c)\prod_{k=1}^{t}(1-z_{k})a\delta$, and we
show that each term in the linear combination vanishes.

Note that it suffices to show that
$y\prod_{k=1}^{t}(1-z_{k})a\delta=yc\prod_{k=1}^{t}(1-z_{k})a\delta$. We prove
this equality, starting from the right-hand side: since
$\delta=\delta^{\prime}c$, we have
$yc\prod_{k=1}^{t}(1-z_{k})a\delta=yc\prod_{k=1}^{t}(1-z_{k})a\delta^{\prime}c=yac\prod_{k=1}^{t}(1-z_{k})\delta^{\prime}c$
(since by the second identity in Lemma 2.3, we have
$yac\prod_{k=1}^{t}(1-z_{k})=yc\prod_{k=1}^{t}(1-z_{k})a$)
$=ya\prod_{k=1}^{t}(1-z_{k})\delta^{\prime}c$ (by Lemma 2.2 (i), since all
letters $z_{i}$ and in $\delta^{\prime}$ are $>c$)
$=y\prod_{k=1}^{t}(1-z_{k})a\delta$, by the same identity in Lemma 2.3.

It follows that
$ae_{\gamma}c=a(1-c)\prod_{k=1}^{t}(1-z_{k})a\delta=a(1-c)\prod_{k=1}^{t}(1-z_{k})ac\delta$
(since $c\delta=\delta$) $=a(1-c)a\prod_{k=1}^{t}(1-z_{k})c\delta$ (by the
first identity in Lemma 2.3) $=a(1-c)ac\prod_{k=1}^{t}(1-z_{k})c\delta$ (by
Lemma 2.2 (i)) $=(ac-ca)\prod_{k=1}^{t}(1-z_{k})\delta$.

On the other hand, we have
$ace_{\delta}=ac(1-a)\prod_{j=1}^{s}(1-y_{j})\prod_{k=1}^{t}(1-z_{k})\delta=(ac-
ca)\prod_{j=1}^{s}(1-y_{j})\prod_{k=1}^{t}(1-z_{k})\delta$. Note that
$\prod_{j=1}^{s}(1-y_{j})$ is equal to $1$ plus a linear combination of $yu$,
with $a<y<c$. Since $(ac-ca)y=acy-cay=0$ (plactic relation), we obtain
$ace_{\delta}=(ac-ca)\prod_{k=1}^{t}(1-z_{k})\delta$.

It follows that $ae_{\gamma}c=ace_{\delta}$.

4\. The last case to consider is when $a\notin\gamma$ and $a\in\delta$;
however, it does not occur because the action $\gamma\cdot c$ is frank (in
particular, if $a\notin\gamma$, then $a\notin\delta$).

II. We prove now the second identity. Note that
$\gamma=\gamma_{1}b\gamma_{2}$, where each letter in $\gamma_{2}$ is smaller
that $b$; hence $\gamma b=\gamma$, by the dual statement of Lemma 2.2 (i). We
have, using the fact that $\gamma$ is idempotent in $Styl(A)$ (see the
sentence before (6)):

$\displaystyle e_{\gamma}ce_{\delta}$ $\displaystyle=e_{\gamma}bce_{\delta}$
(since $e_{\gamma}=e_{\gamma}\gamma=e_{\gamma}\gamma b=e_{\gamma}b$)
$\displaystyle=e_{\gamma}be_{\gamma}c$ (by the first identity in the lemma,
already proved) $\displaystyle=e_{\gamma}e_{\gamma}c$ (since
$e_{\gamma}b=e_{\gamma}$) $\displaystyle=e_{\gamma}c$
$\displaystyle\text{\small(since $e_{\gamma}$ is idempotent)}.$

###  4.3. A quiver map

Let $Q=Q(A)$ be the quiver defined in Subsection 4.1. The path algebra
$\mathbb{Z}Q$ is the free $\mathbb{Z}$-module with basis the set of paths in
the quiver, including an empty path around each vertex $\gamma$ (this empty
path is denoted $\gamma$); the product is the unique product extending the
natural product of paths.

We define a $\mathbb{Z}$-linear mapping
$\varphi:\mathbb{Z}Q\to\mathbb{Z}Styl(A)$ as follows:

  * •

if $\gamma$ is an empty path, then

$\varphi(\gamma)=e_{\gamma};$

  * •

if

(8)
$\gamma_{0}\xrightarrow{c_{1}}\gamma_{1}\xrightarrow{c_{2}}\cdots\xrightarrow{c_{l}}\gamma_{l}$

is a path in $Q$, then its image under $\varphi$ is

$e_{\gamma_{0}}c_{1}e_{\gamma_{1}}c_{2}\cdots c_{l}e_{\gamma_{l}}.$

Note that this mapping is a $\mathbb{Z}$-algebra homomorphism.

######  Theorem 4.3.

The image under $\varphi$ of a path from $\gamma$ to $\delta$ with label $u$
is $e_{\gamma}u$.

###### Proof.

This is clear if the path is of length $0$. Suppose it is true for each path
of length $l\geq 0$. Consider a path
$\gamma_{0}\xrightarrow{c_{1}}\gamma_{1}\xrightarrow{c_{2}}\cdots\xrightarrow{c_{l+1}}\gamma_{l+1}$.
Its image under $\varphi$ is by definition
$x=\varphi(p)e_{\gamma_{l}}c_{l+1}e_{\gamma_{l+1}}$, where $p$ is the path
(8). Thus $x=\varphi(p)e_{\gamma_{l}}c_{l+1}$ (by the second equality in Lemma
4.2) $=\varphi(p)c_{l+1}$ (since $\varphi(p)e_{\gamma_{l}}=\varphi(p)$ by
definition of $\varphi$ and the idempotence of $e_{\gamma_{l}}$)
$=e_{\gamma_{0}}c_{1}\cdots c_{l}c_{l+1}$ (by induction). ∎

######  Corollary 4.4.

Consider two paths in $Q(A)$ starting from the same vertex $\gamma$, with
labels $u,v$. If $\gamma u\equiv_{styl}\gamma v$, then these paths have the
same image under $\varphi$.

###### Proof.

The images of these paths are $e_{\gamma}u$ and $e_{\gamma}v$, respectively.
These elements are by (6) equal to $e_{\gamma}\gamma u$ and $e_{\gamma}\gamma
v$. Thus, the lemma follows. ∎

###  4.4. Extended quiver

The extended quiver $Q^{\prime}(A)$ has the same set of vertices as $Q(A)$,
has all edges of $Q(A)$, together with new edges, which are loops: for each
column $\gamma$ and each $c\in\gamma$, we have in $Q^{\prime}(A)$ the edge

$\gamma\xrightarrow{c}\gamma.$

It is clearly a deterministic automaton. Note that if $c\in A$ and
$\gamma\in\Gamma(A)$, there is an edge labelled $c$ starting from $\gamma$ in
$Q^{\prime}(A)$ if and only if $c\geq min(\gamma)$. Moreover, if for
$\gamma,\delta\in\Gamma(A),w\in A^{*}$, there is a path
$\gamma\xrightarrow{w}\delta$ in $Q^{\prime}(A)$, then $\delta=\gamma\cdot w$.

######  Proposition 4.5.

Let $x\in Styl(A)$ and denote by $\gamma w$ the column-reading word of the
$N$-tableau $N(x)$ of $x$, with $\gamma$ being the first column of $N(x)$.
Then there is a unique path in the extended quiver, starting from $\gamma$,
with label $w$.

Before proving the proposition, we prove a useful lemma, showing that the
involution $\theta$ defined in Section 2.6 conjugates the left and right
actions.

######  Lemma 4.6.

Let $w\in A^{*}$ and $\gamma\in\Gamma(A)$. Then

$\gamma\cdot w=\theta(\theta(w)\cdot\theta(\gamma)).$

###### Proof.

For $w\in A$, the formula follows from the definitions of the left and right
actions on columns. To conclude, it is enough to prove that if the formula
holds for $u,v\in A^{*}$, then also for $w=uv$. We have $\gamma\cdot
w=\gamma\cdot(uv)=(\gamma\cdot u)\cdot
v=\theta(\theta(v)\cdot\theta(\gamma\cdot
u))=\theta(\theta(v)\cdot(\theta(u)\cdot\theta(\gamma))=\theta((\theta(v)\theta(u))\cdot\theta(\gamma))=\theta(\theta(uv)\cdot\theta(\gamma))=\theta(\theta(w)\cdot\theta(\gamma)).$
∎

###### Proof of Proposition 4.5.

Uniqueness follows from the deterministic property of $Q^{\prime}(A)$ viewed
as an automaton.

To prove the existence of this path, it is enough, by the definition of the
right action and of the extended quiver, to show that the height of
$\gamma\cdot p$ is equal to the height $k$ of $\gamma$, for each prefix $p$ of
$w$.

Since $\gamma w$ is the column-reading word of $N(x)$, it follows from (1)
that the $P$-tableau of $\gamma w$ is equal to $N(x)$. Thus, by Schensted’s
theorem, the height $k$ of $N(x)$ is equal to the length of the longest
strictly decreasing subsequence of $\gamma w$. Now, the length of the longest
strictly decreasing subsequence of $\theta(\gamma w)$ is $k$, too. Hence, the
height of the $P$-tableau of $\theta(\gamma w)$ is $k$; by the definition of
left action, the first column of this tableau is $\theta(\gamma
w)\cdot\emptyset$, and this column is equal to
$(\theta(w)\theta(\gamma))\cdot\emptyset=\theta(w)\cdot(\theta(\gamma)\cdot\emptyset)=\theta(w)\cdot\theta(\gamma)$.
Therefore, applying $\theta$ and using Lemma 4.6, we see that $\gamma\cdot w$
is of height $k$.

Since the (left and right) action on columns never decreases the height, it
follows that for each prefix $p$ of $w$, the height of $\gamma\cdot p$ is
equal to $k$. ∎

Lemma 4.6 has the following corollary.

######  Corollary 4.7.

Let $w$ be a word and $\gamma$ be a column. Then $\gamma
w\equiv_{styl}u(\gamma\cdot w)$ for some word $u$.

###### Proof.

We know that $w\cdot\gamma$ is the first column of $P(w\gamma)$. It follows by
column reading and Schensted’s theorem that
$w\gamma\equiv_{plax}(w\cdot\gamma)u$ for some word $u$. Applying $\theta$ and
using Lemma 4.6, we find that for each word $w$ and each column $\gamma$,
$\gamma w\equiv_{plax}u(\gamma\cdot w)$ for some word $u$; therefore $\gamma
w\equiv_{styl}u(\gamma\cdot w)$. ∎

Each path

(9) $\gamma\xrightarrow{w}\gamma\cdot w$

in the extended quiver $Q^{\prime}(A)$, starting from vertex $\gamma$ and with
label $w$, defines a path

(10) $\gamma\xrightarrow{w^{\prime}}\gamma\cdot w$

in the quiver $Q(A)$, by removing the loops. Precisely, we define the label
$w^{\prime}$ of the associated path in $Q(A)$ recursively as follows: if $w$
is empty, $w^{\prime}=w$; otherwise $w=uc$, $u\in A^{*},c\in A$, $u^{\prime}$
is constructed by induction, and then:

  * –

first case: $w^{\prime}=u^{\prime}$ if $\gamma\cdot u=(\gamma\cdot u)\cdot c$
(equivalently $c\in\gamma\cdot u$);

  * –

second case: $w^{\prime}=u^{\prime}c$ otherwise.

We call this construction loops removal.

######  Lemma 4.8.

With these notations, $\gamma\cdot w^{\prime}=\gamma\cdot w$.

###### Proof.

We follow the construction. If $w$ is empty, then $w^{\prime}$ is empty, and
the equality is evident. Suppose now that $w=uc$. In the first case,
$\gamma\cdot w^{\prime}=\gamma\cdot u^{\prime}=\gamma\cdot u$ (by induction)
$=\gamma\cdot(uc)=\gamma\cdot w$. In the second case, $\gamma\cdot
w^{\prime}=\gamma\cdot(u^{\prime}c)=(\gamma\cdot u^{\prime})\cdot
c=(\gamma\cdot u)\cdot c$ (by induction) $=\gamma\cdot(uc)=\gamma\cdot w$. ∎

######  Lemma 4.9.

With these notations, $\gamma w^{\prime}\equiv_{styl}\gamma w$.

###### Proof.

1\. Let $\delta\xrightarrow{c}\delta\cdot c$ be a an edge in the extended
quiver $Q^{\prime}(A)$. Then $c\geq\min(\delta)$. Next, $\delta
c\equiv_{styl}b(\delta\cdot c)$, with $b\in A$: this equality holds indeed
plactically, as a particular case of the presentation by columns of the
plactic monoid due to [BCCL15, CGM15], after applying $\theta$ and Lemma 4.6
(see also [AR22] Proposition 12.3 (v)).

Suppose that moreover $c\in\delta$, equivalently $\delta\cdot c=\delta$. Then
$\delta=\delta_{1}c\delta_{2}$ with each letter in $\delta_{2}$ smaller than
$c$. Then $\delta_{2}c\equiv_{styl}\delta_{2}$, by the dual form of Lemma 2.2
(i), from which follows $\delta c\equiv_{styl}\delta$.

2\. We prove the lemma by following the recursive construction of
$w^{\prime}$. If $w$ is empty, it is evident. Suppose now that $w=uc$ and
assume by induction that $\gamma u\equiv_{styl}\gamma u^{\prime}$, where
$u^{\prime}$ is obtained from $u$ by loops removal. By Corollary 4.7, we have
$\gamma u\equiv_{styl}v(\gamma\cdot u)$ for some word $v$. By 1 and 2, we have
$(\gamma\cdot u)c\equiv_{styl}b(\gamma\cdot w)$, with $b=1$ if $\gamma\cdot
u=\gamma\cdot(uc)$, and $b\in A$ otherwise.

In the first case, we have $\gamma\cdot u=\gamma\cdot(uc)=\gamma\cdot w$,
$w^{\prime}=u^{\prime}$, $b=1$. Then $\gamma w=\gamma
uc\equiv_{styl}v(\gamma\cdot u)c\equiv_{styl}v(\gamma\cdot w)$, and $\gamma
w^{\prime}=\gamma u^{\prime}\equiv_{styl}\gamma u\equiv_{styl}v(\gamma\cdot
u)=v(\gamma\cdot w)$.

In the second case, we have $\gamma\cdot w=\gamma\cdot(uc)\neq\gamma\cdot u$,
$w^{\prime}=u^{\prime}c$, $b\in A$. Then $\gamma w=\gamma
uc\equiv_{styl}v(\gamma\cdot u)c\equiv_{styl}vb(\gamma\cdot w)$, and $\gamma
w^{\prime}=\gamma u^{\prime}c\equiv_{styl}\gamma uc\equiv_{styl}v(\gamma\cdot
u)c\equiv_{styl}vb(\gamma\cdot w)$. ∎

######  Corollary 4.10.

The image under $\varphi$ of the path (10) in $Q(A)$, obtained from the path
(9) in $Q^{\prime}(A)$ by loops removal, is equal to $e_{\gamma}w$.

###### Proof.

Suppose that $w$ is the label of a path in $Q^{\prime}(A)$ starting form
$\gamma$; define $w^{\prime}$ by loops removal. The image under $\varphi$ of
our path of $Q(A)$ is by Theorem 4.3 equal to $y=e_{\gamma}w^{\prime}$. By
(6), we have $y=e_{\gamma}\gamma w^{\prime}$. Hence by Lemma 4.9, the
corollary follows. ∎

###  4.5. The surjectivity of the quiver map

Let $x\in Styl(A)$ and denote by $\eta(x)w_{x}$ the column-reading word of the
$N$-tableau $N(x)$ of $x$, with $\eta(x)$ being the first column of $N(x)$.
Recall from Proposition 4.5, that we have constructed a path, in the extended
quiver $Q^{\prime}(A)$, starting form $\eta(x)$ and with label $w_{x}$. From
this path in $Q^{\prime}(A)$, we obtain by loops removal in Section 4.4, a
path in $Q(A)$ starting form $\eta(x)$ and with label $w^{\prime}_{x}$; we
call such a path an $N$-path.

######  Proposition 4.11.

The set $\\{e_{\eta(x)}w_{x}:x\in Styl(A)\\}$ is a basis of
$\mathbb{Z}Styl(A)$.

###### Proof.

Recall from [AR22] that $Styl(A)$ is a $\mathscr{J}$-trivial monoid, and that
it has therefore the $\mathscr{J}$-order $\leq_{\mathscr{J}}$. One has
$x\leq_{\mathscr{J}}y$ if and only if for some $u,v$, $x=uyv$ (all these
elements are in $Styl(A)$).

Let $x\in Styl(A)$, with $\eta(x)=\gamma$; then by (4), $x=\gamma w_{x}$ in
$\mathbb{Z}Styl(A)$, and by (5),

$e_{\eta(x)}w_{x}=\prod^{\nearrow}_{a\notin\gamma}(1-a)x.$

Let $a\notin\gamma$; then $ax\leq_{\mathscr{J}}x$; moreover by Proposition
2.1, and since $\gamma$ is the first column of $N(x)$, $ax\neq x$ and
therefore $ax<_{\mathscr{J}}x$. It follows from the displayed formula that
$e_{\eta(x)}w_{x}$ is equal to $x$ plus a linear combination of elements
strictly smaller than $x$ in the $\mathscr{J}$-order. Hence, by triangularity,
the elements $e_{\eta(x)}w_{x}$, $x\in Styl(A)$, form a basis of
$\mathbb{Z}Styl(A)$. ∎

######  Corollary 4.12.

The quiver map $\varphi$ is surjective.

###### Proof.

The element $e_{\eta(x)}w_{x}$ is the image under $\varphi$ of the path
constructed in Corollary 4.10. Hence, by Proposition 4.11, $\varphi$ is
surjective. ∎

######  Corollary 4.13.

The $N$-paths are linearly independent modulo $\ker(\varphi)$.

###  4.6. The kernel of the quiver map

The following result shows that $\ker(\varphi)$ is completely described by
Corollary 4.4.

######  Proposition 4.14.

The kernel of $\varphi$ is spanned by the elements which are differences of
two paths in $Q(A)$ starting from the same vertex $\gamma$ and having labels
$u,v$ satisfying $\gamma u\equiv_{styl}\gamma v$.

###### Proof.

Denote by $H$ the subspace described in the statement. We know by Corollary
4.4 that $H$ is a subspace of $\ker(\varphi)$.

Consider a path starting from $\gamma$ and with label $u$. Let $x=\gamma u$.

1\. We show that the first column of $N(x)$ is $\gamma$.

If $a\in\gamma$, by Lemma 2.2 (i), we have $a\gamma=\gamma$ in $Styl(A)$;
hence, $a$ is in the first column of $N(x)$ (by Proposition 2.1), and this
column therefore contains $\gamma$.

Moreover, by definition of the quiver and of paths, the height of $\gamma\cdot
u$ is the same as the height $h$ of $\gamma$; thus the height of
$\theta(\gamma\cdot u)$ is $h$, and so is that of
$\theta(u)\cdot\theta(\gamma)$ by Lemma 4.6; but this column is the first
column of $N(\theta(u)\theta(\gamma))=N(\theta(\gamma u))=N(\theta(x))$. By
Theorem 9.1 in [AR22], $N(x)$ and $N(\theta(x))$ have the same height; the
height of $N(x)$ is therefore $h$. It follows that its first column is
$\gamma$.

2\. Consider now the path (9) of $Q^{\prime}(A)$ constructed in Proposition
4.5, and the associated path (10) in $Q(A)$, obtained by removing the loops:
it starts at $\gamma$ and has $w^{\prime}$ as label.

We know that $\gamma u=x\equiv_{styl}\gamma w$, by (4) since the latter word
is the column-reading word of $N(x)$. Hence by Lemma 4.9, $\gamma
u\equiv_{styl}\gamma w^{\prime}$ and therefore the two paths of $Q(A)$
starting at $\gamma$ and with labels $u$ and $w^{\prime}$ have the same image
under $\varphi$, by Corollary 4.4.

It follows that each element in the quiver algebra is congruent modulo $H$ to
a linear combination of $N$-paths. Since by Corollary 4.13 these $N$-paths are
linearly independant modulo $\ker(\varphi)$, it follows that
$\ker(\varphi)\subset H$. ∎

###  4.7. The quiver of the stylic algebra

Now, let $\mathbb{K}$ be a field of characteristic $0$. We apply a theorem of
Auslander, Reiten and Smalø [ARS97], in order to prove that $Q(A)$ is the
quiver of $\mathbb{K}Styl(A)$.

######  Theorem 4.15.

The quiver of the stylic algebra over $\mathbb{K}$ is $Q(A)$.

We first prove the following useful lemma.

######  Lemma 4.16.

Let $\gamma$ be a column, and $u,v\in A^{*}$. If $\gamma u\equiv_{styl}\gamma
v$, then $\gamma\cdot u=\gamma\cdot v$.

###### Proof.

By Lemma 4.6, it is enough to prove the dual statement: if
$u\gamma\equiv_{styl}v\gamma$, then $u\cdot\gamma=v\cdot\gamma$. The
hypothesis implies that $(u\gamma)\cdot\emptyset=(v\gamma)\cdot\emptyset$.
This implies $u\cdot(\gamma\cdot\emptyset)=v\cdot(\gamma\cdot\emptyset)$, thus
$u\cdot\gamma=v\cdot\gamma$. ∎

###### Proof of Theorem 4.15.

According to a theorem in [ARS97], in the formulation of [DHST11, Theorem
3.3.4], it is enough to show that the ideal $\ker(\varphi)$ is admissible.
This means that $F^{m}\subset\ker(\varphi)\subset F^{2}$, where $F$ is the
ideal in $\mathbb{K}Q(A)$ generated by the arrows of $Q(A)$.

The first inclusion is clear, since the quiver has no closed path, so that for
$m$ large enough, $F^{m}=0$.

We know that $\ker(\varphi)$ is spanned by the elements, differences of two
paths, described in Proposition 4.14, whose notations we use now. In
particular, $\gamma u\equiv_{styl}\gamma v$. Thus it is enough to show that
$u,v$ are both of length at least 2. We may assume that the element is
nonzero.

Observation 1: the alphabet of $\gamma u$ and $\gamma v$ must be equal, since
these words are stylically congruent.

Observation 2: assuming that the alphabet is $1,2,3,\ldots$, call weight of a
column the sum of its elements. Then by definition of frank action, the weight
of $\gamma\cdot a$ is larger that the weight of $\gamma$, and so the weight of
the vertices strictly increases along a path in $Q(A)$.

Suppose by contradiction that $u$ is of length $0$ or $1$, and we begin by
length 0. If $v$ also is of length 0, the element is 0, which was excluded. If
$v$ is of positive length then, since the action is frank, the alphabet of
$\gamma v$ is strictly larger than that of $\gamma$; hence the alphabets of
$\gamma u=\gamma$ and of $\gamma v$ differ, so that by Observation 1, we
cannot have $\gamma u\equiv_{styl}\gamma v$.

Thus we may assume that $u=b$ is of length 1. Then $v$ cannot be of length 0,
by the same argument just given. If $v$ is of length 1, then by Observation 1,
and since the two actions are frank (so that $u,v\notin\gamma$), we must have
$u=v$, and the element is 0, which was excluded. Thus $v$ is of length at
least 2: $v=cv^{\prime}$, $v^{\prime}$ nonempty; then by Observation 1, $c$
appears in $\gamma b$, but not in $\gamma$, since the action $\gamma\cdot c$
is frank, hence $c=b$; but then by Observation 2, the weight of $\gamma\cdot
v$ is larger than that of $\gamma\cdot b$, and we cannot have the equality
$\gamma\cdot u=\gamma\cdot v$, contradicting $\gamma u\equiv_{styl}\gamma v$
by Lemma 4.16. ∎

###  4.8. Cartan invariants and Indecomposable Projective Modules

The _Cartan invariants_ of a finite dimensional $\mathbb{K}$-algebra $\Lambda$
are the numbers $\dim_{\mathbb{K}}(e_{i}\Lambda e_{j})$, where
$\\{e_{1},\ldots,e_{n}\\}$ is a complete system of primitive orthogonal
idempotents of $\Lambda$. They do not depend on the choice of the complete
system.

In the case of the stylic monoid, we are therefore interested in computing the
dimension of the subspaces $e_{\gamma}\mathbb{K}Styl(A)e_{\gamma^{\prime}}$
for $\gamma,\gamma^{\prime}\in\Gamma(A)$.

######  Proposition 4.17.

For $\gamma,\gamma^{\prime}\in\Gamma(A)$,

$\dim\Big{(}e_{\gamma}\mathbb{K}Styl(A)e_{\gamma^{\prime}}\Big{)}=\Big{|}\big{\\{}x\in
Styl(A):\eta(x)=\gamma\text{~{}and~{}}\theta(\eta(\theta(x))=\gamma^{\prime}\big{\\}}\Big{|}.$

###### Proof.

By Proposition 4.11, we have that $\\{e_{\eta(x)}w_{x}:x\in Styl(A)\\}$ is a
basis of $\mathbb{Z}Styl(A)$. Moreover, each $e_{\eta(x)}w_{x}$ is the image
under $\varphi$ of a path in $Q^{\prime}(A)$ that starts at $\eta(x)$, is
labelled $w_{x}$, and ends at $\theta(\eta(\theta(x)))$; see §4.5. Thus,

$e_{\eta(x)}w_{x}=e_{\eta(x)}w_{x}e_{\theta(\eta(\theta(x)))}.$

It follows that $\\{e_{\eta(x)}w_{x}e_{\theta(\eta(\theta(x)))}:x\in
Styl(A)\\}$ is a basis of $\mathbb{Z}Styl(A)$, and that

$\\{e_{\eta(x)}w_{x}e_{\theta(\eta(\theta(x)))}:x\in Styl(A)\text{~{}with
$\eta(x)=\gamma$ and $\theta(\eta(\theta(x)))=\gamma^{\prime}$}\\}$

is a basis of $e_{\gamma}\mathbb{Z}Styl(A)e_{\gamma^{\prime}}$. ∎

We remark that an alternative proof of Proposition 4.17 can be obtained by
appealing to [DHST11, Theorem 3.20], which gives a formula for the Cartan
invariants for any $\mathscr{J}$-trivial monoid $M$. Applied to $Styl(A)$, the
formula says that the Cartan invariants are given by

$\\{x\in
Styl(A):\mathrm{lfix}(x)=\gamma\text{~{}and~{}}\mathrm{rfix}(x)=\gamma^{\prime}\\},$

where

  * •

$\mathrm{lfix}(x)=\min_{\leq_{\mathscr{J}}}\big{\\{}e\in
Styl(A):e^{2}=e\text{~{}and~{}}ex=x\big{\\}}$

  * •

$\mathrm{rfix}(x)=\min_{\leq_{\mathscr{J}}}\big{\\{}e\in
Styl(A):e^{2}=e\text{~{}and~{}}xe=x\big{\\}}$

Proposition 4.17 then follows by observing that $\mathrm{lfix}(x)=\eta(x)$ and
$\mathrm{rfix}(x)=\theta(\eta(\theta(x)))$ for all $x\in Styl(A)$.

Finally, using a similar argument to the proof of Proposition 4.17, one
obtains bases for the right and left indecomposable projective
$Styl(A)$-modules.

######  Proposition 4.18.

For $\gamma\in\Gamma(A)$,

  1. (1)

$\\{e_{\eta(x)}w_{x}:x\in Styl(A)\text{~{}with~{}}\eta(x)=\gamma\\}$ is basis
of $e_{\gamma}\mathbb{K}Styl(A)$, and

  2. (2)

$\\{e_{\eta(x)}w_{x}:x\in
Styl(A)\text{~{}with~{}}\theta(\eta(\theta(x)))=\gamma\\}$ is basis of
$\mathbb{K}Styl(A)e_{\gamma}$.

## References

  * [AR22] A. Abram and C. Reutenauer, _The stylic monoid_ , Semigroup Forum 105 (2022), no. 1, 1–45. MR 4466957
  * [ARS97] Maurice Auslander, Idun Reiten, and Sverre O. Smalø, _Representation theory of Artin algebras_ , Cambridge Studies in Advanced Mathematics, vol. 36, Cambridge University Press, Cambridge, 1997, Corrected reprint of the 1995 original. MR 1476671
  * [ASS06] Ibrahim Assem, Daniel Simson, and Andrzej Skowroński, _Elements of the representation theory of associative algebras. Vol. 1_ , London Mathematical Society Student Texts, vol. 65, Cambridge University Press, Cambridge, 2006, Techniques of representation theory. MR 2197389
  * [ASST15] Arvind Ayyer, Anne Schilling, Benjamin Steinberg, and Nicolas M. Thiéry, _Markov chains, $\mathscr{R}$-trivial monoids and representation theory_, Internat. J. Algebra Comput. 25 (2015), no. 1-2, 169–231. MR 3325881
  * [BBBS11] Chris Berg, Nantel Bergeron, Sandeep Bhargava, and Franco Saliola, _Primitive orthogonal idempotents for $R$-trivial monoids_, J. Algebra 348 (2011), 446–461. MR 2852251
  * [BBD99] Louis J. Billera, Kenneth S. Brown, and Persi Diaconis, _Random walks and plane arrangements in three dimensions_ , Amer. Math. Monthly 106 (1999), no. 6, 502–524. MR 1699244
  * [BCCL15] L. A. Bokut, Yuqun Chen, Weiping Chen, and Jing Li, _New approaches to plactic monoid via Gröbner-Shirshov bases_ , J. Algebra 423 (2015), 301–317. MR 3283719
  * [BD98] Kenneth S. Brown and Persi Diaconis, _Random walks and hyperplane arrangements_ , Ann. Probab. 26 (1998), no. 4, 1813–1854. MR 1675083
  * [BHR99] Pat Bidigare, Phil Hanlon, and Dan Rockmore, _A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements_ , Duke Math. J. 99 (1999), no. 1, 135–174. MR 1700744
  * [Bro00] Kenneth S. Brown, _Semigroups, rings, and Markov chains_ , J. Theoret. Probab. 13 (2000), no. 3, 871–938. MR 1785534
  * [Bro04] by same author, _Semigroup and ring theoretical methods in probability_ , Representations of finite dimensional algebras and related topics in Lie theory and geometry, Fields Inst. Commun., vol. 40, Amer. Math. Soc., Providence, RI, 2004, pp. 3–26. MR 2057147
  * [CGM15] Alan J. Cain, Robert D. Gray, and António Malheiro, _Finite Gröbner-Shirshov bases for plactic algebras and biautomatic structures for plactic monoids_ , J. Algebra 423 (2015), 37–53. MR 3283708
  * [Den11] Tom Denton, _A combinatorial formula for orthogonal idempotents in the 0-Hecke algebra of the symmetric group_ , Electron. J. Combin. 18 (2011), no. 1, Paper 28, 20. MR 2776804
  * [DHST11] Tom Denton, Florent Hivert, Anne Schilling, and Nicolas M. Thiéry, _On the representation theory of finite $\mathscr{J}$-trivial monoids_, Sém. Lothar. Combin. 64 (2010/11), Art. B64d, 44. MR 2800981
  * [GM11] Olexandr Ganyushkin and Volodymyr Mazorchuk, _On Kiselman quotients of 0-Hecke monoids_ , Int. Electron. J. Algebra 10 (2011), 174–191. MR 2821178
  * [GM14] Anna-Louise Grensing and Volodymyr Mazorchuk, _Categorification of the Catalan monoid_ , Semigroup Forum 89 (2014), no. 1, 155–168. MR 3249875
  * [HST13] Florent Hivert, Anne Schilling, and Nicolas Thiéry, _The biHecke monoid of a finite Coxeter group and its representations_ , Algebra Number Theory 7 (2013), no. 3, 595–671. MR 3095222
  * [Lot02] M. Lothaire, _Algebraic combinatorics on words_ , Encyclopedia of Mathematics and its Applications, vol. 90, Cambridge University Press, Cambridge, 2002, A collective work by Jean Berstel, Dominique Perrin, Patrice Seebold, Julien Cassaigne, Aldo De Luca, Steffano Varricchio, Alain Lascoux, Bernard Leclerc, Jean-Yves Thibon, Veronique Bruyere, Christiane Frougny, Filippo Mignosi, Antonio Restivo, Christophe Reutenauer, Dominique Foata, Guo-Niu Han, Jacques Desarmenien, Volker Diekert, Tero Harju, Juhani Karhumaki and Wojciech Plandowski, With a preface by Berstel and Perrin. MR 1905123
  * [LS81] Alain Lascoux and Marcel-P. Schützenberger, _Le monoïde plaxique_ , Noncommutative structures in algebra and geometric combinatorics (Naples, 1978), Quad. “Ricerca Sci.”, vol. 109, CNR, Rome, 1981, pp. 129–156. MR 646486
  * [MS11] Stuart Margolis and Benjamin Steinberg, _The quiver of an algebra associated to the Mantaci-Reutenauer descent algebra and the homology of regular semigroups_ , Algebr. Represent. Theory 14 (2011), no. 1, 131–159. MR 2763297
  * [MS12a] by same author, _Quivers of monoids with basic algebras_ , Compos. Math. 148 (2012), no. 5, 1516–1560. MR 2982439
  * [MS12b] Volodymyr Mazorchuk and Benjamin Steinberg, _Double Catalan monoids_ , J. Algebraic Combin. 36 (2012), no. 3, 333–354. MR 2969066
  * [MS18] Stuart Margolis and Benjamin Steinberg, _Projective indecomposable modules and quivers for monoid algebras_ , Comm. Algebra 46 (2018), no. 12, 5116–5135. MR 3923746
  * [MSS15] Stuart Margolis, Franco Saliola, and Benjamin Steinberg, _Combinatorial topology and the global dimension of algebras arising in combinatorics_ , J. Eur. Math. Soc. (JEMS) 17 (2015), no. 12, 3037–3080. MR 3429159
  * [MSS21] Stuart Margolis, Franco V. Saliola, and Benjamin Steinberg, _Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry_ , Mem. Amer. Math. Soc. 274 (2021), no. 1345, xi+135. MR 4365944
  * [Sag01] Bruce E. Sagan, _The symmetric group_ , second ed., Graduate Texts in Mathematics, vol. 203, Springer-Verlag, New York, 2001, Representations, combinatorial algorithms, and symmetric functions. MR 1824028
  * [Sal07] Franco V. Saliola, _The quiver of the semigroup algebra of a left regular band_ , Internat. J. Algebra Comput. 17 (2007), no. 8, 1593–1610. MR 2378054
  * [Sal09] by same author, _The face semigroup algebra of a hyperplane arrangement_ , Canad. J. Math. 61 (2009), no. 4, 904–929. MR 2541389
  * [SCc08] The Sage-Combinat community, _Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics_ , 2008, http://combinat.sagemath.org.
  * [Sch77] M.-P. Schützenberger, _La correspondance de Robinson_ , Combinatoire et représentation du groupe symétrique (Actes Table Ronde CNRS, Univ. Louis-Pasteur Strasbourg, Strasbourg, 1976), Lecture Notes in Math., Vol. 579, Springer, Berlin, 1977, pp. 59–113. MR 0498826
  * [Ste16] Benjamin Steinberg, _Representation theory of finite monoids_ , Universitext, Springer, Cham, 2016. MR 3525092
  * [Ste20] Itamar Stein, _Representation theory of order-related monoids of partial functions as locally trivial category algebras_ , Algebr. Represent. Theory 23 (2020), no. 4, 1543–1567. MR 4125591
  * [The22] The Sage Developers, _SageMath, the Sage Mathematics Software System (Version 9.5)_ , 2022, https://www.sagemath.org.


# Multigrid Backprojection Super–Resolution
and Deep Filter Visualization

Pablo Navarrete Michelini, Hanwen Liu and Dan Zhu
BOE Technology Group Inc., Ltd.
Beijing, China

###### Abstract

We introduce a novel deep–learning architecture for image upscaling by large
factors (e.g. $4\times$, $8\times$) based on examples of pristine
high–resolution images. Our target is to reconstruct high–resolution images
from their downscale versions. The proposed system performs a multi–level
progressive upscaling, starting from small factors ($2\times$) and updating
for higher factors ($4\times$ and $8\times$). The system is recursive as it
repeats the same procedure at each level. It is also residual since we use the
network to update the outputs of a classic upscaler. The network residuals are
improved by Iterative Back–Projections (IBP) computed in the features of a
convolutional network. To work in multiple levels we extend the standard
back–projection algorithm using a recursion analogous to Multi–Grid algorithms
commonly used as solvers of large systems of linear equations. We finally show
how the network can be interpreted as a standard upsampling–and–filter
upscaler with a space–variant filter that adapts to the geometry. This
approach allows us to visualize how the network learns to upscale. Finally,
our system reaches state of the art quality for models with relatively few
number of parameters.

## Introduction

In this work, we focus on the problem of image upscaling using convolutional
networks. Upscaling signals by integer factors (e.g. $2\times$, $3\times$) is
understood in classical interpolation theory as two sequential processes:
upsample (insert zeros) and filter (?; ?). Standard upscaler algorithms, such
as Bicubic or Lanczos, find high–resolution images with a narrow frequency
content by using fixed low–pass filters. Similar to the classic upscaling
model, the image acquisition can be modeled as low-pass filtering a high
resolution image and then downsample the result (drop pixels). In test
scenarios often used in benchmarks we actually know the exact downscaling
model, e.g. Bicubic downscaler. The Iterative Back–Projection (IBP) algorithm
(?) is often used to enforce the downscaling model for a given upscaler and
get closer to the original image.

More advanced upscalers follow geometric principles to improve image quality.
For example, _edge–directed interpolation_ uses adaptive filters to improve
edge smoothness (?; ?), or _bandlet_ methods use both adaptive upsampling and
filtering (?). More recently, machine learning has been able to use examples
pairs of high and low resolution images to estimate the parameters of
upscaling systems (?). In some cases, the optimization approach of machine
learning hides the connection with classical interpolation theory, e.g. sparse
representation with dictionaries (?; ?). In other cases, the adaptive filter
approach is explicit, e.g. RAISR (?).

Upscaling using convolutional networks started with SRCNN (?; ?) motivated by
the success of deep–learning methods in image classification tasks (?) and
establishing a strong connection with sparse coding methods (?; ?). SRCNN has
later been improved, most notably by EDSR (?) and DBPN (?). Our system shares
the convolutional network approach but follows a different motivation. Namely,
we aim to reveal a strong connection between convolutional–networks and
classical image upscaling. By doing so, we can recover the classic
interpretation of upsampling and filter and visualize what is the network
doing pixel by pixel. Thus, we aim to prove that convolutional networks are a
natural and convenient choice for Super–Resolution (SR) tasks.

Our main contributions are:

  * •

We extend the IBP algorithm to a multi–level IBP.

  * •

We prove that our algorithm works as well as classic IBP, based on an
unrealistic model.

  * •

We introduce a new network architecture that overcomes the unrealistic model
and allows us to learn both upscaling and downscaling.

  * •

We introduce a novel algorithm to analyze the linear components of the
network.

  * •

We show how to interpret the network as a standard upscaler with adaptive
filters.

## Related Work

We consider the following two architectures as the most similar to our system:

  * •

Multi–Scale Laplacian Super–Resolution (MSLapSR) (?): Our system is inspired
by MSLapSR to progressively upscale images using a classic upscaler and
network updates, before back–projections that improve network updates in
lower–resolutions. Both MSLapSR and our systems include _analysis_ and
_synthesis_ networks to convert images to latent space and vice versa. Both
systems share parameters at each scale. Our system differs mostly in the use
of back–projections, that cannot be removed to recover MSLapSR because of the
particular structure of our _upscaler_ network module.

  * •

Deep Back–Projection Network (DBPN) (?): To the extent of our knowledge, this
is the first reference to use IBP in a network architecture. It is also the
state–of–art in terms of image quality, surpassing EDSR(?), former winner of
NTIRE 2017 SR Challenge (?). Their approach to use back–projections is
different than ours because: first, their system is not multi–scale; and
second, they iterate down and up projections. Our multi–scale architecture
requires less number of parameters, because we reuse modules at every scale,
and it is more flexible, because many upscaling factors can be achieved with
the same modules. Also, our system is built upon an algorithm that is proven
to converge, whereas, to the extent of our knowledge, mixing up and down
projections has no convergence guarantees.

$\boldsymbol{MGBP}(X,\mu,L)$: |  $\boldsymbol{BP^{\mu}_{k}}(u,Y_{1},\ldots,Y_{k-1})$:
---|---
0: Input image $X$.  0: Integers $\mu\geqslant 0$ and $L\geqslant 1$.  0: Images $Y_{k}$, $k=2,\ldots,L$.  1: $Y_{1}=X$ 2: for $k=2,\ldots,L$ do 3: $u=(Y_{k-1}\uparrow s)*p$ 4: $Y_{k}=BP^{\mu}_{k}\left(u,Y_{1},\ldots,Y_{k-1}\right)$ 5: end for |  0: Image $u$, level index $k$, number of steps $\mu$.  0: Images $Y_{1},\ldots,Y_{k-1}$ (only for $k>1$).  0: Updated image $u$ 1: if $k>1$ then 2: for $step=1,\ldots,\mu$ do 3: $d=BP^{\mu}_{k-1}\left({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(u*g)\downarrow s},Y_{1},\ldots,Y_{k-2}\right)$ 4: $u=u+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(Y_{k-1}-d)\uparrow s*p}$ 5: end for 6: end if
Algorithm 1 Multi–Grid Back–Projection (MGBP) Figure 1:  Multigrid
Back–Projection (MGBP) system architecture. Lines indicate a number of image
channels moving to different processing blocks, and line colors indicate the
number of channels. Blue represents $3$ channels for RGB images, and black
represents the number of features managed by convolutional networks (latent
space). At level $k$ the current upscaled image is indicated as $I_{k}$ and
residuals in latent space are indicated as $R_{k}$. We use _Analysis_ and
_Synthesis_ modules to transfer images into latent space and vice versa. In
_Initial Steps_ we obtain the first pair of output image $I_{0}$ and residual
$R_{0}$, from the input image. Then, the main diagram shows how to obtain the
pair $I_{L}$ and $R_{L}$ from the previous pair $I_{L−1}$ and $R_{L-1}$. In
red we show the Back–Projection module, which repeats mu back–projection steps
recursively.  Figure 2: Multi–Grid Back–Projection (MGBP) recursion unfold
from Figure 1 for different values of $\mu$, and three levels to output
$2\times$, $4\times$ and $8\times$ upscale images. Our system uses a recursion
analogous to the Full–Multigrid algorithm to solve linear equations and leads
to the well known workflows V–cycle for $\mu=1$ and W–cycles for $\mu=2$ (?).
After every upscaling step, the MGBP recursion sends the output down to every
lower–resolution level in order to validate the downscaling model. The
corrections are back-projected to higher resolutions.

Our contributions add to the following lines of research:

  * •

Recursive Architectures: Extensive work has been done on recursive CNN
architectures inspired on iterative procedures. Our system belongs to this
line of work since we propose an architecture based on IBP and multi–grid
iterations. Of particular interest is the research along this line related to
SR and enhancements problems. In (?), for example, a _half quadratic
splitting_ iteration with a CNN denoiser prior is proposed for image
denoising, deblurring and SR. Most recently, (?) take a similar approach for
image demosaicking. Next, (?) propose to learn an optimizer for image
deconvolution by recurrently incorporating CNNs into a gradient descent
scheme, which could be complementary to our approach. In (?), an energy
minimization iteration is performed using a CNN model for image deconvolution,
which is close to the SR problem. Finally, the work of (?) follows a similar
motivation than ours by proposing a framework to incorporate knowledge of the
image formation into CNNs, applied to denoising, deblurring and compressed
sensing.

All these approaches differ to ours in the fact that our recursion iterates
back and forth between different resolutions. In numerical methods, such
iterations have been used by two types of linear equation solvers:
_multi–grid_ and _domain decomposition_ methods (?; ?). We follow the
multi–grid approach, that can use inductive arguments to study convergence,
and leads to specific processing workflows to move intermediate results
between scales (see for example the W–cycle in Figure 2). Systems like
MS–DenseNet (?) also move back and forth between scales with more simplified
workflows but they were not designed based on classical methods. The
connection to classical methods gives us a justification of these workflows
that, otherwise, would be arbitrary (e.g. why traversing scales with V or W
workflows in Figure 2)? which workflow is better?) We will show, for example,
how different numbers of back–projections (related to depth) make outputs
sharper, same as in IBP. Our main contribution here is to devise a new
algorithm that introduces the multi–grid recursion into IBP. It is a different
algorithm than IBP, that we prove to converge at the same rate, and then
extend to a network architecture. Finally, this effort pays back since our
recursion works well in experiments, with no other method reaching the same
quality with the same number of parameters.

  * •

Network Visualization: A major direction of research in deep–learning is how
to visualize the inner processing of a given architecture (?). Among these, a
line of research on _feature visualization_ studies what does a network detect
(?). Feature visualization can give example inputs that cause desired
behaviors, separating image areas causing behavior from those that only relate
to the causes. Another line of work on _attribution_ studies how does a
network assembles these individual pieces to arrive at later decisions, or why
these decisions were made (?). Our visualization technique belongs to the
latter because we can show how the input pixels are assembled into a
particular output pixel. We target the SR problem where there is extensive
knowledge of non–adaptive filters (e.g. linear, bicubic, etc.) built upon
signal processing theory. The main novelty of our technique is that it
provides an alternative system to replace the network for a given input. The
new system generates the exact same outputs of the network from the same input
images but, unlike the network, it is fully interpretable in the sense that we
know what to expect from its parameters.

## Multigrid Backprojections

A simple and common model for the downscaling process is

$X=(Y*g)\downarrow s\;,$ (1)

where $Y$ is the high–resolution source, $X$ is the low–resolution result, $g$
is a blurring kernel and $\downarrow s$ is a downsampling by factor $s$.

Model (1) gives additional information about the unknown high–resolution image
and narrows down the search space from all possible images to images that
downscaled with model (1) recover the low–resolution input image. This is the
motivation behind the classic IBP algorithm (?). Given model (1) and an
upscaled image $Y$, the IBP algorithm iterates:

$\displaystyle e(Y_{k})$ $\displaystyle=$ $\displaystyle X-(Y_{k}*g)\downarrow
s$ (2) $\displaystyle Y_{k+1}$ $\displaystyle=$ $\displaystyle
Y_{k}+e(Y_{k})\uparrow s*p\;.$ (3)

Here, $e(Y_{k})$ is the mismatch error at low–resolution, $g$ and $p$ are
blurring and upscaling filters, respectively. The iteration is proven to
converge, to enforce model (1) at exponential rate (?).

To make IBP work for multiple scales we change model (1) to:

$X=(\cdots((Y\underbrace{*g)\downarrow s*g)\downarrow s\cdots*g)\downarrow
s}_{L\;\text{times}}\;.$ (4)

This is not a common downscaling procedure in practice and might be the reason
why multi–scale IBP has not been considered yet. We will later replace the
downscaling by a network so that model (4) becomes flexible and is able to
learn a direct downscaling or even more complex models.

Upscaling images with IBP is a two–step process: first, upscale an image; and
second, improve it with IBP. This is reminiscent of the way a Full–Multigrid
algorithm solves linear equations (?). This is: first, find an approximate
solution; and second, improve it by solving an equation for the approximation
error. Both IBP and Multigrid iterate between different scales, but IBP only
uses two levels whereas Multigrid recursively move to coarser grids. We use
the same strategy as in Multigrid to define a so–called _Multi–Grid
Back–Projection_ algorithm as shown in Algorithm 2. Here, back–projections
recursively return to the lowest–resolution enforcing the downscaling model at
each scale.

For $L=2$ the MGBP algorithm and model (4) are equivalent to the original IBP
(?) and model (1), and thus converges at exponential rate. In section A of the
supplementary material we prove convergence for $L>2$. Basically, the
algorithm inherits the exponential rate convergence from the two–level case
through the recursion in Algorithm 2.

## Network Architecture

We convert the Multi–Grid Back–Projection algorithm into a network structure
as follows:

  * •

Step 1: Use a classic method to upscale a low resolution image.

  * •

Step 2: Transfer the upscale image $I$ into latent space using a network
$\text{Analysis}(I)$.

  * •

Step 3: In latent space we apply the recurrence in Algorithm 2 by changing:

    * –

${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(u*g)\downarrow
s}$ into a network
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\text{Downscale}(u)}$.

    * –

${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}(Y_{k-1}-d)\uparrow
s*p}$ into a network
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\text{Upscale}(\left[Y_{k-1},d\right])}$.
Where $\left[Y_{k-1},d\right]$ is the concatenation of features and replaces
the subtraction. Thus, the _Upscaler_ network receives double the number of
features in the input compared to the output.

Figure 1 shows the definition of our network architecture. The unfolded
recursion is shown in Figure 2 for three different values of $\mu$.

## Deep Filter Visualization

Deep Learning architectures are highly non–linear, although much of their
internal structure is linear (e.g. convolutions). We want to study the overall
effect of the linear structure of the network. The general procedure is shown
in Figure 3 and is as follows:

  * •

An input image $X$ passes through all layers of the network, and outputs an
image $Y$.

  * •

At each non-linear layer we record how much did the input change (layer gain).

  * •

We replace (freeze) all non–linearities by the fix gain previously recorded.
The overall system becomes linear, such that $Y=FX+R$.

  * •

We obtain the _effective residual_ $R$ with an input $X=0$ in the activation
frozen system.

  * •

We obtain the _effective filter_ for a particular input pixel by using a
$\delta$ input centered at the pixel location, and subtract the residual $R$
from the output. In linear system terminology we are computing the _impulse
response_ of the system (?).

We can obtain explicit formulas for $F$ and $R$ if we consider a model of
convolutional network as a sequence of linear and nonlinear layers:

$z_{n}=W_{n}x_{n-1}+b_{n}\quad\quad\text{and}\quad\quad
x_{n}=\sigma\left(z_{n}\right)\;,$ (5)

where $x_{n}$ and $z_{n}$ are vectorized features at layer $n$, after and
before activations, respectively. The parameters of the network are the biases
$b_{n}$ and the sparse matrices $W_{n}$ representing the convolutional
operators (also applies for strided and transposed convolutions). For a given
input image $X$, the input of the model is $x_{0}=\text{vec}(X)$ (vectorized
image). The output image $Y$, after $n$ convolutional layers, is
$\text{vec}^{-1}(x_{n})$.

Table 1: Quantitative evaluation of different SR methods. In  red color we
show the best result, in  blue the top–$2$ and  brown the top–$3$ results for
each column and scale. Methods are ordered by increasing number of parameters.

Algorithm | $s$ | $par$ | Set14 | BSDS100 | Urban100 | Manga109
---|---|---|---|---|---|---
|  | $[M]$ | PSNR | SSIM | PSNR | SSIM | PSNR | SSIM | PSNR | SSIM
Bicubic | 2 | – | $30.34$ | $0.870$ | $29.56$ | $0.844$ | $26.88$ | $0.841$ | $30.84$ | $0.935$
A+ (?) | 2 | – | $32.40$ | $0.906$ | $31.22$ | $0.887$ | $29.23$ | $0.894$ | $35.33$ | $0.967$
FSRCNN (?) | 2 | $0.01$ | $32.73$ | $0.909$ | $31.51$ | $0.891$ | $29.87$ | $0.901$ | $36.62$ | $0.971$
SRCNN (?) | 2 | $0.06$ | $32.29$ | $0.903$ | $31.36$ | $0.888$ | $29.52$ | $0.895$ | $35.72$ | $0.968$
MSLapSRN (?) | 2 | $0.22$ | $33.28$ | $0.915$ | $32.05$ | $0.898$ | $31.15$ | $0.919$ | $37.78$ | $0.976$
Our | 2 | $0.28$ | $33.27$ | $0.915$ | $31.99$ | $0.897$ | $31.37$ | $0.920$ | $37.92$ | $0.976$
VDSR (?) | 2 | $0.67$ | $32.97$ | $0.913$ | $31.90$ | $0.896$ | $30.77$ | $0.914$ | $37.16$ | $0.974$
LapSRN (?) | 2 | $0.81$ | $33.08$ | $0.913$ | $31.80$ | $0.895$ | $30.41$ | $0.910$ | $37.27$ | $0.974$
DRCN (?) | 2 | $1.78$ | $32.98$ | $0.913$ | $31.85$ | $0.894$ | $30.76$ | $0.913$ | $37.57$ | $0.973$
D-DBPN (?) | 2 | $5.95$ | $33.85$ | $0.919$ | $32.27$ | $0.900$ | $32.70$ | $0.931$ | $39.10$ | $0.978$
EDSR (?) | 2 | $40.7$ | $33.92$ | $0.919$ | $32.32$ | $0.901$ | $32.93$ | $0.935$ | $39.10$ | $0.977$
Bicubic | 4 | – | $26.10$ | $0.704$ | $25.96$ | $0.669$ | $23.15$ | $0.659$ | $24.92$ | $0.789$
A+ (?) | 4 | – | $27.43$ | $0.752$ | $26.82$ | $0.710$ | $24.34$ | $0.720$ | $27.02$ | $0.850$
FSRCNN (?) | 4 | $0.01$ | $27.70$ | $0.756$ | $26.97$ | $0.714$ | $24.61$ | $0.727$ | $27.89$ | $0.859$
SRCNN (?) | 4 | $0.06$ | $27.61$ | $0.754$ | $26.91$ | $0.712$ | $24.53$ | $0.724$ | $27.66$ | $0.858$
MSLapSRN (?) | 4 | $0.22$ | $28.26$ | $0.774$ | $27.43$ | $0.731$ | $25.51$ | $0.768$ | $29.54$ | $0.897$
Our | 4 | $0.28$ | $28.43$ | $0.778$ | $27.42$ | $0.732$ | $25.70$ | $0.774$ | $30.07$ | $0.904$
VDSR (?) | 4 | $0.67$ | $28.03$ | $0.770$ | $27.29$ | $0.726$ | $25.18$ | $0.753$ | $28.82$ | $0.886$
LapSRN (?) | 4 | $0.81$ | $28.19$ | $0.772$ | $27.32$ | $0.728$ | $25.21$ | $0.756$ | $29.09$ | $0.890$
DRCN (?) | 4 | $1.78$ | $28.04$ | $0.770$ | $27.24$ | $0.724$ | $25.14$ | $0.752$ | $28.97$ | $0.886$
D-DBPN (?) | 4 | $10.4$ | $28.82$ | $0.786$ | $27.72$ | $0.740$ | $26.54$ | $0.795$ | $31.18$ | $0.914$
EDSR (?) | 4 | $43.1$ | $28.80$ | $0.788$ | $27.71$ | $0.742$ | $26.64$ | $0.803$ | $31.02$ | $0.915$
Bicubic | 8 | – | $23.19$ | $0.568$ | $23.67$ | $0.547$ | $20.74$ | $0.516$ | $21.47$ | $0.647$
A+ (?) | 8 | – | $23.98$ | $0.597$ | $24.20$ | $0.568$ | $21.37$ | $0.545$ | $22.39$ | $0.680$
FSRCNN (?) | 8 | $0.01$ | $23.93$ | $0.592$ | $24.21$ | $0.567$ | $21.32$ | $0.537$ | $22.39$ | $0.672$
SRCNN (?) | 8 | $0.06$ | $23.85$ | $0.593$ | $24.13$ | $0.565$ | $21.29$ | $0.543$ | $22.37$ | $0.682$
MSLapSRN (?) | 8 | $0.22$ | $24.57$ | $0.629$ | $24.65$ | $0.592$ | $22.06$ | $0.598$ | $23.90$ | $0.759$
Our | 8 | $0.28$ | $24.82$ | $0.635$ | $24.67$ | $0.592$ | $22.21$ | $0.603$ | $24.12$ | $0.765$
VDSR (?) | 8 | $0.67$ | $24.21$ | $0.609$ | $24.37$ | $0.576$ | $21.54$ | $0.560$ | $22.83$ | $0.707$
LapSRN (?) | 8 | $0.81$ | $24.44$ | $0.623$ | $24.54$ | $0.586$ | $21.81$ | $0.582$ | $23.39$ | $0.735$
D-DBPN (?) | 8 | $23.2$ | $25.13$ | $0.648$ | $24.88$ | $0.601$ | $22.83$ | $0.622$ | $25.30$ | $0.799$
EDSR (?) | 8 | $43.1$ | $24.94$ | $0.640$ | $24.80$ | $0.596$ | $22.47$ | $0.620$ | $24.58$ | $0.778$

######  Definition 1 (Activation Gain)

The _gain_ of an activation function $\sigma$ is given by
$G(x)[i]=\sigma(x[i])/x[i]$ and equal to $1$ if $x[i]=0$.

Figure 3: Activation freezing procedure to convert a network into a linear
system. We can perform impulse response analysis to study the overall filter
effect at each pixel location.  Figure 4: Interpretation of the upscaling
network as a standard upscaler with adaptive filters.

######  Theorem 1 (Activation Freeze)

Let $\hat{W}_{n}=G(z_{n})W_{n}$ and $\hat{b}_{n}=G(z_{n})b_{n}$. Let

$Q_{0}=I\;,\quad Q_{i}=\prod_{k=n-i+1}^{n}\hat{W}_{k},\quad\text{for
}i=1,\ldots,n\;.$ (6)

The output of the convolutional network is given by $x_{n}=F\;x_{0}+R$ , where
$F=Q_{n}$ is the effective filter and
$R=Q\ast\hat{b}=\sum_{k=0}^{n}Q_{k}\hat{b}_{n-k}$ is the effective residual.

The proof of the theorem is a direct consequence of $\sigma(x)=G(x)x$ and
expansion of (5). Although this theorem only applies to sequential networks,
it helps to show that the overall effective filter depends on all
convolutional filters as well as biases (only through activations). Similarly,
the effective residual depends on both convolutional filters and biases (both
explicitly and through activations).

For the sake of simplicity, here we use our visualization technique from input
to outputs of the network. Nevertheless, we note that we could start at any
layer and stop at any posterior layer to study attributions within the
network.

## Experiments

We use one single configuration to test our system for $2\times$, $4\times$,
and $8\times$ upscaling. We configure the _Analysis_ , _Synthesis_ , _Upscale_
and _Downscale_ modules in Figure 1 using $4$–layer dense networks (?) as
filter–blocks. We use $48$ features and growth rate $16$ within dense
networks. For classic upscaler we start with Bicubic and the upscaling filters
are set as parameters to learn during training.

For training the system we fix the number of back–projections to $\mu=2$
(W–cycle according to Figure 2). We train the system for $8\times$ upscaler
with the multi–scale loss function introduced in (?):

$\mathcal{L}(Y,X;\theta)=\sum_{L=1,2,3}\sum_{k=1}^{L}\mathbb{E}\left[||Y^{L}_{k}-X_{k}||_{1}\right]\;.$
(7)

We train our system with Adam optimizer and a learning rate initialized as
$10^{-3}$ and square root decay. We use $128\times 128$ patches (pieces of
images) with batch size $16$. The patches were sampled randomly from datasets
DIV2K and Flickr2K, containing photographs of general natural scenes.

### Comparisons

Figure 5: Perceptual evaluation of different SR methods for $4\times$
upscaling.  Figure 6: Perceptual evaluation of different SR methods for
$8\times$ upscaling.

In Table 1 we compare PSNR and SSIM values for different methods. The two
evaluation metrics measure the difference between an upscaler output and the
original high-resolution image. Higher values are better in both cases.
Roughly speaking, PSNR (range $0$ to $\infty$) is a log–scale version of
mean–square–error and SSIM (range $0$ to $1$) uses image statistics to better
correlate with human perception. Full expressions are as follows:

$\displaystyle PSNR(X,Y)$
$\displaystyle=10\cdot\log_{10}\left(\frac{255^{2}}{MSE}\right)\;,$ (8)
$\displaystyle SSIM(X,Y)$
$\displaystyle=\frac{(2\mu_{X}\mu_{Y}+c_{1})(2\sigma_{XY}+c_{2})}{(\mu_{X}^{2}+\mu_{Y}^{2}+c_{1})(\sigma_{X}^{2}+\sigma_{Y}^{2}+c_{2})}\;,$
(9)

where $MSE=mean((X-Y)^{2})$ is the mean square error of $X$ and $Y$; $\mu_{X}$
and $\mu_{Y}$ are the averages of $X$ and $Y$, respectively; $\sigma_{X}^{2}$
and $\sigma_{Y}^{2}$ are the variances of $X$ and $Y$, respectively;
$\sigma_{XY}$ is the covariance of X and Y; $c_{1}=6.5025$ and
$c_{2}=58.5225$.

Our method is outperformed only by EDSR and DBPN, that use $20$ to more than
$100$ times the number of parameters of our system. Among systems with less
than $2$ million parameters, our system obtains better results, only matched
by MSLapSR for $2\times$ upscaling.

In Figure 8 we better visualize the difference in complexity between different
systems. It is apparent from these results that the size of the system matters
to improve PSNR values, with EDSR and DBPN far from other methods, but the
cost can be overwhelming in performance. Our system clearly improves the state
of the art for systems with less than two million parameters, with better
quality and significantly less parameters.

Figure 7: Output images for $8\times$ upscaling using different numbers of
back–projections $\mu$. The network was trained with $\mu=2$ fixed. The
effective filters are shown together with their frequency response (FFT).

Figures 5 and 6 show the difference in perceptual quality for $4\times$ and
$8\times$ upscaling. In general, EDSR and DBPN outputs look sharper and show
consistent geometry. But often we find patches with aliasing, such as parallel
lines, where the geometry becomes chaotic and perceptual quality behaves
randomly. In such cases our system can take advantage compared to most of
other systems.

(a) $4\times$ results on Set14

(b) $8\times$ results on Set14

Figure 8: Quality vs Complexity of different SR methods.  Figure 9: Effective
filters and residual for $4\times$ and $8\times$ upscaler. . Filters are not
only directional but follow several features around a pixels. Residuals are in
general small and thus most of the work is done by the filters.

### Analysis

Figure 9 shows two examples of effective filters and residuals according to
our novel visualization method. The shapes of filters following edges are
reminiscent of the research on directional filter upscalers (?; ?). In
general, we observe that filters are highly adaptive. They become symmetric
and narrow in flat areas (like Linear or Bicubic upscalers), directional close
to sharp lines, and increase in size close to complex features. For example,
in the $4\times$ upscale of Figure 9 a red box shows an area with the eye of a
baboon and the wrinkles around its eye. In the filter we can observe the shape
of the eye and waves following the wrinkles. As expected, for $8\times$
upscaler the receptive field increases since the filters look bigger. We
remind that we are using the same number of parameters, but passing through
more layers. In the green box in 9 we highlight the face and hand of a woman.
The filter at the tip of the nose follows the face features, and the filter at
the hand captures features from all the edges around.

Figure 7 shows the effect of the depth on the effective filters and residuals.
Here, training has tuned the network to work best with $\mu=2$
back–projections. For $\mu>2$ the output image looks oversharp, and too soft
for $\mu<2$. Accordingly, filters are larger and extract more high–frequencies
for $\mu>2$ and become smaller and low-pass for $\mu<2$. The same effect is
observed with classic IBP (?), showing the effective design of our network
architecture.

We observe that residuals are in general small and help fixing textures and
small details. This is an indication that filters are doing most of the work
for upscaling. We remind that, after freezing activations, the residual is a
fixed component of the output that does not change with the input. Thus,
residuals are very limited to estimate local details in the output as they
depend only on activations for this purpose.

On the other hand, filters contain relations between neighboring pixels and we
argue that because of this they are better to generalize. Effective filters
also show all the details regarding the receptive field of the network. The
receptive field is adaptive as the network does not use neighboring pixels if
it does not need to (e.g. flat areas) and extend to large areas when the
network is deep (e.g. $8\times$ upscaler) and local details are complex.

Finally, we remind that this analysis is precise. The network can be replaced
by these adaptive filters plus residuals and it would give the exact same
output. The strong dependency of filters and residuals on the input image
shows all the non–linearities of the network. It is remarkable that
convolutional networks can achieve the level of adaptivity revealed by these
visualization experiments and it further justifies their success in
super–resolution tasks.

## Conclusions

We introduced a new architecture for single image super–resolution that
reaches state of the art for methods with less that $2$ million parameters and
a new technique to analyze the network. The analysis shows how the network
learns to upscale by capturing complex relationships between pixels.

## References

  * [Algazi, Ford, and Potharlanka 1991] Algazi, V. R.; Ford, G. E.; and Potharlanka, R.  1991\.  Directional interpolation of images based on visual properties and rank order filtering.  In Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing, volume 4, 3005–3008.  Toronto, ON: IEEE Signal Processing Society.
  * [Dai et al. 2007] Dai, S.; Han, M.; Wu, Y.; and Gong, Y.  2007\.  Bilateral back–projection for single image super resolution.  In IEEE International Conference on Multimedia and Expo (ICME).
  * [Diamond et al. 2017] Diamond, S.; Sitzmann, V.; Heide, F.; and Wetzstein, G.  2017\.  Unrolled optimization with deep priors.  CoRR abs/1705.08041.
  * [Dong et al. 2014a] Dong, C.; Loy, C.; He, K.; and Tang, X.  2014a.  Learning a deep convolutional network for image super–resolution.  In et al., D. F., ed., Proceedings of European Conference on Computer Vision (ECCV), volume 8692 of Lecture Notes in Computer Science, 184–199.  Zurich: Springer.
  * [Dong et al. 2014b] Dong, C.; Loy, C. C.; He, K.; and Tang, X.  2014b.  Learning a deep convolutional network for image super–resolution.  In in Proceedings of European Conference on Computer Vision (ECCV).
  * [Dong et al. 2015] Dong, C.; Loy, C.; He, K.; and Tang, X.  2015\.  Image super–resolution using deep convolutional networks.  IEEE Transactions on Pattern Analysis and Machine Intelligence 38(2):295–307.
  * [Dong, Loy, and Tang 2016] Dong, C.; Loy, C. C.; and Tang, X.  2016\.  Accelerating the super–resolution convolutional neural network.  In in Proceedings of European Conference on Computer Vision (ECCV).
  * [Gong et al. 2018] Gong, D.; Zhang, Z.; Shi, Q.; van den Hengel, A.; Shen, C.; and Zhang, Y.  2018\.  Learning an optimizer for image deconvolution.  CoRR abs/1804.03368.
  * [Haris, Shakhnarovich, and Ukita 2018] Haris, M.; Shakhnarovich, G.; and Ukita, N.  2018\.  Deep back–projection networks for super–resolution.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
  * [Huang et al. 2017a] Huang, G.; Chen, D.; Li, T.; Wu, F.; van der Maaten, L.; and Weinberger, K. Q.  2017a.  Multi-scale dense convolutional networks for efficient prediction.  CoRR abs/1703.09844.
  * [Huang et al. 2017b] Huang, G.; Liu, Z.; van der Maaten, L.; and Weinberger, K. Q.  2017b.  Densely connected convolutional networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.
  * [Irani and Peleg 1991] Irani, M., and Peleg, S.  1991\.  Improving resolution by image registration.  CVGIP: Graph. Models Image Process. 53(3):231–239.
  * [Kim, Lee, and Lee 2016a] Kim, J.; Lee, J. K.; and Lee, K. M.  2016a.  Accurate image super–resolution using very deep convolutional networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR Oral).
  * [Kim, Lee, and Lee 2016b] Kim, J.; Lee, J. K.; and Lee, K. M.  2016b.  Deeply-recursive convolutional network for image super–resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR Oral).
  * [Kokkinos and Lefkimmiatis 2018] Kokkinos, F., and Lefkimmiatis, S.  2018\.  Deep image demosaicking using a cascade of convolutional residual denoising networks.  CoRR abs/1803.05215.
  * [Kruse, Rother, and Schmidt 2017] Kruse, J.; Rother, C.; and Schmidt, U.  2017\.  Learning to push the limits of efficient fft-based image deconvolution.  In The IEEE International Conference on Computer Vision (ICCV).
  * [Lai et al. 2017a] Lai, W.-S.; Huang, J.-B.; Ahuja, N.; and Yang, M.-H.  2017a.  Deep laplacian pyramid networks for fast and accurate super–resolution.  In IEEE Conference on Computer Vision and Pattern Recognition.
  * [Lai et al. 2017b] Lai, W.-S.; Huang, J.-B.; Ahuja, N.; and Yang, M.-H.  2017b.  Fast and accurate image super–resolution with deep laplacian pyramid networks.  arXiv:1710.01992.
  * [LeCun, Bengio, and Hinton 2015] LeCun, Y.; Bengio, Y.; and Hinton, G.  2015\.  Deep learning.  Nature 521(7553):436–444.
  * [Li and Orchard 2001] Li, X., and Orchard, M. T.  2001\.  New edge–directed interpolation.  IEEE Transactions on Image Processing 10(10):1521–1527.
  * [Lim et al. 2017] Lim, B.; Son, S.; Kim, H.; Nah, S.; and Lee, K. M.  2017\.  Enhanced deep residual networks for single image super–resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops.
  * [Mallat and Peyre 2007] Mallat, S., and Peyre, G.  2007\.  A review of bandlet methods for geometrical image representation.  Numerical Algorithms 44(3):205–234.
  * [Mallat 1998] Mallat, S.  1998\.  A Wavelet Tour of Signal Processing.  Academic Press.
  * [Olah et al. 2018] Olah, C.; Satyanarayan, A.; Johnson, I.; Carter, S.; Schubert, L.; Ye, K.; and Mordvintsev, A.  2018\.  The building blocks of interpretability.  Distill.  https://distill.pub/2018/building-blocks.
  * [Olah, Mordvintsev, and Schubert 2017] Olah, C.; Mordvintsev, A.; and Schubert, L.  2017\.  Feature visualization.  Distill.  https://distill.pub/2017/feature-visualization.
  * [Park, Park, and Kang 2003] Park, S.; Park, M.; and Kang, M.  2003\.  Super–resolution image reconstruction: a technical overview.  Signal Processing Magazine, IEEE 20(3):21–36.
  * [Proakis and Manolakis 2007] Proakis, J., and Manolakis, D.  2007\.  Digital Signal Processing.  Prentice Hall international editions. Pearson Prentice Hall.
  * [Romano, Isidoro, and Milanfar 2016] Romano, Y.; Isidoro, J.; and Milanfar, P.  2016\.  RAISR: rapid and accurate image super resolution.  CoRR abs/1606.01299.
  * [Timofte and Smet 2014] Timofte, R., and Smet, V. D.  2014\.  Gool, “a+: Adjusted anchored neighborhood regression for fast super–resolution.  In in Proc. Asian Conf. Comput. Vis. (ACCV.
  * [Timofte et al. ] Timofte, R.; Agustsson, E.; Van Gool, L.; Yang, M.-H.; Zhang, L.; et al.  Ntire 2017 challenge on single image super-resolution: Methods and results.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops.
  * [Trottenberg and Schuller 2001] Trottenberg, U., and Schuller, A.  2001\.  Multigrid.  Orlando, FL, USA: Academic Press, Inc.
  * [Widlund and Toselli 2004] Widlund, O., and Toselli, A.  2004\.  Domain decomposition methods - algorithms and theory, volume 34.  Springer.
  * [Yang et al. 2008] Yang, J.; Wright, J.; Huang, T.; and Ma, Y.  2008\.  Image super–resolution as sparse representation of raw image patches.  In IEEE Conference on Computer Vision and Pattern Recognition.
  * [Yang et al. 2010] Yang, J.; Wright, J.; Huang, T.; and Ma, Y.  2010\.  Image super–resolution via sparse representation.  Image Processing, IEEE Transactions on 19(11):2861–2873.
  * [Zhang and Zhu 2018] Zhang, Q., and Zhu, S.  2018\.  Visual interpretability for deep learning: a survey.  Frontiers of Information Technology and Electronic Engineering 19(1):27–39.
  * [Zhang et al. 2017] Zhang, K.; Zuo, W.; Gu, S.; and Zhang, L.  2017\.  Learning deep cnn denoiser prior for image restoration.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

## Supplementary Material

### Back–Projection Convergence

In the following analysis we consider vectors instead of images. This
simplifies the analysis since we can use (rectangular) matrices $U$ and $D$ to
represent upsampling and downsampling operators, respectively. Thus:

  * •

$Dy$ represents downsampling operation $(Y*g)\downarrow s$. Where
$y=\text{vec}(Y)$ for a high resolution image $Y$.

  * •

$Ux$ represents upsampling operation $(X\uparrow s)*p$. Where
$x=\text{vec}(X)$ for a low resolution image $X$.

Our $L$–level downscaling model is now:

$x=D^{L}y\;.$ (10)

The target of back–projections is to recover this property in upscale images.
Convergence is characterized by the mismatch error defined as follows:

######  Definition 2 (Downscale mismatch error)

The _downscale mismatch error_ of a high–resolution image $y_{L+1}$ at level
$L+1$ is given by:

$e(y_{L+1})=x-D^{L}y_{L+1}\;.$ (11)

And the classic back–projection algorithm uses the following iteration:

######  Definition 3 (Classic Back–projection)

The one–level ($L=1$) back–projection iteration is given by:

$y^{t+1}_{2}=y^{t}_{2}+Ue(y^{t}_{2})\;.$ (12)

First, we recall the classic convergence theorem (?), in a simplified version
adapted from (?).

######  Theorem 2 (Classic Back–Projection Convergence)

The one–level ($L=1$) back–projection iteration converges, $Dy\rightarrow x$,
at exponential rate if the following condition holds:

$||I-DU||_{1}<1\;,$ (13)

where $||A||_{1}=\max_{j}\sum_{i}|a_{ij}|$.

#### Proof:

$\displaystyle e(y^{t+1}_{2})$ $\displaystyle=$ $\displaystyle x-Dy^{t+1}_{2}$
(14) $\displaystyle=$ $\displaystyle x-D(y^{t}_{2}+Ue(y^{t}_{2}))$ (15)
$\displaystyle=$
$\displaystyle\underbrace{x-Dy^{t}_{2}}_{e(y^{t}_{2})}-DUe(y^{t}_{2})=(I-DU)e(y^{t}_{2})\;,$
(16)

By Hölder’s inequality we get
$||e(y^{t+1}_{2})||_{1}\leqslant||I-DU||_{1}\;||e(y^{t}_{2})||_{1}$ which
proves the theorem. $\square$

Now, we rewrite the MGBP algorithm using matrix/vector notation:

$MGBP(x)$: |  $BP^{\mu}_{k}(u,y_{1},\ldots,y_{k-1})$:
---|---
0: Input image $x$.  0: Integers $\mu\geqslant 0$ and $L\geqslant 1$.  0: Images $y_{k}$, $k=2,\ldots,L$.  1: $y_{1}=x$ 2: for $k=2,\ldots,L$ do 3: $u=Uy_{k-1}$ 4: $y_{k}=BP^{\mu}_{k}\left(u,y_{1},\ldots,y_{k-1}\right)$ 5: end for |  0: Image $u$, level index $k$, number of steps $\mu$.  0: Images $y_{1},\ldots,y_{k-1}$ (only for $k>1$).  0: Updated image $u$ 1: if $k>1$ then 2: for $step=1,\ldots,\mu$ do 3: $d=BP^{\mu}_{k-1}\left(Du,y_{1},\ldots,y_{k-2}\right)$ 4: $u=u+U(y_{k-1}-d)$ 5: end for 6: end if
Algorithm 2 Multi–Grid Back–Projection (MGBP) algorithm in matrix/vector
notation.

######  Definition 4 (single–level mismatch error)

Assume that the MGBP algorithm runs $\mu$ back–projection steps from level
$k=2,\ldots,L$. Then, the _single–level mismatch error_ for a $L+1$–resolution
image $y_{L+1}$ is given by:

$q(y_{L+1})=y^{\mu}_{L}-Dy_{L+1}$ (17)

This is usefull since the MGBP iteration can be written as
$y^{t+1}=y^{t}+Uq(y^{t})$. It easily follows that:

$\displaystyle q(y^{t+1}_{L+1})$ $\displaystyle=$ $\displaystyle
y^{\mu}_{L}-Dy^{t+1}_{L+1}$ (18) $\displaystyle=$ $\displaystyle
y^{\mu}_{L}-D(y^{t}_{L+1}+Uq(y^{t}_{L+1}))$ (19) $\displaystyle=$
$\displaystyle(I-DU)q(y^{t}_{L+1})$ (20)

######  Theorem 3 (MGBP Convergence)

The MGBP iteration converges, $D^{L}y_{L+1}\rightarrow x$, at exponential rate
if the following condition holds:

$||I-DU||_{1}<1\;.$ (21)

#### Proof:

We follow by induction. From the classic convergence theorem we know that
$||e(y^{t+1}_{2})||_{1}\leqslant||I-DU||_{1}\;||e(y^{t}_{2})||_{1}$. For $L=1$
the MGBP iteration is equivalent to classic back–projection, and so the
theorem is verified for $L=2$.

Next, we assume that the theorem holds for $L$ and we study the error for
$L+1$:

$\displaystyle e(y^{\mu}_{L+1})$ $\displaystyle=$ $\displaystyle
x-D^{L}y^{\mu}_{L+1}$ (22) $\displaystyle=$ $\displaystyle
x-D^{L-1}(y^{\mu}_{L}-q(y^{\mu}_{L+1}))$ (23) $\displaystyle=$ $\displaystyle
x-D^{L-1}(y^{\mu}_{L}-(I-DU)^{\mu}q(y^{0}_{L+1}))$ (24) $\displaystyle=$
$\displaystyle x-D^{L-1}(y^{\mu}_{L}-(I-DU)^{\mu}(y^{\mu}_{L}-DUy^{\mu}_{L}))$
(25) $\displaystyle=$
$\displaystyle\underbrace{x-D^{L-1}y^{\mu}_{L}}_{e(y^{\mu}_{L})}+D^{L-1}(I-DU)^{\mu+1}y^{\mu}_{L}$
(26)

By triangle inequality and Hölder’s inequality we have:

$||e(y^{\mu}_{L+1})||_{1}\leqslant||e(y^{\mu}_{L})||_{1}+||D^{L-1}||_{1}||(I-DU)^{\mu+1}||_{1}||y^{\mu}_{L}||_{1}\;.$
(27)

The first term decreases exponentially by inductive assumption. The second
term also decreases exponentially with $\mu$ if $||I-DU||_{1}<1$. The term
$||y^{\mu}_{L}||_{1}$ is bounded since by inductive assumption we know that
$y^{\mu}_{L}$ converges to a fixed $L$–level image. $\square$