# Trivial colors in colorings of Kneser graphs

Sergei Kiselev111Moscow Institute of Physics and Technology, Email:
<EMAIL_ADDRESS>Andrey Kupavskii222G-SCOP, CNRS, University Grenoble-
Alpes, France and Moscow Institute of Physics and Technology, Russia; Email:
<EMAIL_ADDRESS>The authors acknowledge the financial support from the
Russian Government in the framework of MegaGrant no 075-15-2019-1926.

###### Abstract

We show that any proper coloring of a Kneser graph $KG_{n,k}$ with $n-2k+2$
colors contains a trivial color (i.e., a color consisting of sets that all
contain a fixed element), provided $n>(2+\epsilon)k^{2}$, where $\epsilon\to
0$ as $k\to\infty$. This bound is essentially tight.

##  1 Introduction

Throughout the paper, we use standard notations $[n]:=\\{1,\ldots,n\\},$
$[a,b]=\\{a,a+1,\ldots,b\\}$, $2^{X}$ for the power set of $X$, and ${X\choose
k}$ for the collection of all $k$-element subsets of $X.$ Any
$\mathcal{F}\subset 2^{X}$ we call a family.

Given positive integers $n\geqslant 2k$, a Kneser graph $KG_{n,k}$ is a graph
whose vertex set is the collection of all $k$-element subsets of the set
$\\{1,\ldots,n\\}$, with edges connecting pairs of disjoint sets. One of the
classical results in combinatorics, conjectured by Kneser [5] and proved by
Lovász [6], states that the chromatic number of $KG_{n,k}$ is equal to
$n-2k+2$. The proof of Lovász, as well as subsequent proofs given by Bárány
and Green, rely on the Borsuk–Ulam theorem and thus on combinatorial topology.
There was a ‘‘combinatorial’’ proof given by Matousek and Ziegler, which used
Tucker’s lemma instead of the Borsuk-Ulam theorem, but it essentially uses the
same machinery as the previous proofs. One of the drawbacks of only having a
combinatorial topology proof is that the approach is very sensitive to the
setting, and many related questions seem to be out of reach of that method. In
particular, we do not know, how big is the largest vertex subset of $KG_{n,k}$
that we can properly cover in $n-2k+1$ colors. This motivates the quest of
searching for a more extremal-combinatorial approach to this question. One
step in this direction is to better understand the structure of proper
colorings of $KG_{n,k}$ that use few (minimum possible number of) colors.

Note that each color in the coloring of $KG_{n,k}$ forms an independent set,
which, in turn, is an intersecting family: i.e., a family of sets in which any
two intersect. In this terminology, a proper coloring of $KG_{n,k}$ into $t$
colors is the same as a partition of ${[n]\choose k}$ into $t$ intersecting
families. We say that an intersecting family is trivial, or a star, if all
sets in the family contain a fixed element $i$. If this is the case, then we
say that $i$ is a center of $\mathcal{F}$. More generally, we call two
families $\mathcal{A},\mathcal{B}\subset 2^{X}$ cross-intersecting, if $A\cap
B\neq\emptyset$ for any $A\in\mathcal{A},B\in\mathcal{B}$.

The standard example of a proper coloring of $KG_{n,k}$ consists of $n-2k+1$
star $\mathcal{C}_{1},\ldots,\mathcal{C}_{n-2k+1}$, where
$\mathcal{C}_{i}:=\\{A\in{[n]\choose k}:A\subset[i,n],i\in A\\}$, and the set
${[n-2k+2,n]\choose k}$. That is, all but one colors are trivial. The
advantage of always having a trivial color in a coloring of $KG_{n,k}$ is that
one can remove the color, remove the corresponding center from the ground set,
and thus reduce the study of colorings of $KG_{n,k}$ to that of $KG_{n-1,k}.$
This motivates the following question, asked by the authors in [4]:

######  Problem 1.

Given $k$, what is the largest number $n=n(k)$, such that there exists a
proper coloring of $KG_{n,k}$ into $n-2k+2$ colors without any trivial colors?

Let us recall two important results from extremal set theory. First, the
Erdős–Ko–Rado theorem [1] states that $\alpha(KG_{n,k})={n-1\choose k-1},$
provided $n\geqslant 2k$. The Hilton–Milner theorem [2] states that any non-
trivial intersecting family of $k$-subsets of $[n]$ has size at most
${n-1\choose k-1}-{n-k-1\choose k-1}+1$, provided $n\geqslant 2k.$ Let us use
the latter to establish a simple bound on $n(k).$

######  Proposition 2.

We have $n(k)<k^{3}$ for $k\geqslant 3$.

###### Proof.

The Hilton-Milner theorem states that any non-trivial intersecting family in
${[n]\choose k}$ has size at most
$\binom{n-1}{k-1}-\binom{n-k-1}{k-1}+1\leqslant k\binom{n-2}{k-2}$. If we have
a coloring of $KG_{n,k}$ with non-trivial colors, then we need at least
$\binom{n}{k}/\left(k\binom{n-2}{k-2}\right)=\frac{n(n-1)}{k^{2}(k-1)}$ colors
cover all vertices. This is larger than $n-2k+2$ for $n=k^{3}$ and $k\geqslant
3$. ∎

Doing a bit more careful calculations, one can show that $n(k)\leqslant
k^{3}-k^{2}-2k+2$ for $k\geqslant 3$ using the argument above. However, the
$k^{3}$-barrier for $n$ is not easy to improve.

On the other hand, in [4] we provided a construction of a coloring with non-
trivial colors, which gives $n(k)\geqslant 2(k-1)^{2}$ for $k\geqslant 3$. For
completeness, we will reproduce the construction in the next section.

The main result of this paper is a proof of an almost-matching upper bound on
$n(k).$

######  Theorem 3.

Let $n,k$ be sufficiently large integers, and
$\varepsilon=\varepsilon(k)=\frac{3}{\ln k}$ be such that
$n\geqslant(2+\varepsilon)k^{2}$. Then $\binom{[n]}{k}$ cannot be covered by
$n$ intersecting non-trivial families. In particular,
$n(k)<(2+\varepsilon)k^{2}$ for all sufficiently large $k$.

Note that the theorem is stated in terms of covering ${[n]\choose k}$ by
intersecting families. This is stronger than the same statement for partitions
of ${[n]\choose k}$ (i.e., colorings of $KG_{n,k}$) since any partition is a
covering as well.

Besides being interesting in its own right, our proofs introduce an
interesting mixture of techniques that may be useful for other problems
related to intersecting families.

The rest of the paper is structured as follows. In the next section, we shall
present the lower bound construction from [4]. In Section 3, we will prove a
slightly weaker upper bound on $n(k)$. In Section 4, we will prove Theorem 3.

##  2 Lower bound construction

######  Proposition 4 ([4]).

We have $n(k)\geqslant 2(k-1)^{2}$ for $k\geqslant 3$.

###### Proof.

Put $n:=2(k-1)^{2}$ and split the ground set $[n]$ into $k-1$ blocks $A_{i}$
of size $2k-2$. For each block, say, $A_{1}:=[2k-2]$, consider the following
covering by intersecting families: for $i=1,\ldots,2k-5$, define

$F_{i}:=\\{2k-4,2k-3,2k-2\\}\cup\\{i+1,\ldots,i+k-3\\},$

where the addition and subtraction in the second part of the set is modulo
$2k-5$ (and thus the elements belong to $[2k-5]$). Consider the intersecting
Hilton-Milner-type families of the form

$\mathcal{H}_{i}:=\Big{\\{}F\in{[n]\choose k}:i\in F,F\cap
F_{i}\neq\emptyset\Big{\\}}\cup\\{F_{i}\\}.$

Complement it with the intersecting family

$\mathcal{G}:=\Big{\\{}F\in{[n]\choose k}:|F\cap\\{2k-4,2k-3,2k-2\\}|\geqslant
2\Big{\\}}.$

If a set $G\cap[2k-2]\supset\\{i,j\\}$ for $i<j$, then $G$ is contained in one
of the families $\mathcal{G}$, $\mathcal{H}_{l},$ $l\in[2k-5]$. Indeed,

  * •

if $\\{i,j\\}\subset\\{2k-4,2k-3,2k-2\\}$, then $G\subset\mathcal{G}$;

  * •

if $i<2k-4\leqslant j$, then $G\subset\mathcal{H}_{i}$;

  * •

if $j<2k-4$ and $j\leqslant i+k-3$, then $G\subset\mathcal{H}_{i}$;

  * •

if $i+k-2\leqslant j<2k-4$, then $j+k-3$ mod $2k-5$ is at least $i$, and $G$
is contained in $\mathcal{H}_{j}$.

Therefore, any set intersecting $A_{1}$ in at least $2$ elements is contained
in one of the intersecting families given above. On the other hand, any
$k$-set must intersect one of the $k-1$ blocks in at least $2$ elements. Thus,
considering similar collections of intersecting families in the other blocks,
we get that the whole of ${[n]\choose k}$ is covered.

We have $2k-4$ intersecting families on each block, which gives $(2k-4)(k-1)$
families in total. On the other hand,
$\chi(KG_{n,k})=2(k-1)^{2}-2k+2=2(k-2)(k-1)$, that is, the number of
intersecting families we used equals the chromatic number of the graph. It is
also clear that none of the families is a star, and we can easily preserve
this property when making a coloring (rather than a covering). ∎

We note that most of the families in the coloring presented above are
Hilton–Milner type families.

##  3 A weaker upper bound

We say that $C\subset X$ is a cover of a family $\mathcal{F}\subset 2^{X}$ if
$C\cap A\neq\emptyset$ for any $A\in\mathcal{F}$. Let $\tau(\mathcal{F})$
stand for the size of the smallest cover of $\mathcal{F}.$ Note that saying
that $\tau(\mathcal{F})\geqslant 2$ is the same as saying that $\mathcal{F}$
is non-trivial. In this section we are going to prove the following theorem.

######  Theorem 5.

Consider $m$ intersecting families
$\mathcal{F}_{1},\ldots,\mathcal{F}_{m}\subset\binom{[n]}{k}$ with
$\tau(\mathcal{F}_{i})\geqslant 2$ and such that
$\mathcal{F}_{1}\cup\ldots\cup\mathcal{F}_{m}=\binom{[n]}{k}$. Then
$m>n^{2}/(8k^{2})$.

A simple numerical corollary is as follows.

######  Corollary 6.

If $n\geqslant 8k^{2}$, $k\geqslant 2$ and $KG_{n,k}$ is covered by $n-2k+2$
intersecting families, then one of these families is trivial. In short,
$n(k)<8k^{2}.$

In the proof of Theorem 5, we are going to use the following elegant result
due to Spencer. We reproduce its proof for completeness. Note that
$\mathsf{E}$ stand for the expectation, and for a family $\mathcal{H}$ and a
set $A$, we denote by $\mathcal{H}[A]$ the restriction of $\mathcal{H}$ on
$A$, that is, $\mathcal{H}[A]=\\{X\in\mathcal{H}:X\subset A\\}$. Given a
family $\mathcal{F}\subset 2^{X}$, a subset $I\subset X$ is an independent set
in $\mathcal{F}$ if no set from $\mathcal{F}$ is entirely contained in $I$.

######  Theorem 7 ([8]).

Consider a family $\mathcal{H}\subset 2^{[n]}$ containing no independent set
of size $b$ and let $\mathcal{H}^{(k)}$,
$\mathcal{H}^{(k)}\subset\mathcal{H},$ be the family of all $k$-sets of
$\mathcal{H}$, $1\leqslant k\leqslant n$. Then for any $0<p<1$ the following
holds:

$\sum_{i=2}^{n}|\mathcal{H}^{(i)}|p^{i}>np-b.$

###### Proof.

Take a random subset $A$ of $[n]$, including each element independently with
probability $p$. Then, for each set $X\in\mathcal{H}[A],$ remove an arbitrary
element $v\in X$ from $A$. The resulting set $A^{\prime}$ is clearly
independent, therefore $|A|-|\mathcal{H}[A]|\leqslant|A^{\prime}|<b$. Since
this holds for any $A$, we get that the same holds on average:

$\mathsf{E}|A|-\mathsf{E}|\mathcal{H}[A]|<b.$

The statement of the theorem follows from the inequality above by substituting
the values of the expectations: $\mathsf{E}|A|=np$ and
$\mathsf{E}|\mathcal{H}[A]|=\sum_{i=2}^{n}|\mathcal{H}^{(i)}|p^{i}$. ∎

Note that the bound in Theorem 7 is not sharp, e.g. for a 2-graph it states
that the number of edges is at least $n^{2}/(4b)$, while Turán’s theorem gives
approximately $n^{2}/(2b)$ edges. This is a potential direction for
improvement, which, unfortunately, does not give results as sharp as Theorem
3.

We say that a family $\mathcal{H}$ _set-covers_ a family $\mathcal{F}$ if for
each set $F\in\mathcal{F}$ there is a set $H\in\mathcal{H}$ such that
$H\subset F$. Note that any independent set in $\mathcal{H}$ is also
independent in $\mathcal{F}$.

######  Lemma 8.

Let $\mathcal{F}\subset\binom{[n]}{k}$ be an intersecting family with
$\tau(\mathcal{F})=\tau$. Then it can be set-covered by a family of
$\tau$-sets of size $\tau k^{\tau-1}$.

###### Proof.

For any $Y\subset[n]$, we use a standard notation
$\mathcal{F}(Y):=\\{F\in\mathcal{F}:Y\subset F\\}$. Consider a cover $X$ of
$\mathcal{F}$ of size $\tau$. Define $\mathcal{H}_{1}\subset{[n]\choose 1}$ as
follows: $\mathcal{H}_{1}:=\\{\\{i\\}:i\in X\\}.$ Then
$\mathcal{F}\subset\cup_{G\in\mathcal{H}(1)}\mathcal{F}(G)$ by the definition
of a cover.

For each $1\leqslant\ell<\tau$, let us show how to construct
$\mathcal{H}_{\ell+1}$ from $\mathcal{H}_{\ell}$. More precisely, assume that
we have a family $\mathcal{H}_{\ell}\subset{[n]\choose\ell}$ of at most $\tau
k^{\ell-1}$ sets such that
$\mathcal{F}\subset\cup_{G\in\mathcal{H}_{\ell}}\mathcal{F}(G)$. For each set
$G\in\mathcal{H}_{\ell}$, consider a set $F_{G}\in\mathcal{F}$ that is
disjoint with $G$. Such set must exist since $|G|<\tau$. Put
$\mathcal{H}_{\ell+1}:=\\{G\cup\\{i\\}:G\in\mathcal{H}_{\ell},i\in F_{G}\\}$.
It should be clear that $|\mathcal{H}_{\ell+1}|\leqslant\tau k^{\ell}$ and
that

$\mathcal{F}\subset\bigcup_{G^{\prime}\in\mathcal{H}_{\ell+1}}\mathcal{F}(G^{\prime}).$

Finally, we put $\mathcal{H}:=\mathcal{H}_{\tau}$. ∎

###### Proof of Theorem 5.

Consider a collection $\mathcal{F}_{1},\ldots,\mathcal{F}_{m}$ of intersecting
families that cover ${[n]\choose k}$. Put $\tau_{i}:=\tau(\mathcal{F}_{i})$
and let $\mathcal{H}_{i}$ be a set-covering of $\mathcal{F}_{i}$ from Lemma 8.
Then the union $\mathcal{H}_{1}\cup\ldots\cup\mathcal{H}_{m}$ has no
independent set of size $k$ and from Theorem 7 we have

$\sum_{i=1}^{m}\tau_{i}k^{\tau_{i}-1}p^{\tau_{i}}>np-k$

which is equivalent to

$\sum_{i=1}^{m}\tau_{i}(kp)^{\tau_{i}-1}>n-k/p.$

Note that $xa^{x-1}<2a$ for $x>2$ and $a<1/\sqrt{e}$, therefore the inequality
above is implied by the following inequality:

$2mkp>n-k/p,$

provided that $kp<1/\sqrt{e}$. This is true for our choice of $n$ if we take
$p=2k/n$. Substituting this value of $p$ in the last displayed inequality, we
get $4mk^{2}/n>n/2,$ which is equivalent to the statement of the theorem. ∎

##  4 Proof of Theorem 3

Assume that there are intersecting families
$\mathcal{F}_{1},\ldots,\mathcal{F}_{n}$ with $\tau(\mathcal{F}_{i})\geqslant
2$ such that $\mathcal{F}_{1}\cup\ldots\cup\mathcal{F}_{n}=\binom{[n]}{k}$.

The first step of the proof is to split each color $\mathcal{F}_{i}$ into two
parts such that each is easier to deal with. This is done using the following
simple lemma.

######  Lemma 9.

Let $\mathcal{G}$ be an intersecting family of $k$-sets with
$\tau(\mathcal{G})\geqslant 2$. Then we can split it into
$\mathcal{G}^{\prime}\sqcup\mathcal{G}^{\prime\prime}$, where
$\mathcal{G}^{\prime}$ can be set-covered by at most $k$ 2-edges and
$\mathcal{G}^{\prime\prime}$ cross-intersects some family of $t$-sets
$\mathcal{G}^{\times}$ with $t\in\\{k-1,k\\}$ and
$\tau(\mathcal{G}^{\times})\geqslant\sqrt{k}$.

###### Proof.

If $\tau(\mathcal{G})\geqslant\sqrt{k}$, we can put
$\mathcal{G}^{\prime\prime}:=\mathcal{G}$, since $\mathcal{G}$ cross-
intersects itself. So we will assume that
$2\leqslant\tau(\mathcal{G})<\sqrt{k}$.

Put $\tau:=\tau(\mathcal{G})$ and let $a_{1},\ldots,a_{\tau}$ be a piercing
set of $\mathcal{G}$. Put $\mathcal{G}_{i}=\\{G\setminus\\{a_{i}\\}\colon
G\in\mathcal{G},a_{i}\in G\\}$. Note that we can set-cover $\mathcal{G}$ by
$S:=\sum_{i=1}^{\tau}\tau(\mathcal{G}_{i})$ edges: for each $i$ we draw edges
from $a_{i}$ to vertices of a piercing set of $\mathcal{G}_{i}$.

If $S\leqslant k$ we can put $\mathcal{G}^{\prime}=\mathcal{G}$ and
$\mathcal{G}^{\prime\prime}=\varnothing$. Otherwise, for some $i$ we have,
$\tau(\mathcal{G}_{i})>k/\tau>\sqrt{k}$. Then we put $\mathcal{G}^{\prime}$ to
be the family of all sets containing $a_{i}$,
$\mathcal{G}^{\prime\prime}:=\mathcal{G}\setminus\mathcal{G}^{\prime}$ and
$\mathcal{G}^{\times}:=\mathcal{G}_{i}$. ∎

Using this lemma, we split
$\mathcal{F}_{i}=\mathcal{F}^{\prime}_{i}\sqcup\mathcal{F}^{\prime\prime}_{i}$
for each $i\in[n]$. Next, consider a ($2$-)graph $H$ on $[n]$ formed by at
most $kn$ edges that altogether set-cover
$\mathcal{F}^{\prime}_{1},\ldots,\mathcal{F}^{\prime}_{n}$ (the existence of
such $H$ is guaranteed by the lemma). Each independent $k$-set of $H$ should
belong to some $\mathcal{F}_{i}$, therefore it must be contained in the
corresponding family $\mathcal{F}_{i}^{\prime\prime}$.

The following theorem is the crux of the proof.

######  Theorem 10.

In the assumptions of Theorem 3, let $G$ be a graph on $[n]$ with at most $nk$
edges and let $\mathcal{I}(G)$ be the family of all $k$-sets in $[n]$ that are
independent in $G$. Let $\mathcal{F}\subset\mathcal{I}(G)$ be a family of
independent $k$-sets in G, which cross-intersects some family $\mathcal{G}$ of
$t$-sets with $\tau(\mathcal{G})\geqslant\sqrt{k}$ and $t\leqslant k$. Then
$|\mathcal{I}(G)|>n\cdot|\mathcal{F}|$.

We prove this theorem in a separate subsection. Using this result, it is
straightforward to finish the proof of Theorem 3. Indeed, the $k$-sets that
are not set-covered by $H$ ($\mathcal{I}(G)$ in the notation of Theorem 10)
must be contained in the union of $\mathcal{F}^{\prime\prime}_{i},$ $i\in[n].$
However by Lemma 9, each $\mathcal{F}^{\prime\prime}_{i}$ cross-intersects a
family of $t$-sets $\mathcal{G}_{i}$, where $t\leqslant k$, with
$\tau(\mathcal{G}_{i})\geqslant\sqrt{k}$. Theorem 10 then guarantees that
$\mathcal{I}(H)$ satisfies
$|\mathcal{I}(H)|>n|\mathcal{F}^{\prime\prime}_{i}|,$ and thus
$\mathcal{I}(H)$ cannot be covered by the union of
$\mathcal{F}^{\prime\prime}_{i}$, a contradiction.

###  4.1 Proof of Theorem 10

In view of Proposition 2, we can assume that $n<k^{3}$. We are going to use
the following result by Khadžiivanov and Nikiforov [3] (see [7] for a
reformulation and a proof in English):

######  Theorem 11.

For a given graph $G$ let $\gamma$ be the density $\frac{|E(G)|}{|V(G)|^{2}}$
and $N_{r}(G)$ be the number of cliques on $r$ vertices, $r\leqslant n$. Then,
if $\gamma\geqslant\frac{r-2}{2(r-1)}$, we have

$N_{r}(G)\geqslant\frac{2(r-1)\gamma-(r-2)}{r}\cdot
nN_{r-1}(G)\mbox{\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ and\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ }N_{r-1}(G)>0.$ (1)

Note that if the inequality on $\gamma$ in Theorem 1 holds for some $r$, then
it holds for smaller $r\geqslant 2$ as well. That is, we can apply
$\eqref{reiher_eq}$ several times to compare $N_{r}(G)$ with
$N_{r^{\prime}}(G)$ for $r>r^{\prime}\geqslant 2$.

The idea behind the proof is as follows. Similarly to the proof of Lemma 8 we
inductively construct a family that set-covers $\mathcal{F}$ of larger and
larger uniformity using sets from $\mathcal{G}$. (These set-covers are encoded
in the families $\mathcal{H}_{\ell}$ from the proof. We have to be more
careful with these set-covers than in Lemma 8, in order to ensure disjointness
of certain families.) At each step of the procedure, indexed by the uniformity
of $\mathcal{H}_{\ell}$, we consider the collection of independent sets that
is set-covered by $\mathcal{H}_{\ell}$, and bound from below the proportion of
these sets that would be ‘‘missed out’’ by the set-cover
$\mathcal{H}_{\ell+1}$ of size $1$ larger. We use the result of Khadžiivanov
and Nikiforov for this bound.

###### Proof of Theorem 10.

Let $\mathcal{I}$ be the family of all $k$-independent sets in $G$. Put
$\tau:=\tau(\mathcal{G})$. For $A\subset[n]$, $|A|<\tau$, fix a set
$F_{A}\in\mathcal{G}$ which is disjoint with $A$. For $A\subset B\subset[n]$
and a family $\mathcal{W}\subset 2^{[n]}$, denote

$\mathcal{W}(A,B):=\\{F\setminus A\colon F\in\mathcal{W},F\cap B=A\\}.$

Put $N_{\ell}=t^{\ell}$. First, we are going to construct a sequence of
families $\mathcal{H}_{\ell}$ of pairs $(A_{i},B_{i})$, $i=1,\ldots,N_{\ell}$,
such that $\mathcal{F}=\bigsqcup_{i=1}^{N_{\ell}}\mathcal{F}(A_{i},B_{i})$,
$|A_{i}|=\ell$, $|B_{i}|\leqslant\ell k$. (Disjointness is crucial here.)

Construction of $\mathcal{H}_{\ell}$. First, we put
$\mathcal{H}_{0}:=\\{(\varnothing,\varnothing)\\}$.

For each $0\leqslant\ell<\tau$, let us show how to construct
$\mathcal{H}_{\ell+1}$ from $\mathcal{H}_{\ell}$. We have
$\mathcal{H}_{\ell}:=\\{(A_{1},B_{1}),\ldots,(A_{N_{\ell}},B_{N_{\ell}})\\}$
such that $|A_{i}|=\ell$,

$\mathcal{F}=\bigsqcup_{i=1}^{N_{\ell}}\mathcal{F}(A_{i},B_{i})\mbox{\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ and\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
}\mathcal{I}\supset\bigsqcup_{i=1}^{N_{\ell}}\mathcal{I}(A_{i},B_{i}).$

For each pair $(A,B)\in\mathcal{H}_{\ell}$ put
$\\{f_{1},\ldots,f_{t}\\}:=F_{A}$. Since each set in $\mathcal{F}$ intersects
$F_{A}$, we can decompose

$\mathcal{F}(A,B)=\bigsqcup_{j=1}^{t}\mathcal{F}\big{(}A\cup\\{f_{j}\\},B\cup\\{f_{1},\ldots,f_{j}\\}\big{)}$

and

$\mathcal{I}(A,B)=\mathcal{I}(A,B\cup
F_{A})\sqcup\bigsqcup_{j=1}^{t}\mathcal{I}(A\cup\\{f_{j}\\},B\cup\\{f_{1},\ldots,f_{j}\\})$
(2)

Then we put

$\mathcal{H}_{\ell+1}:=\bigcup_{(A,B)\in\mathcal{H}_{\ell}}\Big{\\{}\big{(}A\cup\\{f_{j}\\},B\cup\\{f_{1},\ldots,f_{j}\\}\big{)}\colon
j=1,\ldots,t,\ \text{where}\ \\{f_{1},\ldots,f_{t}\\}=F_{A}\Big{\\}}.$

This completes the construction of $\mathcal{H}_{\ell}.$

Put
$\mathcal{I}_{\ell}:=\bigsqcup_{(A,B)\in\mathcal{H}_{\ell}}\mathcal{I}(A,B)$.
Note that, since $\mathcal{F}(A,B)\subset\mathcal{I}(A,B)$, we have
$\mathcal{F}\subset\mathcal{I}_{\ell}$ for any $\ell\leqslant\tau$.

Let $c_{\ell}\geqslant 0$ be such that for any $(A,B)\in\mathcal{H}_{\ell}$,
$\\{f_{1},\ldots,f_{t}\\}=F_{A}$, we have

$\mathcal{I}(A,B\cup F_{A})\geqslant
c_{\ell}\cdot\sum_{j=1}^{t}\big{|}\mathcal{I}(A\cup\\{f_{j}\\},B\cup\\{f_{1},\ldots,f_{j}\\})\big{|}.$
(3)

Note that by the definition of $c_{\ell}$ and (2) we have

$|\mathcal{I}_{\ell}|\geqslant(1+c_{\ell})\cdot|\mathcal{I}_{\ell+1}|$

for any $0\leqslant\ell<\tau$ and, therefore,

$|\mathcal{I}|=|\mathcal{I}_{0}|\geqslant|\mathcal{I}_{\tau}|\cdot\prod_{\ell=0}^{\tau-1}(1+c_{\ell})\geqslant|\mathcal{F}|\cdot\prod_{\ell=0}^{\tau-1}(1+c_{\ell}).$
(4)

Now we are going to show that we can put $c_{\ell}:=e^{-1/\varepsilon}$ in
(3).

Consider a pair $(A,B)$ from $\mathcal{H}_{\ell}$ anf put
$\\{f_{1},\ldots,f_{t}\\}=F:=F_{A}$. For convenience, put
$\mathcal{I}^{\prime}:=\mathcal{I}(A,B)$. We can decompose

$\bigsqcup_{j=1}^{t}\mathcal{I}^{\prime}(\\{f_{j}\\},\\{f_{1},\ldots,f_{j}\\})=\bigsqcup_{\varnothing\neq
A^{\prime}\subset F}\mathcal{I}^{\prime}(A^{\prime},F).$

Let us compare |$\mathcal{I}^{\prime}(\varnothing,F)$| and
$|\mathcal{I}^{\prime}(A^{\prime},F)|$, for $A^{\prime}\subset F$,
$A^{\prime}\neq\varnothing$ using Theorem 1.

Put $X:=[n]\setminus(B\cup F)$. We are going to apply Theorem 1 on the graph
$\overline{G}[X]$, i.e., the complement of $G$ induced on $X$. Put
$\gamma=\frac{1}{2}-\rho$, where $\rho$ is the density of edges in $G[X]$.
Note that
$\rho\leqslant\frac{|e(G)|}{|X|^{2}}\leqslant\frac{nk}{(n-k(\ell+1))^{2}}$.

Recall that $\mathcal{I}^{\prime}(\varnothing,F)$ is the family of independent
$(k-\ell)$-sets in $G[X]$. Note that each set from
$\mathcal{I}^{\prime}(A^{\prime},F)$ is the intersection (of size
$k-\ell-|A^{\prime}|$) of a $k$-element independent set in $G$ with $X$, and
thus $|\mathcal{I}^{\prime}(A^{\prime},F)|$ is bounded from above by the
number of independent $(k-\ell-|A|)$-sets in $G[X]$. Applying (1), we have

$|\mathcal{I}^{\prime}(\varnothing,F)|\geqslant|\mathcal{I}^{\prime}(A^{\prime},F)|\cdot
n^{|A^{\prime}|}\prod_{i=0}^{|A^{\prime}|-1}\frac{2(k-\ell-i-1)\gamma-(k-\ell-i-2)}{k-\ell-i}=$
$=|\mathcal{I}^{\prime}(A^{\prime},F)|\cdot
n^{|A^{\prime}|}\prod_{i=0}^{|A^{\prime}|-1}\frac{1-2(k-\ell-i-1)\rho}{k-\ell-i}.$

######  Claim 12.

We have $(k-\ell-i-2)\rho\leqslant\frac{k^{2}}{n}$.

###### Proof.

Indeed,

$(k-\ell-i-2)\rho\leqslant\frac{nk(k-\ell-i-2)}{(n-k(\ell+1))^{2}}=\frac{k^{2}}{n}\cdot\frac{1-\frac{\ell+i+2}{k}}{\left(1-\frac{k}{n}(\ell+1)\right)^{2}}\leqslant$
$\leqslant\frac{k^{2}}{n}\cdot\frac{1-\frac{\ell+i+2}{k}}{\left(1-\frac{\ell+1}{2k}\right)^{2}}\leqslant\frac{k^{2}}{n}\cdot\frac{1-\frac{\ell+i+2}{k}}{1-\frac{\ell+1}{k}}\leqslant\frac{k^{2}}{n}.$

∎

Then we have

$|\mathcal{I}^{\prime}(\varnothing,F)|\geqslant|\mathcal{I}^{\prime}(A^{\prime},F)|\cdot
n^{|A^{\prime}|}\prod_{i=0}^{|A^{\prime}|-1}\frac{1-2k^{2}/n}{k-\ell-i}\geqslant|\mathcal{I}^{\prime}(A^{\prime},F)|\cdot\left(\frac{n-2k^{2}}{k}\right)^{|A^{\prime}|}\geqslant|\mathcal{I}^{\prime}(A^{\prime},F)|\cdot(\varepsilon
k)^{|A^{\prime}|}$

Rewriting, we get

$\sum_{\varnothing\neq A^{\prime}\subset
F}\frac{|\mathcal{I}^{\prime}(A^{\prime},F)|}{|\mathcal{I}^{\prime}(\varnothing,F)|}\leqslant\sum_{\varnothing\neq
A^{\prime}\subset F}(\varepsilon k)^{-|A^{\prime}|}=$
$\leqslant\sum_{a=1}^{t}\binom{t}{a}(\varepsilon k)^{-a}=(1+1/(\varepsilon
k))^{t}-1\leqslant e^{1/\varepsilon}.$

We used $t\leqslant k$ and $1+x\leqslant e^{x}$ in the last inequality. So we
can put $c_{\ell}:=e^{-1/\varepsilon}$ in (3).

Finally, from (4), using that $1+x\geqslant e^{x-x^{2}}$ for $|x|\leqslant
1/2$, we have

$|\mathcal{I}|\geqslant|\mathcal{F}|\cdot\prod_{\ell=0}^{\tau-1}(1+c_{\ell})=|\mathcal{F}|\cdot(1+e^{-1/\varepsilon})^{\tau}\geqslant|\mathcal{F}|\cdot\exp\big{(}\tau\cdot(e^{-1/\varepsilon}-e^{-2/\varepsilon})\big{)}\geqslant$
$|\mathcal{F}|\cdot\exp\big{(}\sqrt{k}\cdot(k^{-1/3}-k^{-2/3})\big{)}\geqslant|\mathcal{F}|\cdot
n,$

where the last inequality holds for $k$ large enough and, say, $n<k^{3}$. This
completes the proof. ∎

## References

  * [1] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics 12 (1961), N1, 313–320.
  * [2] A.J.W. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369–384.
  * [3] N. Khadžiivanov, V. Nikiforov, The Nordhaus–Stewart–Moon–Moser inequality, Serdica 4 (1978) 344–350 (in Russian).
  * [4] S. Kiselev, A. Kupavskii, Sharp bounds for the chromatic number of random Kneser graphs, arXiv:1810.01161.
  * [5] M. Kneser, Aufgabe 360, Jahresbericht der Deutschen Mathematiker-Vereinigung 2 (1955), 27.
  * [6] L. Lovasz, Kneser’s conjecture, chromatic number, and homotopy, J. Combin. Theory Ser. A, 25 (1978), N3, 319–324.
  * [7] C. Reiher, The clique density theorem, Annals of Mathematics (2016), 683–707.
  * [8] J. Spencer, Turan’s theorem for k-graphs, Discrete Math. 2 (1972), 183–186.


# Blind Super-Resolution Kernel Estimation using an Internal-GAN

Sefi Bell-Kligler Assaf Shocher Michal Irani
Dept. of Computer Science and Applied Math
The Weizmann Institute of Science, Israel
Project website: http://www.wisdom.weizmann.ac.il/$\sim$vision/kernelgan

###### Abstract

Super resolution (SR) methods typically assume that the low-resolution (LR)
image was downscaled from the unknown high-resolution (HR) image by a fixed
‘ideal’ downscaling kernel (e.g. Bicubic downscaling). However, _this is
rarely the case in real LR images_ , in contrast to synthetically generated SR
datasets. When the assumed downscaling kernel deviates from the true one, the
performance of SR methods significantly deteriorates. This gave rise to
_Blind-SR_ – namely, SR when the downscaling kernel (“SR-kernel”) is unknown.
It was further shown that the true SR-kernel is the one that maximizes the
recurrence of patches across scales of the LR image. In this paper we show how
this powerful cross-scale recurrence property can be realized using _Deep
Internal Learning_. We introduce “KernelGAN”, an image-specific _Internal-GAN_
[29], which trains solely on the LR test image at test time, and learns its
internal distribution of patches. Its _Generator_ is trained to produce a
downscaled version of the LR test image, such that its _Discriminator_ cannot
distinguish between the patch distribution of the downscaled image, and the
patch distribution of the original LR image. _The Generator, once trained,
constitutes the downscaling operation with the correct image-specific SR-
kernel_. KernelGAN is fully unsupervised, requires no training data other than
the input image itself, and leads to state-of-the-art results in Blind-SR when
plugged into existing SR algorithms. 111Project funded by the European
Research Council (ERC) under the Horizon 2020 research & innovation program
(grant No. 788535)

(a) Comparison to SotA SR methods (SR$\times 4$):
Since they train on _’ideal’ LR images_, they perform poorly on _real non-
ideal LR images_.
|  |  Bicubic |  EDSR+ |  RCAN+ |  KernelGAN(Ours) |  |  Ground Truth HR
---|---|---|---|---|---|---|---
|  LR Input image |  interpolation |  [21] |  [38] |  SR method: [30] |  |

(b) Comparison to SotA _Blind_ -SR methods (SR$\times 4$): |  |  PDN |  WDSR |  Kernel of [24] |  KernelGAN(Ours) |  |  Ground Truth HR
---|---|---|---|---|---|---|---
|  LR Input image |  [34] |  [36] |  SR method:[30] |  SR method:[30] |  |

Figure 1:  SR$\times 4$ on real ‘non-ideal’ LR images (downloaded from the
internet, or downscaled by an unknown kernel). Full images and additional
examples in supplementary material (_please zoom in on screen_).

##  1 Introduction

The basic model of SR assumes that the low-resolution input image $I_{LR}$ is
the result of down-scaling a high-resolution image $I_{HR}$ by a scaling
factor $s$ using some kernel $k_{s}$ (the "SR kernel"), namely:

$I_{LR}=\left(I_{HR}\>\boldsymbol{*}\>k_{s}\right)\downarrow_{s}$ (1)

The goal is to recover $I_{HR}$ given $I_{LR}$. This problem is ill-posed even
when the SR-Kernel is assumed known (an assumption made by most SR methods –
older [8, 32, 7] and more recent [5, 20, 19, 21, 38, 35, 12]). A boost in SR
performance was achieved in the past few years introducing Deep-Learning based
methods [5, 20, 19, 21, 38, 35, 12]. However, since most SR methods train on
synthetically downscaled images, they implicitly rely on the SR-kernel $k_{s}$
being fixed and ‘ideal’ (usually a Bicubic downscaling kernel with
antialiasing– MATLAB’s default imresize command). Real LR images, however,
rarely obey this assumption. This results in poor SR performance by state-of-
the-art (SotA) methods when applied to real or ‘non-ideal’ LR images (see Fig.
1(a)).

The SR kernel of real LR images is influenced by the sensor optics as well as
by tiny camera motion of the hand-held camera, resulting in a _different non-
ideal SR-kernel for each LR image_ , even if taken by the same sensor. It was
shown in [26] that the effect of using an incorrect SR-kernel is of greater
influence on the SR performance than any choice of an image prior. This
observation was later shown to hold also for deep-learning based priors [30].
The importance of the SR-kernel accuracy was further analyzed empirically in
[27].

The problem of SR with an unknown kernel is known as _Blind SR_. Some Blind-SR
methods [33, 17, 14, 13, 3] were introduced prior to the deep learning era.
Few Deep Blind-SR methods [34, 36] were recently presented in the NTIRE’2018
SR challenge [31]. These methods do not explicitly calculate the SR-kernel,
but propose SR networks that are robust to variations in the downscaling
kernel. A work concurrent to ours, IKC [10], performs Blind-SR by alternating
between the kernel estimation and the SR image reconstruction. A different
family of recent Deep SR methods [30, 37], while not explicitly Blind-SR,
allow to input a different _image-specific_ (pre-estimated) SR-kernel along
with the LR input image at test time. Note that _SotA (non-blind) SR methods
cannot make any use of an image-specific SR kernel at test time_ (even if
known/provided), since it is different from the fixed downscaling kernel they
trained on. These methods thus produce poor SR results in realistic scenarios
– see Fig. 1(a) (in contrast to their _excellent_ performance on synthetically
generated LR images).

The recurrence of small image patches (5x5, 7x7) across scales of a single
image, was shown to be a very strong property of natural images [8, 39].
Michaeli & Irani [24] exploited this recurrence property to estimate the
unknown SR-kernel directly from the LR input image. An important observation
they made was that the correct SR-kernel is also the downscaling kernel which
maximizes the similarity of patches across scales of the LR image. Based on
their observation, they proposed a nearest-neighbor patch based method to
estimate the kernel. However, their method tends to fail for SR scale factors
larger than $\times 2$, and has a very long runtime.

This _internal_ cross-scale recurrence property is very powerful, since it is
_image-specific_ and unsupervised (requires no prior examples). In this paper
we show how this property can be combined with the power of Deep-Learning, to
obtain the best of both worlds – _unsupervised_ SotA SR-kernel estimation,
with SotA Blind-SR results. We build upon the recent success of _Deep Internal
Learning_ [30] (training an _image-specific_ CNN on examples extracted
directly from the test image), and in particular on _Internal-GAN_ [29] – a
self-supervised GAN which learns the image-specific distribution of patches.

More specifically, we introduce "KernelGAN" – an image-specific _Internal-GAN_
, which estimates the SR kernel that best preserves the distribution of
patches across scales of the LR image. Its _Generator_ is trained to produce a
downscaled version of the LR test image, such that its _Discriminator_ cannot
distinguish between the patch distribution of the downscaled image, and the
patch distribution of the original LR image. In other words, $G$ trains to
fool $D$ to believe that all the patches of the downscaled image were actually
taken from the original one. _The Generator, once trained, constitutes the
downscaling operation with the correct image-specific SR-kernel_. KernelGAN is
fully unsupervised, requires no training data other than the input image
itself, and leads to state-of-the-art results in Blind-SR when plugged into
existing SR algorithms.

Since downscaling by the SR-kernel is a _linear_ operation applied to the LR
image (convolution and subsampling – see Eq. 1), our Generator (as opposed to
the Discriminator) is a _linear network_ (without non-linear activations). At
first glance, it may seem that a single-strided convolution layer (which stems
from Eq. 1) should suffice as a Generator. Interestingly, we found that using
a _deep linear network_ is dramatically superior to a single-strided one. This
is consistent with recent findings in theoretical deep-learning [28, 2, 18,
11], where deep linear networks were shown to have optimization advantages
over a single layer network for linear regression models. This is further
elaborated in Sec. 4.1.

Our contributions are therefore several-fold:

  * •

This is the first dataset-invariant deep-learning method to estimate the
unknown SR kernel (a critical step for true SR of _real_ LR images). KernelGAN
is fully unsupervised and requires no training data other than the input image
itself, hence enables true SR in "the wild".

  * •

KernelGAN leads to state-of-the-art results in Blind-SR when plugged into
existing SR algorithms.

  * •

To the best of our knowledge, this is the first practical use for deep
_linear_ networks (so far used mostly for theoretical analysis), with
demonstrated practical advantages.

Figure 2:  KernelGAN: The patch GAN trains on patches of a single input image
(real). $D$ tries to distinguish real patches from those generated by $G$
(fake). $G$ learns to downscale $X2$ the image while fooling $D$ i.e.
maintaining the same distribution of patches. Both networks are fully
convolutional, which in the case of images implies that each pixel in the
output is a result of a specific receptive field (i.e. patch) in the input.

##  2 Overview of the Approach

Given only the input image, our goal is to find its underlying image-specific
SR kernel. We seek the kernel that best preserves the distribution of patches
across scales of the LR image. More specifically, we aim to "generate" a
downscaled image (e.g. by a factor of 2) such that its patch distribution is
as close as possible to that of the LR image.

By matching distributions rather than individual patches, we can leverage
recent advances in distribution modeling using Generative Adversarial Networks
(GANs) [9]. GANs can be understood as a tool for distribution matching [9]. A
GAN typically learns a distribution of images in a large image dataset. It
maps examples from a source distribution, $p_{x}$, to examples
indistinguisable from a target distribution, $p_{y}$: $G:x\rightarrow y$ with
$x$$\sim$$p_{x}$, and $G(x)$$\sim$$p_{y}$. An internal GAN [29] trains on a
single input image and learns its unique internal distribution of patches.

Inspired by InGAN [29], KernelGAN is also an image specific GAN that _trains
on a single input image._ It consists of a downscaling generator ($G$) and a
discriminator ($D$) as depicted in Fig. 2. Both G and D are fully-
convolutional, which implies the network is applied to patches rather than the
whole image, as in [16]. Given an input image $I_{LR}$, $G$ learns to
downscale it, such that, for $D$, at the _patch level_ , it is
indistinguishable from the input image $I_{LR}$.

$D$ trains to output a heat map, referred to as D-map (see fig. 2) indicating
for each pixel, how likely is its surrounding patch to be drawn from the
original patch-distribution. It alternately trains on real examples (crops
from the input image) and fake ones (crops from $G$’s output). The loss is the
pixel-wise MSE difference between the output D-map and the label map. The
labels for training $D$ are a map of all ones for crops extracted from the
original LR image, and a map of all zeros for crops extracted from the
downscaled image.

We adopt a variant of the LSGAN [23] with the L1 Norm, and define the
objective of KernelGAN as:

$G^{*}(I_{LR})=\operatorname*{argmin}_{G}\max_{D}\left\\{\mathbb{E}_{x\sim\text{patches}(I_{LR})}[\left|D(x)-1\right|+\left|D(G(x)))\right|]+\mathcal{R}\right\\}$
(2)

where $\mathcal{R}$ is the regularization term on the downscaling SR-kernel
resulting from the generator $G$ (see more details in Sec. 4.2). Once
converged, the generator $G^{*}$ constitutes, implicitly, the ideal SR
downscaling function for the specific LR image.
The GAN trains for 3,000 iterations, alternating single optimization steps of
$G$ and $D$, with the ADAM optimizer ($\beta_{1}=0.5,\beta_{2}=0.999$).
Learning rate is $2e^{-4}$, decaying $\times$0.1 every 750 iters.

##  3 Discriminator

The goal of the discriminator $D$ is to learn the distribution of patches of
the input image $I_{LR}$ and discriminate between real patches belonging to
this distribution and fake patches generated by $G$. $D$’s real examples are
crops from $I_{LR}$, while fake examples are crops currently outputed by $G$.

We use a fully-convolutional patch discriminator, as introduced in [16],
applied to learn the patch distribution of a single image as in [29]. To
discriminate small image patches, we use no pooling or strides, thus achieving
a small receptive field of a 7$\times$7 patch. In this setting, $D$ is
implicitly applied to each patch separately and produces a heat-map ($D$-map)
where each location in the map corresponds to a patch from the input. The
labels for the discriminator are maps (matrices of real/fake, i.e. 1/0 labels,
respectively) of the same size as the input to the discriminator. Each pixel
in $D$-map indicates how likely is its surrounding patch to be drawn from the
learned patch distribution. See Fig. 3 for architecture details of the
discriminator.

Figure 3:  Fully Convolutional Patch Discriminator: A 7$\times$7 convolution
filter followed by six 1$\times$1 convolutions, including Spectral
normalization [25], Batch normalization [15], ReLU and a Sigmoid activations.
An input crop of 32$\times$32 results with a 32$\times$32 map$\in$ [0,1].

##  4 Deep Linear Generator = The downscaling SR-Kernel

###  4.1 Deep Linear Generator

The generator $G$ constitutes the downscaling model. Since downscaling by
convolution and subsampling is a _linear_ transform (Fig. 1), we use a
_linear_ Generator (without any non-linear activations). We refer to the model
of downscaling from Eq. 1. In principle, the expressiveness of a single
strided convolutional layer should cover all possible downscaling methods
captured by Eq. 1. However, we empirically found that such architecture does
not converge to the correct solution (see 6). We attribute this behavior to
the following _conjecture_ : A generator consisting of a single layer has
exactly one set of parameters for the correct solution (the set of weights
that make the ground-truth kernel). This means that there is only one point on
the optimization surface that is acceptable as a solution and it is the global
minimum. Achieving such a global minimum is easy when the loss function is
convex (as in linear regression). But in our case the overall loss function is
a non-linear neural network- $D$ which is highly non-convex. In such case, the
probability for getting from some random initial state to the global minimum
using gradient based methods is negligible. In contrast to a single layer,
standard _(_ deep) neural networks are assumed to converge from a random
initialization due to the fact that there are many good local minima and
negligibly few bad local minima [6, 18]. Hence, for a problem that by
definition has one valid solution, optimizing a single layer generator is
impossible.

A non-linear generator would not be suitable either. Without an explicit
constraint on $G$ to be linear, it will generate physically unwanted solutions
for the optimization objective. Such solutions include generating any image
that contains valid patches but has no downscaling relation (Eq. 1). One
example is generating a tile of just several patches from the input. This
would be a solution that complies with eq. 2 but is unwanted.

This conjecture motivated us to use deep linear networks. These are networks
consisting of a sequence of linear layers with _no activations_ , and are used
for theoretical analysis [28, 2, 18, 11]. The expressiveness of a deep linear
network is exactly as the one of a single linear layer (i.e. Linear
regression), however, its optimization has several different aspects. While it
can be convex with respect to the input, the loss would never be convex with
respect to the weights (assuming more than one layer). In fact, linear
networks have infinitely many equally valued global minima. Any choice of
network parameters matching to one of these minima would be equivalent to any
other minimum point- they are just different factorizations of the same
matrix. Motivated by these observations, we employ a deep linear generator. By
that we allow infinitely many valid solutions to our optimization objective,
all equivalent to the same linear solution. Furthermore, it was shown by [2],
that gradient-based optimization is faster for deeper linear networks than
shallow ones.

Fig. 4 depicts the architecture of $G$. We use 5 hidden convolutional layers
with 64 channels each. The first 3 filters are 7$\times$7, 5$\times$5,
3$\times$3 and the rest are 1$\times$1\. This makes a receptive field of 13
$\times$13 (allowing for a 13 $\times$ 13 SR kernel). This setting of filters
takes into account the effective receptive field [22]; maintaining the same
receptive field while having filters bigger than 1$\times$1 following the
first layer encourages the center of the kernel to have higher values. To
provide a reasonable initial starting point, the generator’s output is
constrained to be similar to an ideal downscaling (e.g. bicubic) of the input,
for the first iterations. Once satisfied, this constraint is discarded.

###  4.2 Extracting the explicit kernel

At any iteration during the training, the generator $G$ constitutes the
_currently_ estimated downscaling operation for the specific LR input image.
The image-specific kernel is implicitly captured by the trained weights of
$G$. However, there are two reasons to explicitly extract the kernel from $G$.
First, we are interested in having a compact downscaling convolution kernel
rather than a downscaling network. This step is trivial; convolving all the
filters of $G$ sequentially with sride 1 results in the SR-kernel $k$ (see
Fig. 4). When extracted, the kernel is just a small array that can be supplied
to SR algorithms. The second reason for explicitly extracting the kernel is to
allow applying explicit and physically-meaningful priors on the kernel. This
is the goal of the regularization term $\mathcal{R}$ in Eq.2 which decreases
the hypotheses space to a sub-set of the plausible kernels, that obey certain
restrictions. Such restrictions are that the kernel would sum up to 1 and be
centered so it will not shift the image. The regularization also ameliorates
faulty tendencies of the optimization process to produce kernels that are too
spread out and smooth. However, it is not enough to extract the kernel, this
extraction must be differentiable so that the regularization losses can be
back-propagated through it. At each iteration, we apply a differentiable
action of calculating the kernel (convolving all the filters of $G$
sequentially with stride-1). The regularization loss term $\mathcal{R}$ is
then applied and included in the optimization objective.

The regularization term in our objective in eq. 2 is the following:

$\mathcal{R}=\alpha\mathcal{L}_{sum\\_to\\_1}+\beta\mathcal{L}_{boundaries}+\gamma\mathcal{L}_{sparse}+\delta\mathcal{L}_{center}\vspace*{-0.11cm}$
(3)

where $\alpha=0.5$, $\beta=0.5$, $\gamma=5$, $\delta=1$, and:

  * •

$\mathcal{L}_{sum\\_to\\_1}=\left|1-\sum_{i,j}k_{i,j}\right|$ encourages $k$
to sum to 1.

  * •

$\mathcal{L}_{boundaries}=\sum_{i,j}\left|k_{i,j}\cdot m_{i,j}\right|$
penalizing non-zero values close to the boundaries. $m$ is a constant mask of
weights exponentially growing with distance from the center of $k$.

  * •

$\mathcal{L}_{sparse}=\sum_{i,j}\left|k_{i,j}\right|^{\nicefrac{{1}}{{2}}}$
encourages sparsity to prevent the network from oversmoothing kernels.

  * •

$\mathcal{L}_{center}=\left\lVert\left(x_{0},y_{0}\right)-\frac{\sum_{i,j}{k_{i,j}\cdot\left(i,j\right)}}{\sum_{i,j}k_{i,j}}\right\rVert_{2}$
encourages $k$’s center of mass to be at the center of the kernel, where
($x_{0},y_{0}$) denote the center indices.

SR kernels are not only image specific, but also depend on the desired scale-
factor $s$. However, there is a simple relation between SR-kernels of
different scales. We are thus able to obtain a kernel for SR $\times$4 from
$G$ that was trained to downscale by $\times$2\. This is advantageous for two
reasons: First, it allows extracting kernels for various scales by one run of
KernelGAN. Second, it prevents downscaling the LR image too much. Small LR
images downscaled by a scale factor of 4 may result in tiny images ($\times$16
smaller than the HR image) which may not contain enough data to train on.
KernelGAN is trained to estimate a kernel $k_{2}$ for a scale-factor of 2. It
is easy to show that the kernel for a scale factor of 4, i.e. $k_{4}$, can be
analytically calculated by requiring:
$I_{LR}\boldsymbol{*}k_{4}\downarrow_{4}=(I_{LR}\boldsymbol{*}k_{2}\downarrow_{2})\boldsymbol{*}k_{2}\downarrow_{2}$.
It implies that $k_{4}=k_{2}\>\boldsymbol{*}\>k_{2\\_dilated}$ , where
$k_{2\\_dilated}[n_{1},n_{2}]=\begin{cases}k_{2}\left[\frac{n_{1}}{2},\frac{n_{2}}{2}\right]\quad&n_{1},n_{2}\textrm{\>
even}\\\ 0\quad&\textrm{else}\\\ \end{cases}$
For a mathematical proof of the above derivation, as well as an ablation study
of the various kernel constraints – see our  project website.

Figure 4:  Deep linear G: A 6 layer convolutional network without non-linear
activations.
The deep linear network on the left has equal expressiveness power as the
single strided convolution downscaling model, on the right.
Figure 5:  SR kernel estimation: We compare ground truth kernel, Michaeli and
Irani [24] and KernelGAN (ours). PSNR of ZSSR [30], when supplied with those
kernels, is noted in the bottom right of each kernel, emphasizing the
significance of kernel estimation accuracy. Our method outperforms [24] in SR
performance (as well as in visual similarity to ground truth SR kernel)

| Method |  $\times$2 |  $\times$4
---|---|---|---
Class 1: | Bicubic Interpolation | 28.731 / 0.8040 | 25.330 / 0.6795
SotA SR algorithms |  Bicubic kernel + ZSSR [30] | 29.102 / 0.8215 | 25.605 / 0.6911
(trained on bicubically |  EDSRplus [21] | 29.172 / 0.8216 | 25.638 / 0.6928
downscaled images) |  RCANplus [38] | 29.198 / 0.8223 | 25.659 / 0.6936
Class 2: |  PDN [34] \- 1st in NTIRE track4 | - |  26.340 / 0.7190
Blind-SR |  WDSR [36] \- 1st in NTIRE track2 | - | 21.546 / 0.6841
NTIRE’18 [31] |  WDSR [36] \- 1st in NTIRE track3 | - | 21.539 / 0.7016
winners |  WDSR [36] \- 2nd in NTIRE track4 | - | 25.636 / 0.7144
Class 3: |  Michaeli & Irani [24] \+ SRMD [37] | 25.511 / 0.8083 | 23.335 / 0.6530
kernel estimation |  Michaeli & Irani [24] \+ ZSSR [30] | 29.368 / 0.8370 | 26.080 / 0.7138
+ |  KernelGAN (Ours) \+ SRMD [37] |  29.565 / 0.8564 |  25.711 / 0.7265
non Blind-SR algorithm |  KernelGAN (Ours) \+ ZSSR [30] |  30.363 / 0.8669 |  26.810 / 0.7316
Class 4: |  Ground-truth kernel + SRMD [37] | 31.962 / 0.8955 | 27.375 / 0.7655
Upper bound |  Ground-truth kernel + ZSSR [30] | 32.436 / 0.8992 | 27.527 / 0.7446
Table 1: _SotA SR performance (PSNR(dB) / SSIM) on 100 images of DIV2KRK (sec.
5.2) . Red indicates the best performance, blue indicates second best._

##  5 Experiments and results

We evaluated our method on real LR images, as well as on ‘non-ideal’
synthetically generated LR images with ground-truth (both ground-truth HR
images, as well as the true SR-kernels).

###  5.1 Evaluation Method

The performance of our method is analyzed in 2 ways: _Kernel estimation_
accuracy and _SR performance_. The latter is done both visually (see fig. 1(a)
and supplementary material), and empirically on the synthetic dataset
analyzing PSNR and SSIM measurements (Table 1). Evaluation is done using the
script provided by [19] and used by many works, including [30, 20, 21]. For
evaluation of the kernel estimation we chose two non-blind SR algorithms that
accept a SR-kernel as input [30, 37], provide them with different kernels
(bicubic, ground truth SR-kernel, ours and [30]) and compared their SR
performance. We present four types (categories) of algorithms for the
analysis:

  * •

_Type 1_ includes the non-blind SotA SR methods trained on bicubically
downscaled images.

  * •

_Type 2_ are the winners of the NTIRE’2018 Blind-SR challenge [31].

  * •

_Type 3_ consists of combinations of 2 methods for SR-kernel estimation, [24]
and ours, and 2 non-blind SR methods, [30, 37], that regard the estimated
kernel as input. This combination is itself, a full Blind-SR algorithm.

  * •

_Type 4_ , is again the combination above, only with the use of the ground
truth SR-kernel, thus providing an upper bound to _Type 3_.

When providing a kernel to ZSSR [30] (whether ours, [24]’s, ground-truth
kernel), we provide both the $\times$2 and $\times$4 kernels, in order to
exploit the gradual process of ZSSR (using 2 sequential SR steps).

We compare our kernel estimation to Michaeli & Irani [24] which, to the best
of our knowledge, is the leading method for SR-kernel estimation from a single
image.

###  5.2 Dataset for Blind-SR

There is no adequate dataset for quantitatively evaluating Blind-SR. The data
used in the NTIRE’2018 Blind-SR challenge [31] has an inherent problem; it
suffers from sub-pixel misalignments between the LR image and the HR ground
truth, resulting in subpixel misalignments between the reconstructed SR images
and the HR ground truth images. Such small misalignments are known to prefer
(i.e. give lower error to) blurry images over sharp ones. A different
benchmark suggested by [4] is not yet available, and is only restricted to 3
SR blur kernels. As a result, we generated a new Blind-SR benchmark, referred
to as _DIV2KRK_ (DIV2K random kernel).

Using the validation set (100 images) from the widely used DIV2K [1] dataset,
we blurred and subsampled each image with a different, randomly generated
kernel. Kernels were 11x11 anisotropic gaussians with random lengths
$\lambda_{1},\lambda_{2}\mathtt{\sim}\mathcal{U}(0.6,5)$ independently
distributed for each axis, rotated by a random angle
$\theta\mathtt{\sim}\mathcal{U}[-\pi,\pi]$. To deviate from a regular
gaussian, we further apply uniform multiplicative noise (up to 25% of each
pixel value of the kernel) and normalize it to sum to one. See Figs. 5 and 6
for a few such examples. Data and reproduction code are available on  project
website.

###  5.3 Results

Our method together with ZSSR [30] outperforms SotA SR results visually and
numerically by a large margin of 1dB and 0.47dB for scales $\times$2 and
$\times$4 respectively. When the kernel deviates from bicubic, as in _DIV2KRK_
and real images, _Type 1_ , SotA SR, tends to produce blurry results (often
comparable to naive bicubic interpolation), and highlights undesired artifacts
(e.g. JPEG compression), such examples are shown in Fig. 1(a). _Type 2_ , i.e.
SotA Blind-SR methods, produce significantly better quantitative results, than
_Type 1_. Although visually (as shown in Fig. 1(b)), tend to over-smooth
patterns and over-sharpen edges in an artificial and graphical manner.

Our SR-kernel estimation, plugged into ZSSR [30], shows superior results over
both types by a large margin of 1.1dB, 0.47dB for scales $\times$2, $\times 4$
respectively, and visually recovering small details from the LR image as shown
in Fig 1. Although, our kernel together with [37] did not perform as well for
scale $\times 4$, ranking lower than [34] in PSNR (but higher in SSIM).

Regarding SR-kernel estimation, we analyze _Type 3_. When fixing a SR
algorithm, our kernel estimation outperforms [24] visually, as seen in Fig.
1(b), and quantitatively by 1dB, 0.73dB when plugged in [30] and 4dB, 2.3dB
when plugged in [37] for scales $\times 2$, $\times 4$ respectively.

The superiority of _Type 3_ and _Type 4_ (as shown in Table 1) shows
empirically the importance of performing SR with regard to the image specific
SR-kernel. Moreover, using a SR algorithm with different SR-kernels leads to
significantly different results, demonstrating the importance of the SR-kernel
accuracy. This is also shown in Fig. 5 with a large difference in PSNR while
small (but visible) difference in the estimated kernel. For more visual
results+comparisons see  project website.

Run-time: Network training is done during test time. There is no actual
inference step since the trained $G$ implicitly contains the resulting SR-
kernel. Runtime is _61 or 102 seconds_ per image on a single _Tesla V-100 or
Tesla K-80_ GPU, respectively. Runtime is independent both of image size and
scale factor, since the GAN analyzes patches rather than the whole image.
Since the same kernel applies to the entire image, analyzing a fixed number of
crops suffices to estimate the kernel. Fixed sized image crops (64$\times$64
to $G$, and accordingly 32$\times$32 to D) are randomly selected _with
probability proportional to their gradient content_. KernelGAN first estimates
the $\times$2 SR-kernel, and then derives analytically kernels for other
scales (e.g., $\times$4).  For comparison, [24] runs 45 minutes per image on
our _DIV2KRK_ and time consumption grows with image size.

Figure 6:  Depth is of the essence for the linear network: The deep linear
generator outperforms the single layer version by 3.8dB and 1.6dB for $\times
2$ and $\times 4$ over DIV2KRK. Kernel examples emphasize superiority of the
deep linear network.

##  6 Conclusion

We present significant progress towards real-world SR (i.e., Blind-SR), by
estimating an image-specific SR-kernel based on the LR image alone. This is
done via an image-specific internal-GAN, which trains solely on the LR input
image, and learns its internal distribution of patches without requiring any
prior examples. This gives rise to true SR "in the wild". We show both
visually and quantitatively that when our kernel estimation is provided to
existing off-the-shelf non-blind SR algorithms, it leads to SotA SR results,
by a large margin.

## References

  * [1] Eirikur Agustsson and Radu Timofte.  Ntire 2017 challenge on single image super-resolution: Dataset and study.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [2] Sanjeev Arora, Nadav Cohen, and Elad Hazan.  On the optimization of deep networks: Implicit acceleration by overparameterization.  In Jennifer G. Dy and Andreas Krause, editors, ICML, volume 80 of Proceedings of Machine Learning Research, pages 244–253. PMLR, 2018\.
  * [3] Isabelle Begin and Frank P. Ferrie.  Blind super-resolution using a learning-based approach.  In International Conference on Pattern Recognition, ICPR ’04, Washington, DC, USA, 2004. IEEE Computer Society.
  * [4] Jianrui Cai, Hui Zeng, Hongwei Yong, Zisheng Cao, and Lei Zhang.  Toward real-world single image super-resolution: A new benchmark and a new model, 2019.
  * [5] Kaiming He Xiaoou Tang Chao Dong, Chen Change Loy.  Learning a deep convolutional network for image super-resolution.  In European Conference on Computer Vision (ECCV), 2014.
  * [6] Anna Choromanska, MIkael Henaff, Michael Mathieu, Gerard Ben Arous, and Yann LeCun.  The Loss Surfaces of Multilayer Networks.  In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, volume 38 of Proceedings of Machine Learning Research, pages 192–204, San Diego, California, USA, 09–12 May 2015. PMLR.
  * [7] Gilad Freedman and Raanan Fattal.  Image and video upscaling from local self-examples.  ACM Trans. Graph., April 2011.
  * [8] Daniel Glasner, Shai Bagon, and Michal Irani.  Super-resolution from a single image.  In ICCV, 2009.
  * [9] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2672–2680. Curran Associates, Inc., 2014.
  * [10] Jinjin Gu, Hannan Lu, Wangmeng Zuo, and Chao Dong.  Blind super-resolution with iterative kernel correction.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2019.
  * [11] Moritz Hardt and Tengyu Ma.  Identity matters in deep learning.  CoRR, abs/1611.04231, 2016.
  * [12] Muhammad Haris, Greg Shakhnarovich, and Norimichi Ukita.  Deep back-projection networks for super-resolution.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [13] He He and Wan-Chi Siu.  Single image super-resolution using gaussian process regression.  In Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR ’11, pages 449–456, Washington, DC, USA, 2011\. IEEE Computer Society.
  * [14] Yu He, Kim-Hui Yap, Li Chen, and Lap-Pui Chau.  A soft map framework for blind super-resolution image reconstruction.  Image Vision Comput., 27(4):364–373, March 2009.
  * [15] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, pages 448–456. JMLR.org, 2015.
  * [16] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A Efros.  Image-to-image translation with conditional adversarial networks.  The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [17] Neel Joshi, Richard Szeliski, and David J. Kriegman.  Psf estimation using sharp edge prediction.  2008 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8, 2008.
  * [18] Kenji Kawaguchi.  Deep learning without poor local minima.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 586–594. Curran Associates, Inc., 2016.
  * [19] Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee.  Accurate image super-resolution using very deep convolutional networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, pages 1646–1654, 06 2016.
  * [20] Jiwon Kim, Jung Kwon Lee, and Kyoung Mu Lee.  Deeply-recursive convolutional network for image super-resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR Oral), June 2016.
  * [21] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super-resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [22] Wenjie Luo, Yujia Li, Raquel Urtasun, and Richard Zemel.  Understanding the effective receptive field in deep convolutional neural networks.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 4898–4906. Curran Associates, Inc., 2016.
  * [23] Xudong Mao, Qing Li, Haoran Xie, Raymond Y. K. Lau, and Zhen Wang.  Least squares generative adversarial networks.  In Computer Vision (ICCV), IEEE International Conference on, 2017\.
  * [24] T. Michaeli and M. Irani.  Nonparametric blind super-resolution.  In International Conference on Computer Vision (ICCV), 2013.
  * [25] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida.  Spectral normalization for generative adversarial networks.  In International Conference on Learning Representations, 2018.
  * [26] Alexander Apartsin Boaz Nadler Anat levin Netalee Efrat, Daniel Glasner.  Accurate blur models vs. image priors in single image super-resolution.  In ICCV, 2013.
  * [27] G. Riegler, S. Schulter, M. Rüther, and H. Bischof.  Conditioned regression models for non-blind single image super-resolution.  In 2015 IEEE International Conference on Computer Vision (ICCV), pages 522–530, Dec 2015.
  * [28] Andrew M. Saxe, James L. McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks, 2013.
  * [29] Assaf Shocher, Shai Bagon, Phillip Isola, and Michal Irani.  Ingan: Capturing and remapping the “dna” of a natural image.  In arXiv, 2019.
  * [30] Assaf Shocher, Nadav Cohen, and Michal Irani.  Zero-shot super-resolution using deep internal learning.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [31] Radu Timofte, Shuhang Gu, Jiqing Wu, Luc Van Gool, Lei Zhang, Ming-Hsuan Yang, Muhammad Haris, et al.  Ntire 2018 challenge on single image super-resolution: Methods and results.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, June 2018.
  * [32] Radu Timofte, Vincent De Smet, and Luc Van Gool.  A+: Adjusted anchored neighborhood regression for fast super-resolution.  In ACCV, 2014.
  * [33] Qiang Wang, Xiaoou Tang, and Harry Shum.  Patch based blind image super resolution.  In Proceedings of the Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1 - Volume 01, ICCV ’05, pages 709–716, Washington, DC, USA, 2005. IEEE Computer Society.
  * [34] Wang Xintao, Yu Ke, Hui Tak-Wai, Dong Chao, Lin Liang, and Change Loy Chen.  Deep poly-dense network for image superresolution.  NTIRE challenge, 2018.
  * [35] W. Yifan, F. Perazzi, B. McWilliams, A. Sorkine-Hornung, O Sorkine-Hornung, and C. Schroers.  A fully progressive approach to single-image super-resolution.  In CVPR Workshops, June 2018.
  * [36] Jiahui Yu, Yuchen Fan, Jianchao Yang, Ning Xu, Zhaowen Wang, Xinchao Wang, and Thomas S. Huang.  Wide activation for efficient and accurate image super-resolution.  CoRR, abs/1808.08718, 2018.
  * [37] Kai Zhang, Wangmeng Zuo, and Lei Zhang.  Learning a single convolutional super-resolution network for multiple degradations.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 3262–3271, 2018.
  * [38] Yulun Zhang, Kunpeng Li, Kai Li, Lichen Wang, Bineng Zhong, and Yun Fu.  Image super-resolution using very deep residual channel attention networks.  In ECCV, 2018.
  * [39] Maria Zontak and Michal Irani.  Internal statistics of a single natural image.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011.