# Chromatic number is not tournament-local

António Girão  Mathematical Institute, University of Oxford, UK
<EMAIL_ADDRESS>,  Kevin Hendrey  Institute for Basic
Science, Daejeon, South Korea<EMAIL_ADDRESS>,  Freddie Illingworth
Mathematical Institute, University of Oxford, UK Department of Mathematics,
University College London, UK<EMAIL_ADDRESS>,  Florian Lehner
Department of Mathematics, University of Auckland, New Zealand
<EMAIL_ADDRESS>,  Lukas Michel  ,  Michael Savery  Heilbronn
Institute for Mathematical Research, Bristol, UK  and  Raphael Steiner
Institute of Theoretical Computer Science, ETH Zürich, Switzerland
<EMAIL_ADDRESS>
###### Abstract.

Scott and Seymour conjectured the existence of a function
$f\colon\mathbb{N}\to\mathbb{N}$ such that, for every graph $G$ and tournament
$T$ on the same vertex set, $\chi(G)\geqslant f(k)$ implies that
$\chi(G[N_{T}^{+}(v)])\geqslant k$ for some vertex $v$. In this note we
disprove this conjecture even if $v$ is replaced by a vertex set of size
$\mathcal{O}(\log{\lvert V(G)\rvert})$. As a consequence, we answer in the
negative a question of Harutyunyan, Le, Thomassé, and Wu concerning the
corresponding statement where the graph $G$ is replaced by another tournament,
and disprove a related conjecture of Nguyen, Scott, and Seymour. We also show
that the setting where chromatic number is replaced by degeneracy exhibits a
quite different behaviour.

A.G. and F.I. were supported by EPSRC grant EP/V007327/1. F.I. and F.L. were
supported by MATRIX-Simons travel grants. L.M. and M.S. were supported by
MATRIX travel grants. R.S. was supported by an ETH Zürich Postdoctoral
Fellowship. K.H. was supported by the Institute for Basic Science
(IBS-R029-C1).

##  1\. Introduction

The question of what structures must appear in graphs of large chromatic
number is one of the most fundamental in modern graph theory. One obvious
reason for a graph to have high chromatic number is the presence of a large
clique, but constructions from the 1940s and 50s of, for example, Tutte
[Des54] and Zykov [Zyk49] demonstrate the existence of triangle-free graphs of
arbitrarily large chromatic number. In particular, there are graphs with
arbitrarily large chromatic number in which every neighbourhood is independent
(and hence $1$-colourable).

Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour, and Thomassé
[BCC+13] conjectured that the analogous phenomenon does not occur in
tournaments. This was confirmed recently in a beautiful paper of Harutyunyan,
Le, Thomassé, and Wu [HLTW19] in which they showed that for every $k$ there
exists an $f(k)$ such that every tournament with chromatic number111The
_chromatic number_ , $\chi(T)$, of a tournament $T$ is the least $k$ for which
there is a partition of $V(T)$ into $k$ parts each of which induces a
transitive (acyclic) subtournament of $T$. at least $f(k)$ contains a vertex
$v$ such that $\chi(T[N^{+}(v)])\geqslant k$.

Separately, Scott and Seymour [SS16] (see also [HLTW19, Conj. 7]) conjectured
a similar result for a graph and a tournament on the same vertex set.

######  Conjecture 1 (Scott and Seymour).

For every positive integer $k$ there exists a $\chi$ such that, for every
graph $G$ with $\chi(G)\geqslant\chi$ and every tournament $T$ on the same
vertex set, there is a vertex $v$ such that $\chi(G[N_{T}^{+}(v)])\geqslant
k$.

This conjecture is supported by the observation [SS16] that the statement
holds when chromatic number is replaced by fractional chromatic number (see
Section 4 for more details). The main result of this note is a disproof of 1
for $k\geqslant 3$. In fact, we prove something stronger: $G$ and $T$ may be
chosen such that the out-neighbourhood222The _out-neighbourhood_ , $N^{+}(S)$,
of a set $S$ is $\bigcup_{v\in S}N^{+}(v)$. This might contain vertices of
$S$. of any set of size at most $\frac{\log{\lvert V(T)\rvert}}{2\chi^{2}}$ is
bipartite.

######  Theorem 2.

For every positive integer $\chi$ there are arbitrarily large $N$ for which
there is a graph $G$ and a tournament $T$ on the same $N$-vertex set such that
$\chi(G)=\chi$ and, for every set $U$ of at most $\frac{\log{N}}{2\chi^{2}}$
vertices, $\chi(G[N_{T}^{+}(U)])\leqslant 2$.

We will show that $G$ can in fact be taken to be triangle-free which will be
useful for our proof of Corollary 3. We make two remarks concerning the
optimality of Theorem 2.

  * •

It is not possible to replace 2 by 1 in the bound on the chromatic number of
the out-neighbourhood, even when $U$ consists of a single vertex. Indeed,
suppose that $G[N_{T}^{+}(v)]$ is independent for every vertex $v$. Let $xy$
be an edge of $G$. No out-neighbourhood of a vertex of $T$ can contain both
$x$ and $y$, so $\\{x,y\\}$ dominates $T$. But then $G$ is 3-colourable: one
colour for each of $N_{T}^{+}(x)$ and $N_{T}^{+}(y)$, and a final colour for
whichever of $x$ and $y$ has not been coloured.

  * •

The bound on the size of $U$ is very close to being best possible. Let $S$ be
a dominating set of $T$ of size at most $\lceil\log_{2}{N}\rceil$ (such a set
can be constructed greedily). Then $N^{+}(S)$ contains all vertices of $G$
except perhaps one and so, for any $0\leqslant\ell\leqslant\chi-2$, there is
some $U\subseteq S$ of size at most
$\lceil\log_{2}(N)/\lfloor\frac{\chi-2}{\ell}\rfloor\rceil$ with
$\chi(G[N_{T}^{+}(U)])>\ell$.

Theorem 2 has the following corollary, which resolves in a strong sense a
question of Harutyunyan, Le, Thomassé, and Wu [HLTW19] concerning the
analogous problem for two tournaments on the same vertex set.

######  Corollary 3.

For every positive integer $\chi$ there are arbitrarily large $N$ for which
there are tournaments $T_{1}$ and $T_{2}$ on the same $N$-vertex set such that
$\chi(T_{1})=\chi$ and, for every set $U$ of at most
$\frac{\log{N}}{8\chi^{2}}$ vertices, $\chi(T_{1}[N_{T_{2}}^{+}(U)])\leqslant
2$.

In turn, Corollary 3 has the following immediate consequence which disproves a
conjecture of Nguyen, Scott, and Seymour [NSS23, 3.4].

######  Corollary 4.

For every positive integer $\chi$ there are arbitrarily large $N$ for which
there is an $N$-vertex tournament $T$ and disjoint subsets $A,B\subseteq V(T)$
such that $\chi(T[A]),\chi(T[B])\geqslant\chi$ and the following holds. For
all $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ of size at most
$\frac{\log{N}}{32\chi^{2}}$, both $\chi(A\cap N^{+}(B^{\prime}))$ and
$\chi(B\cap N^{+}(A^{\prime}))$ are at most $2$.

Finally, we include two results for the setting where chromatic number is
replaced by degeneracy (or equivalently maximum average degree). Since every
graph of high chromatic number has high degeneracy, Theorem 2 shows that for
every positive integer $d$ there is a graph $G$ and a tournament $T$ on the
same vertex set such that the degeneracy of $G$ is at least $d$, but the
subgraph of $G$ induced on each out-neighbourhood of $T$ is bipartite. Our
next result strengthens this statement by ensuring that the graph induced on
the out-neighbourhood is 1-degenerate.

######  Proposition 5.

For every positive integer $k$, there is a $k$-regular graph $G$ and a
tournament $T$ on the same vertex set such that $G[N_{T}^{+}(v)]$ is a forest
for every vertex $v$.

Despite this result, and in contrast to Theorem 2, if $G$ has high degeneracy
and $T$ is a tournament on the same vertex set, then there is a two-vertex set
whose out-neighbourhood has high degeneracy.

######  Theorem 6.

For every positive integer $k$, every graph $G$ with degeneracy at least
$12k$, and every tournament $T$ on the same vertex set, there exist vertices
$x,y$ such that $G[N^{+}(\\{x,y\\})]$ has degeneracy at least $k-1$.

##  2\. Proofs of the main theorems

In this section we present the proof of Theorem 2. Our construction is based
on the classical _Schrijver graphs_ [Sch78].

######  Definition 7.

Let $k\geqslant 1$ and $n\geqslant 2k$ be integers. The _Kneser graph_
$\operatorname{\textup{{KG}}}(n,k)$ is the graph whose vertex set is
$\binom{[n]}{k}$ and in which two distinct sets $S_{1},S_{2}\in\binom{[n]}{k}$
are adjacent if and only if $S_{1}\cap S_{2}=\varnothing$. The _Schrijver
graph_ $\operatorname{\textup{{SG}}}(n,k)$ is the induced subgraph of
$\operatorname{\textup{{KG}}}(n,k)$ whose vertex set consists of all stable
sets in $\binom{[n]}{k}$. Here, a set $S\in\binom{[n]}{k}$ is called _stable_
if it does not include two cyclically consecutive333By this we mean a pair
$i,i+1$ where $1\leqslant i<n$ or the pair $n,1$. elements of $[n]$.

Kneser [Kne55] conjectured that the chromatic number of
$\operatorname{\textup{{KG}}}(n,k)$ is $n-2k+2$. This conjecture remained open
for two decades and was first proved by Lovász [Lov78] using homotopy theory
(see also Bárány [Bár78] and Greene [Gre02] for very short proofs). Shortly
afterwards, Schrijver [Sch78] introduced the graphs
$\operatorname{\textup{{SG}}}(n,k)$ and proved that
$\operatorname{\textup{{SG}}}(n,k)$ is vertex-critical with chromatic number
$\chi(\operatorname{\textup{{SG}}}(n,k))=\chi(\operatorname{\textup{{KG}}}(n,k))=n-2k+2$.

To prove Theorem 2, we will show that for every integer $\chi\geqslant 3$ and
every sufficiently large integer $k$ there exists a tournament $T$ on the same
vertex set as $\operatorname{\textup{{SG}}}(2k+\chi-2,k)$ such that for every
$U\subseteq V(T)$ which is sufficiently small, the out-neighbourhood of $U$ in
$T$ induces a bipartite subgraph of
$\operatorname{\textup{{SG}}}(2k+\chi-2,k)$. As
$\chi(\operatorname{\textup{{SG}}}(2k+\chi-2,k))=\chi$, this will prove
Theorem 2.

In constructing our tournament, we rely on the following combinatorial
statement which follows directly from the existence of tournaments with high
domination number.

######  Lemma 8.

For every positive integer $t$ there is some $n_{0}$ such that for all
integers $n\geqslant n_{0}$ there exists a function $f\colon\binom{[n]}{t}\to
2^{[n]}$ with the following two properties:

  * •

for every $A,B\in\binom{[n]}{t}$, at least one of $A\cap f(B)$ and $B\cap
f(A)$ is empty, and

  * •

for every collection $(A_{i})_{i\in I}$ of at most $\frac{\log{n}}{2t}$ sets
from $\binom{[n]}{t}$,

$\bigcap_{i\in I}f(A_{i})\neq\varnothing.$

###### Proof.

By a classical result of Erdős [Erd63] (see [GS71] for an explicit
construction), for every sufficiently large $n$ there is an $n$-vertex
tournament in which every set of at most $\log(n)/2$ vertices is dominated by
a vertex outside the set. Let $n$ be large enough that this result holds and
that $\log(n)/2\geqslant t$, and let $T$ be the corresponding tournament.
Identify $V(T)$ with $[n]$ and, for $A\in\binom{[n]}{t}$, define $f(A)$ as

$f(A)\coloneqq\\{v\in[n]\setminus A\colon v\text{ dominates }A\\}.$

We claim $f$ satisfies the two properties of the lemma statement. Firstly, let
$A,B\in\binom{[n]}{t}$ and suppose for a contradiction that $A\cap f(B)$ and
$B\cap f(A)$ are both non-empty. Then there is some $a\in A\setminus B$ that
dominates $B$ and some $b\in B\setminus A$ that dominates $A$. This implies
that $a$ and $b$ are distinct, and the edge between them is oriented in both
directions, which is a contradiction. Next, let $(A_{i})_{i\in I}$ be a
collection of at most $\frac{\log{n}}{2t}$ sets from $\binom{[n]}{t}$. Let
$A=\bigcup_{i\in I}A_{i}$ which is a set of size at most $\log(n)/2$. By the
definition of $T$ some vertex $x\not\in A$ dominates $A$, but then
$x\in\bigcap_{i\in I}f(A_{i})$, as required. ∎

Before giving the proof of Theorem 2, let us fix the following notation: for a
set $S\in\binom{[n]}{k}$, we denote by $\operatorname{\textup{{gap}}}(S)$ the
set of “left-elements” of cyclically consecutive pairs of $[n]$ that are
disjoint from $S$. Concretely, $r\in\operatorname{\textup{{gap}}}(S)$ if and
only if $\\{r,r+1\\}\cap S=\varnothing$, where addition is to be understood
modulo $n$ (that is, $n+1$ is identified with $1$). Pause to note that every
stable set $S\subseteq[n]$ of size $k$ (that is, every vertex of the Schrijver
graph $\operatorname{\textup{{SG}}}(n,k)$) satisfies
$\lvert\operatorname{\textup{{gap}}}(S)\rvert=n-2k$. Every
$S\in\binom{[n]}{k}$ can be recovered from $\operatorname{\textup{{gap}}}(S)$
and so $\lvert
V(\operatorname{\textup{{SG}}}(n,k))\rvert\leqslant\binom{n}{n-2k}$.

###### Proof of Theorem 2.

The result is trivial for $\chi\leqslant 2$, so let $\chi\geqslant 3$ be an
integer, $t\coloneqq\chi-2$, and $n_{0}$ be as given by Lemma 8. Pick some
positive integer $k>t$ such that $2k+t\geqslant n_{0}$, set $n\coloneqq 2k+t$,
and set $G\coloneqq\operatorname{\textup{{SG}}}(n,k)$. Note that $G$ is
triangle-free, has chromatic number $\chi$ and, for any $S\in
V(\operatorname{\textup{{SG}}}(n,k))$,
$\operatorname{\textup{{gap}}}(S)\in\binom{[n]}{t}$. Hence, $N\coloneqq\lvert
V(\operatorname{\textup{{SG}}}(n,k))\rvert\leqslant\binom{n}{t}\leqslant
n^{t}$.

Let $f\colon\binom{[n]}{t}\to 2^{[n]}$ be the function from Lemma 8. Define a
directed graph $D$ on the same vertex set as $G$ that has a directed edge from
a vertex $S_{1}$ to a vertex $S_{2}$ if and only if
$f(\operatorname{\textup{{gap}}}(S_{1}))\cap\operatorname{\textup{{gap}}}(S_{2})=\varnothing$.
Note, by the first property of $f$ guaranteed by Lemma 8, that any two
distinct vertices of $D$ are connected by an arc in at least one of the two
possible directions. Hence, there exists a spanning subdigraph $T$ of $D$
which is a tournament.

Let $U$ be any set of at most
$\frac{\log{N}}{2\chi^{2}}\leqslant\frac{\log{N}}{2t^{2}}\leqslant\frac{\log{n}}{2t}$
vertices. To finish the proof we will show that the out-neighbourhood
$N_{D}^{+}(U)$ induces a bipartite subgraph of $G$ (and hence the same is true
for the out-neighbourhood $N_{T}^{+}(U)\subseteq N_{D}^{+}(U)$ in $T$). Write
$U=\\{S_{1},\dotsc,S_{\lvert U\rvert}\\}$. By the second property of $f$
guaranteed by Lemma 8, there is some $r\in[n]$ common to all the
$f(\operatorname{\textup{{gap}}}(S_{i}))$. By the definition of $D$, any $S\in
N_{D}^{+}(U)$ satisfies $r\notin\operatorname{\textup{{gap}}}(S)$ and so
$S\cap\\{r,r+1\\}\neq\varnothing$. Colouring all the vertices in the out-
neighbourhood that include the element $r$ with one colour and all the
remaining vertices (which necessarily contain $r+1$) with another colour
provides a proper $2$-colouring of $G[N_{D}^{+}(S)]$. This concludes the proof
of the theorem. ∎

We can convert the graph $G$ from Theorem 2 to a tournament: pick any linear
order on the vertices of $G$ and construct a tournament $T_{1}$ whose back-
edge graph is $G$. We will show that $\chi(G)$ and $\chi(T_{1})$ are closely
related, and thus prove Corollary 3.

###### Proof of Corollary 3.

Let $K\coloneqq 2\chi$ and $n$ be sufficiently large. By Theorem 2 there is a
triangle-free graph $G$ with chromatic number $K$ and a tournament $T$ on the
same $N$-vertex set such that, for every set $U$ of at most
$\frac{\log{N}}{8\chi^{2}}$ vertices, $\chi(G[N_{T}^{+}(U)])\leqslant 2$. Let
$(V(G),\prec)$ be a linear order and define a tournament $T_{1}$ with vertex
set $V(G)$ as follows: there is an arc from vertex $u$ to vertex $v$ in
$T_{1}$ if either $v\prec u$ and $uv\in E(G)$ or $u\prec v$ and $uv\notin
E(G)$. We further set $T_{2}\coloneqq T$ and claim that the pair
$(T_{1},T_{2})$ of tournaments satisfies the statement of the corollary.

Let $W\subseteq V(G)$ be any set of vertices where $T_{1}[W]$ is transitive.
Note that if $v_{1}v_{2}v_{3}$ is a path in $G$ (so $v_{1}v_{3}\notin E(G)$ by
triangle-freeness) and $v_{1}\prec v_{2}\prec v_{3}$, then $v_{1}v_{2}v_{3}$
is a cyclic triangle in $T_{1}$ and so $v_{1}$, $v_{2}$, $v_{3}$ are not all
in $W$. In particular, the partition $W=W_{1}\cup W_{2}$ where

$\displaystyle W_{1}$ $\displaystyle\coloneqq\\{w\in W\colon\text{there is
$w^{\prime}\in W$ such that $w^{\prime}\prec w$ and $w^{\prime}w\in
E(G)$}\\},$ $\displaystyle W_{2}$ $\displaystyle\coloneqq\\{w\in
W\colon\text{there is no $w^{\prime}\in W$ such that $w^{\prime}\prec w$ and
$w^{\prime}w\in E(G)$}\\},$

gives a proper 2-colouring of the vertices of $G[W]$. Since this holds for any
$W$ where $T_{1}[W]$ is transitive, we have
$\chi(T_{1})\geqslant\chi(G)/2=\chi$.

To finish the proof, consider any set $U$ of at most
$\frac{\log{N}}{8\chi^{2}}=\frac{\log N}{2K^{2}}$ vertices. Note that
$G[N_{T}^{+}(U)]=G[N_{T_{2}}^{+}(U)]$ is bipartite. Let $I_{1}$, $I_{2}$ be
two disjoint independent sets in $G$ such that $I_{1}\cup
I_{2}=N_{T_{2}}^{+}(U)$. Now consider any two vertices $u,v\in I_{j}$ for some
$j\in\\{1,2\\}$ and note that since $uv\notin E(G)$, there is an arc from $u$
to $v$ in $T_{1}$ if and only if $u\prec v$. Hence $T_{1}[I_{1}]$ and
$T_{1}[I_{2}]$ are transitive tournaments and so
$\chi(T_{1}[N_{T_{2}}^{+}(U)])\leqslant 2$. ∎

To prove Corollary 4, we can now take the two tournaments $T_{1}$ and $T_{2}$
from Corollary 3 and combine them appropriately: we simply orient the edges
within $A$ and $B$ according to $T_{1}$, and the edges between $A$ and $B$
according to $T_{2}$.

###### Proof of Corollary 4.

Let $\chi$ be a positive integer. By Corollary 3, for arbitrarily large $N$
there exist tournaments $T_{1}$ and $T_{2}$ on the same $N$-vertex set $V$
with $\chi(T_{1})=2\chi$ and $\chi(T_{1}[N^{+}_{T_{2}}(U)])\leqslant 2$ for
every $U\subseteq V$ of size at most $\frac{\log{N}}{32\chi^{2}}$. Partition
$V$ into sets $A$ and $B$ such that
$\chi(T_{1}[A]),\chi(T_{1}[B])\geqslant\chi$, then construct a new tournament
$T$ on $V$ by orienting the edge between $u,v\in V$ to agree with $T_{1}$ if
$u,v\in A$ or $u,v\in B$, and orienting it to agree with $T_{2}$ otherwise. It
is not difficult to see that $T$ satisfies the conditions of the corollary. ∎

##  3\. Degeneracy

In this section we consider the setting in which degeneracy replaces chromatic
number. We first show that there is a tournament on the vertex set of the
$k$-dimensional hypercube such that each out-neighbourhood induces a forest in
the hypercube, proving Proposition 5. Therefore, having high degeneracy does
not imply that some out-neighbourhood has high degeneracy.

###### Proof of Proposition 5.

For each $k$, let $G_{k}$ be the hypercube on $2^{k}$ vertices. We will
actually prove something stronger than Proposition 5, namely that the _closed_
in- and out-neighbourhoods444The _closed in-neighbourhood_ of a vertex $v$ in
tournament $T$ is $N_{T}^{-}[v]\coloneqq\\{v\\}\cup N_{T}^{-}(v)$. The closed
out-neighbourhood is defined analogously. $G_{k}[N_{T}^{-}[v]]$ and
$G_{k}[N_{T}^{+}[v]]$ are both forests for every vertex $v\in V(G_{k})$. We
proceed by induction on $k$. For $k=1$ the result is immediate, so given
$k\geqslant 1$ let $T_{k}$ be a tournament on $V(G_{k})$ with the desired
property. We will view $G_{k+1}$ as the union of two copies of $G_{k}$, say
$G_{k}^{1}$ and $G_{k}^{2}$, connected via the matching consisting of all
edges of the form $x^{1}x^{2}$, where $x^{1}\in V(G_{k}^{1})$ and $x^{2}\in
V(G_{k}^{2})$ denote the copies of a vertex $x\in V(G_{k})$. For each
$S\subseteq V(G_{k})$, we will write $S^{(1)}$ and $S^{(2)}$ for the
corresponding sets of vertices in $G_{k}^{1}$ and $G_{k}^{2}$ respectively.

Now define a tournament $T_{k+1}$ on vertex set $V(G_{k+1})$ as follows. First
orient the edges within each of $V(G_{k}^{1})$ and $V(G_{k}^{2})$ according to
$T_{k}$, in the canonical way. Then for each $x\in V(G_{k})$, orient every
edge between $x^{1}$ and ${N_{T_{k}}^{-}[x]}^{(2)}$ away from $x^{1}$ and
every edge between $x^{1}$ and ${N_{T_{k}}^{+}(x)}^{(2)}$ towards $x^{1}$.
This completes the construction of $T_{k+1}$. Observe that for each $x\in
V(G_{k})$, the edges between $x^{2}$ and ${N_{T_{k}}^{-}(x)}^{(2)}$ are
oriented away from $x^{2}$ and the edges between $x^{2}$ and
${N_{T_{k}}^{+}[x]}^{(2)}$ are oriented towards $x^{2}$.

Let $x\in V(G_{k})$ and note that
$N_{T_{k+1}}^{+}[x^{1}]={N_{T_{k}}^{+}[x]}^{(1)}\cup{N_{T_{k}}^{-}[x]}^{(2)}$.
By the induction hypothesis, $N_{T_{k}}^{+}[x]$ and $N_{T_{k}}^{-}[x]$ both
induce forests in $G_{k}$, so ${N_{T_{k}}^{+}[x]}^{(1)}$ and
${N_{T_{k}}^{-}[x]}^{(2)}$ do the same in $G_{k+1}$. Since there is exactly
one edge in $G_{k+1}$ between these two sets, namely $x^{1}x^{2}$, the graph
$G_{k+1}[N_{T_{k+1}}^{+}[x^{1}]]$ is acyclic. Analogous arguments show that
$G_{k+1}[N_{T_{k+1}}^{-}[x^{1}]]$, $G_{k+1}[N_{T_{k+1}}^{+}[x^{2}]]$, and
$G_{k+1}[N_{T_{k+1}}^{-}[x^{2}]]$ are all acyclic too. Since every vertex of
$G_{k+1}$ is of the form $x^{1}$ or $x^{2}$ for some $x\in V(G_{k})$, this
completes the proof. ∎

However, we will now show that, unlike with chromatic number, having high
degeneracy implies that there are two vertices $x$ and $y$ such that the out-
neighbourhood of $\\{x,y\\}$ has high degeneracy.

###### Proof of Theorem 6.

Let $H$ be a bipartite subgraph of $G$ with $\delta(H)\geqslant 6k$ and let
$A\cup B$ be a bipartition of $H$ with $\lvert A\rvert\geqslant\lvert
B\rvert$. Define $T_{1}=T[A]$ and $T_{2}=T[B]$. Pick $x\in A$ satisfying
$\lvert N_{T_{1}}^{+}[x]\rvert\geqslant\lvert A\rvert/2$ and define
$A^{\prime}=N_{T_{1}}^{+}[x]$. Now let $H_{1}=H[A^{\prime},B]$. It can be
shown using linear programming duality that every tournament has a probability
distribution on its vertex set which assigns weight at least $1/2$ to every
closed in-neighbourhood (see [FR95, Sec. 1.2]). Let $w$ be such a probability
distribution for $T_{2}$. Take a random vertex $y\in B$ according to $w$ and
note that $\mathbb{P}(u\in N^{+}_{T_{2}}[y])\geqslant 1/2$ for every $u\in B$.
Let $H_{2}=H_{1}[A^{\prime},N_{T_{2}}^{+}[y]]$ so that for every $e\in
E(H_{1})$, $\mathbb{P}[e\in E(H_{2})]\geqslant 1/2$. We have
$\mathbb{E}[e(H_{2})]\geqslant e(H_{1})/2\geqslant 3k\lvert
A^{\prime}\rvert\geqslant k(\lvert A^{\prime}\rvert+\lvert B\rvert)$, from
which it follows, since $\lvert N_{T_{2}}^{+}[y]\rvert\leqslant\lvert
B\rvert$, that there exists $y\in B$ such that $e(H_{2})\geqslant k\lvert
V(H_{2})\rvert$. Removing $x$ and $y$ from $H_{2}$, we obtain a subgraph
$G^{\prime}$ of $G[N^{+}_{T}(\\{x,y\\})]$ with
$e(G^{\prime})\geqslant(k-2)\lvert V(G^{\prime})\rvert$. Thus $G^{\prime}$,
and therefore also $G[N^{+}(\\{x,y\\})]$, has degeneracy greater than $k-2$. ∎

##  4\. Fractional chromatic number

We remind the reader that a graph $G$ has fractional chromatic number
$\chi_{f}(G)\leqslant r$ if and only if there is a probability distribution on
the independent sets of $G$ such that the random independent set
$\boldsymbol{I}$ obtained and every vertex $v$ satisfy
$\mathbb{P}(v\in\boldsymbol{I})\geqslant 1/r$. In this section we demonstrate
that the modified version of 1 in which chromatic number is replaced by
fractional chromatic number is true, as observed by Scott and Seymour [SS16]
without proof.

######  Theorem 9.

For $c\geqslant 1$, let $G$ be a graph and $T$ be a tournament on the same
vertex set such that $\chi_{f}(G[N_{T}^{+}(v)])\leqslant c$ for every vertex
$v$. Then $\chi_{f}(G)\leqslant 2(c+1)$.

###### Proof.

Let $w$ be a probability distribution on the vertex set of $T$ that assigns
weight at least $1/2$ to every closed in-neighbourhood. For each vertex $v$,
since $\chi_{f}(G[N_{T}^{+}(v)])\leqslant c$, there is a random independent
set $\boldsymbol{I}_{v}$ of $G[N_{T}^{+}(v)]$ such that
$\mathbb{P}(u\in\boldsymbol{I}_{v})\geqslant 1/c$ for every $u\in
N_{T}^{+}(v)$.

We sample a random independent set $\boldsymbol{I}$ of $G$ as follows. First
pick a vertex $\boldsymbol{v}$ according to $w$. Then with probability
$1/(c+1)$ take $\boldsymbol{I}=\\{\boldsymbol{v}\\}$ and with probability
$c/(c+1)$ take $\boldsymbol{I}=\boldsymbol{I}_{\boldsymbol{v}}$. Note that,
for any vertex $u$, if $\boldsymbol{v}\in N^{-}[u]$, then $u\in\boldsymbol{I}$
with probability at least $1/(c+1)$. Hence, by the defining property of $w$,
$\mathbb{P}(u\in\boldsymbol{I})\geqslant 1/(2c+2)$ and so
$\chi_{f}(G)\leqslant 2(c+1)$. ∎

##  5\. Closing remarks

We have been unable to determine whether high chromatic number forces an out-
neighbourhood with high degeneracy, and we would be interested to know if this
is the case.

######  Question 10.

Does there exist, for each integer $d$, an integer $\chi$ such that for every
graph $G$ with $\chi(G)\geqslant\chi$ and every tournament $T$ on the same
vertex set, there is a vertex $v$ for which $G[N^{+}_{T}(v)]$ has degeneracy
at least $d$?

We do, however, suspect that this is true for $d=2$, that is, it should be
possible to force some out-neighbourhood to contain a cycle.

######  Conjecture 11.

For every graph $G$ with sufficiently large chromatic number, and every
tournament $T$ on the same vertex set, there exists a vertex $v$ such that
$G[N^{+}_{T}(v)]$ contains a cycle.

We have shown that for certain very structured tournaments $T$ there are
graphs on the same vertex set with large chromatic number, in which every out-
neighbourhood of $T$ induces a bipartite subgraph. We conjecture that (with
high probability) we cannot replace $T$ with a random tournament.

######  Conjecture 12.

For every positive integer $k$, there exists a $\chi$ such that if $T$ is the
uniformly random tournament on vertex set $[N]$, then with high probability
(as $N\to\infty$), for every graph $G$ on $[N]$ with $\chi(G)\geqslant\chi$
there is a vertex $v\in[N]$ for which $G[N^{+}_{T}(v)]\geqslant k$.

Finally, as remarked after the statement of Theorem 2, if
$\chi(G)\geqslant\chi$, then there is a collection of at most
$\lceil\log_{2}(N)/\lfloor\chi/2-1\rfloor\rceil$ out-neighbourhoods whose
union induces a subgraph of chromatic number at least 3. It would be
interesting to know if $o(\log(N)/\chi)$ (as $\chi\to\infty$) out-
neighbourhoods suffice here. In particular, we conjecture the following.

######  Conjecture 13.

There exists $f(N)$ satisfying $f(N)=o(\log N)$ such that for every $N$-vertex
graph $G$ with $\chi(G)\geqslant f(N)$, and every tournament $T$ on the same
vertex set, there is a vertex $v$ for which $\chi(G[N^{+}_{T}(v)])\geqslant
3$.

### Acknowledgements

We would like to thank Sang-il Oum, Alex Scott, David Wood, and Liana
Yepremyan for organising the April 2023 MATRIX-IBS Structural Graph Theory
Downunder III workshop where we began this work. Our thanks to Paul Seymour
for helpful comments on the paper.

## References

  * [Bár78] Imre Bárány (Nov. 1978).  A short proof of Kneser’s conjecture.  _Journal of Combinatorial Theory, Series A_ 25(3), 325–326.
  * [BCC+13] Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé (Jan. 2013).  Tournaments and colouring.  _Journal of Combinatorial Theory, Series B_ 103(1), 1–20.
  * [Des54] Blanche Descartes (May 1954).  $k$-chromatic graphs without triangles.  _American Mathematical Monthly_ 61(5), 352–353.
  * [Erd63] Paul Erdős (Oct. 1963).  On a problem in graph theory.  _The Mathematical Gazette_ 47, 220–223.
  * [FR95] David C. Fisher and Jennifer Ryan (Mar. 1995).  Tournament games and positive tournaments.  _Journal of Graph Theory_ 19(2), 217–236.
  * [Gre02] Joshua E. Greene (Dec. 2002).  A new short proof of Kneser’s conjecture.  _The American Mathematical Monthly_ 109(10), 918–920.
  * [GS71] Ronald L. Graham and Joel H. Spencer (Jan. 1971).  A constructive solution to a tournament problem.  _Canadian Mathematical Bulletin_ 14, 45–48.
  * [HLTW19] Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, and Hehui Wu (Sep. 2019).  Coloring tournaments: from local to global.  _Journal of Combinatorial Theory, Series B_ 138, 166–171.
  * [Kne55] Martin Kneser (1955).  Aufgabe 360.  _Jahresbericht der Deutschen Mathematiker-Vereinigung_ 58(2).
  * [Lov78] László Lovász (Nov. 1978).  Kneser’s conjecture, chromatic number, and homotopy.  _Journal of Combinatorial Theory, Series A_ 25(3), 319–324.
  * [NSS23] Tung Nguyen, Alex Scott, and Paul Seymour (Jun. 2023).  Some results and problems on tournament structure.  arXiv:2306.02364.
  * [Sch78] Alexander Schrijver (1978).  Vertex-critical subgraphs of Kneser graphs.  _Nieuw Archief voor Wiskunde_ 26(3), 454–461.
  * [SS16] Alex Scott and Paul Seymour (Mar. 2016).  Open problems for the Barbados Graph Theory Workshop 2016, problem 1.  url: https://web.math.princeton.edu/~pds/barbados2016/openproblems.html.  Accessed on 18 May 2023.
  * [Zyk49] A. Zykov (1949).  On some properties of linear complexes (in Russian).  _Matematicheskiǐ Sbornik_ 24, 163–188.  For an English translation see American Mathematical Society Translations 79, 1952.


# Towards a representer theorem for identification of passive systems

B. M. Shali and H. J. van Waarde The authors B. M. Shali<EMAIL_ADDRESS>and H. J. van Waarde<EMAIL_ADDRESS>are with the Bernoulli Institute
for Mathematics, Computer Science, and Artificial Intelligence, University of
Groningen, Groningen, The Netherlands. H. J. van Waarde acknowledges financial
support by the Dutch Research Council under the NWO Talent Programme Veni
Agreement (VI.Veni.22.335).

###### Abstract

A major problem in system identification is the incorporation of prior
knowledge about the physical properties of the given system, such as
stability, positivity and passivity. In this paper, we present first steps
towards tackling this problem for passive systems. In particular, using ideas
from the theory of reproducing kernel Hilbert spaces, we solve the problem of
identifying a nonnegative input-output operator from data consisting of input-
output trajectories of the system. We prove a representer theorem for this
problem in the case where the input space is finite-dimensional. This provides
a computationally tractable solution, which we show can be obtained by solving
an associated semidefinite program.

##  I Introduction

System identification is the process of obtaining a mathematical model that
accurately describes the behaviour of a dynamical system based on empirical
observations. System identification has a rich history in the field of systems
and control. The classical approach is to search within a given class of
finite-dimensional parametric models, e.g., in autoregressive or state-space
form. Recently, inspired by developments in machine learning, a new paradigm
for system identification has emerged [1, 2, 3, 4]. The latter uses the theory
of reproducing kernel Hilbert spaces [5, 6] and formulates system
identification as function (operator) estimation in a possibly infinite-
dimensional reproducing kernel Hilbert space. A key aspect of this paradigm is
the _representer_ theorem, which allows for a computationally tractable
solution to this estimation problem.

A major challenge in system identification is the incorporation of prior
knowledge about the physical properties of the system, such as stability [7],
positivity [8, 9] and (incremental) dissipativity [10, 11]. The incorporation
of such properties can enhance the reliability and robustness of the
identified model by ensuring that the simulated behaviour aligns with the
real-world behaviour of the system. This is particularly relevant when the
model is used to simulate trajectories far away from the data set used for
identification. For example, it has been shown [12, 13] that incorporating
stability in the identified model results in better long-term predictions and
generalizations to new data sets.

In this paper, we focus on the identification of passive systems, which can be
seen as a special case of dissipative systems. Identification of dissipative
systems has been studied in the case where the underlying model class consists
of linear systems [10]. On the other hand, identification of incrementally
dissipative (nonlinear) systems has been studied in the case where the
underlying model class is a reproducing kernel Hilbert space of operators
[11]. The results in the latter are obtained by making use of the so-called
_scattering transform_ , which allows to reformulate the original problem as
the problem of identifying a system with a small incremental gain. While these
results can be used to identify systems with non-incremental properties, i.e.,
systems that are simply dissipative, the reliance on the scattering transform
presents some limitations. Most notably, the scattering transform is generally
not computable in the non-incremental case.

Motivated by this, we consider the problem of identifying a passive input-
output model for a (nonlinear) system from data on its input and output
trajectories. We consider an input-output model defined as an operator from
the space of inputs to itself. In this case, passivity of the system
corresponds to nonnegativity of the corresponding input-output operator, under
the assumption that the latter is causal. Therefore, as a first step towards
identifying a passive input-output model, we focus on the problem of
identifying a nonnegative input-output operator. Since nonnegativity is not
preserved under arbitrary linear combinations, we cannot directly apply the
theory of reproducing Hilbert spaces and use the representer theorem. Instead,
we take inspiration from the sum of squares idea for nonnegative function
estimation recently developed in [14].

In particular, we consider a class of input-output operators defined via a
feature map and a nonnegative bounded linear operator in such a way that
nonnegativity of the input-output operator is guaranteed. Then, we formulate
the identification problem as an estimation problem for the aforementioned
linear operator. As our main result, we obtain a representer theorem for this
estimation problem in the case where the input space is finite-dimensional.
Then, we show that a solution of the latter can be obtained by solving an
associated semidefinite program. Finally, by means of an example, we
demonstrate how these results can be used in practice, even when the input
space is not finite-dimensional.

The remainder of this paper is organized as follows. We introduce notation and
preliminaries in Section II. We formulate the identification problem in
Section III and we discuss the relevant theory of reproducing kernel Hilbert
spaces in Section IV. We solve the identification problem in Section V and we
show how the solution can be obtained by solving an associated semidefinite
program in Section VI. Finally, we demonstrate our results with an example in
Section VII and we provide concluding remarks in Section VIII.

##  II Notation and prelimnaries

We denote the set of positive integers by $\mathbb{N}$. For $n\in\mathbb{N}$,
we denote the set $\\{1,\dots,n\\}$ by $[n]$. We denote the Cartesian product
of the sets $X$ and $Y$ by $X\times Y$. Given a set $X$ and $n\in\mathbb{N}$,
we write $X^{n}$ to denote the Cartesian product

$X^{n}=\underbrace{X\times X\times\cdots\times X}_{n\text{ times}}.$ (1)

Given a Hilbert space $\mathcal{U}$, we denote the corresponding inner product
by $\langle\cdot,\cdot\rangle_{\mathcal{U}}$ and the induced norm by
$\lVert\cdot\rVert_{\mathcal{U}}$. We say that an operator
$G:\mathcal{U}\to\mathcal{U}$ is _nonnegative_ if $\langle
Gu,u\rangle_{\mathcal{U}}\geq 0$ for all $u\in\mathcal{U}$. Given another
Hilbert space $\mathcal{W}$, we denote the Banach space of bounded linear
operators from $\mathcal{U}$ to $\mathcal{W}$ by
$\mathscr{B}(\mathcal{U},\mathcal{W})$ and the operator norm by
$\lVert\cdot\rVert$. We use the shorthand notation
$\mathscr{B}(\mathcal{U})=\mathscr{B}(\mathcal{U},\mathcal{U})$ and

$\mathscr{B}^{+}(\mathcal{U})=\left\\{G\in\mathscr{B}(\mathcal{U})\,\left|\,\vphantom{G\in\mathscr{B}(\mathcal{U})}G\text{
is nonnegative}\right.\right\\}.$ (2)

We denote the adjoint of $B\in\mathscr{B}(\mathcal{U},\mathcal{W})$ by
$B^{*}\in\mathscr{B}(\mathcal{W},\mathcal{U})$. We identify the vector
$w\in\mathcal{W}$ with the operator $\alpha\mapsto\alpha w$, which belongs to
$\mathscr{B}(\mathbb{R},\mathcal{W})$. Consequently,
$w^{*}\in\mathscr{B}(\mathcal{W},\mathbb{R})$ is such that $w^{*}z=\langle
w,z\rangle_{\mathcal{W}}$ for all $z\in\mathcal{W}$. In particular, given
$w_{1},w_{2}\in\mathcal{W}$, we have that
$w_{1}w_{2}^{*}\in\mathscr{B}(\mathcal{W})$ is such that
$w_{1}w_{2}^{*}z=\langle w_{2},z\rangle_{\mathcal{W}}w_{1}$ for all
$z\in\mathcal{W}$.

Note that $\mathcal{U}^{n}$ is a Hilbert space with inner-product

$\langle(u_{1},\dots,u_{n}),(v_{1},\dots,v_{n})\rangle_{\mathcal{U}^{n}}=\sum_{i=1}^{n}\langle
u_{i},v_{i}\rangle_{\mathcal{U}}.$ (3)

Given operators $M_{ij}\in\mathscr{B}(\mathcal{U})$, $i,j\in[n]$, we define

$M=\begin{bmatrix}M_{11}&\cdots&M_{1n}\\\ \vdots&\ddots&\vdots\\\
M_{n1}&\cdots&M_{nn}\end{bmatrix}$ (4)

as the operator in $\mathscr{B}(\mathcal{U}^{n})$ such that

$M(u_{1},\dots,u_{n})=\left(\sum_{i=1}^{n}M_{1i}u_{i},\dots,\sum_{i=1}^{n}M_{ni}u_{i}\right).$
(5)

It is easily seen that any $M\in\mathscr{B}(\mathcal{U}^{n})$ can be written
in the form (4) for suitably chosen $M_{ij}\in\mathscr{B}(\mathcal{U})$,
$i,j\in[n]$.

###  II-A Signal spaces

Let $\mathbb{R}^{+}$ denote the set of nonnegative real numbers and let
$\mathcal{R}$ be a finite-dimensional Hilbert space, e.g., $\mathbb{R}^{m}$
with the Euclidian inner-product. The set of _square integrable functions_
$L_{2}(\mathbb{R}^{+},\mathcal{R})$ consists of all measurable functions
$u:\mathbb{R}^{+}\to\mathcal{R}$ such that $\int_{0}^{\infty}\lVert
u(t)\rVert_{\mathcal{R}}\textrm{d}t<\infty$. If we identify functions that
differ only on a set of Lebesgue measure zero, then
$L_{2}(\mathbb{R}^{+},\mathcal{R})$ becomes a Hilbert space with inner-product

$\langle
u,v\rangle_{L_{2}(\mathbb{R}^{+},\mathcal{R})}=\int_{0}^{\infty}\langle
u(t),v(t)\rangle_{\mathcal{R}}\textrm{d}t,$ (6)

The Hilbert space $L_{2}([0,T],\mathcal{R})$, where $T>0$, can be defined
similarly by replacing the upper bound with $T$.

Let $\mathbb{Z}^{+}$ denote the set of nonnegative integers. The set of
_square summable sequences_ $\ell_{2}(\mathbb{Z}^{+},\mathcal{R})$ consists of
all functions $u:\mathbb{Z}^{+}\to\mathcal{R}$ such that
$\sum_{t=0}^{\infty}\lVert u(t)\rVert_{\mathcal{R}}<\infty.$ The latter is a
Hilbert space with inner-product

$\langle
u,v\rangle_{\ell_{2}(\mathbb{Z}^{+},\mathcal{R})}=\sum_{t=0}^{\infty}\langle
u(t),v(t)\rangle_{\mathcal{R}}.$ (7)

The Hilbert space $\ell_{2}(\\{0,1\dots,T\\},\mathcal{R})$, where
$T\in\mathbb{N}$, can be defined similarly.

We will collectively refer to the spaces above as _signal spaces_. Thus, a
signal space consists of functions $u:\mathbb{T}\to\mathcal{R}$, where
$\mathcal{R}$ is a Hilbert space and $\mathbb{T}$ is a time axis given by one
of $\mathbb{R}^{+}$, $[0,T]$, $\mathbb{Z}^{+}$ or $\\{0,1,\dots,T\\}$.

###  II-B Passivity and causality

Next, we define the notions of causality and passivity, see [15, Chapter VI]
for details. Let $\mathcal{U}$ be a signal space. For $\tau\in\mathbb{T}$, we
define the truncation operator $P_{\tau}:\mathcal{U}\to\mathcal{U}$ as

$(P_{\tau}u)(t)=\begin{dcases*}u(t)&$t\leq\tau$,\\\ 0&$t>\tau$.\end{dcases*}$
(8)

Note that $P_{\tau}$ is linear, $P_{\tau}^{2}=P_{\tau}$ and
$P_{\tau}^{*}=P_{\tau}$, that is, $P_{\tau}$ is an orthogonal projection for
all $\tau\in\mathbb{T}$. We say that an operator $G:\mathcal{U}\to\mathcal{U}$
is:

  1. 1.

_passive_ if

$\langle P_{\tau}u,P_{\tau}Gu\rangle_{\mathcal{U}}\geq 0$ (9)

for all $u\in\mathcal{U}$ and $\tau\in\mathbb{T}$;

  2. 2.

_causal_ if

$P_{\tau}Gu=P_{\tau}GP_{\tau}u,$ (10)

for all $u\in\mathcal{U}$ and $\tau\in\mathbb{T}$.

In other words, $G$ is causal if the output at each time instant depends only
on the past of the input. Note that $G$ is passive only if it is nonnegative
(take $\tau\to\infty$ in (9)). If $G$ is causal, then $G$ is passive if and
only if $G$ is nonnegative since

$\langle P_{\tau}u,P_{\tau}Gu\rangle_{\mathcal{U}}=\langle
P_{\tau}u,P_{\tau}GP_{\tau}u\rangle_{\mathcal{U}}=\langle
P_{\tau}u,GP_{\tau}u\rangle_{\mathcal{U}},$

for all $u\in\mathcal{U}$ and $\tau\in\mathbb{T}$, where the second equality
follows from the fact that $P_{\tau}$ is an orthogonal projection.

##  III Problem formulation

Let $\mathcal{U}$ be a signal space. Suppose that we are given a data set
consisting of $n\in\mathbb{N}$ input-output signals

$(u_{i},y_{i})\in\mathcal{U}\times\mathcal{U},\quad i\in[n].$ (11)

At a high-level, we are interested in finding a passive operator
$G:\mathcal{U}\to\mathcal{U}$ that fits the data well, i.e., such that the
_data misfit_

$L(G)=\sum_{i=1}^{n}\lVert Gu_{i}-y_{i}\rVert_{\mathcal{U}}^{2}$ (12)

is small. Note that a passive operator is necessarily nonnegative. Therefore,
as a first step towards solving this high-level problem, in this paper, we
focus on the following problem.

###### Problem 1

Given the data in (11), find a nonnegative operator
$G:\mathcal{U}\to\mathcal{U}$ such that $L(G)$ is small.

We will formalize what “small” means by introducing an appropriate cost
functional in Section V. Then, we will solve Problem 1 in the case where
$\mathcal{U}$ is finite-dimensional. Note that the only finite dimensional
signal space that we consider is $\ell_{2}(\\{0,\dots,T\\},\mathcal{R})$,
where $T\in\mathbb{N}$ and $\mathcal{R}$ is a Hilbert space. Nevertheless,
since nonnegativity is defined for operators on arbitrary Hilbert spaces, the
following results are equally applicable to any finite-dimensional Hilbert
space $\mathcal{U}$. In particular, they are applicable to any finite
dimensional subspace of a signal space. We will demonstrate this with an
example in Section VII.

##  IV Reproducing kernel Hilbert spaces

In this section, we will introduce part of the theory on reproducing kernel
Hilbert spaces that is relevant to this paper. We refer to [6] for a detailed
treatment of the case where the kernel is scalar-valued, and to [16] for the
extension to the general case. We also refer to the technical report by [17].
In the context of this paper, we restrict the discussion to the case where the
input and output spaces are identical.

Consider a Hilbert space $\mathcal{U}$. A Hilbert space $\mathcal{H}$ of
operators from $\mathcal{U}$ to $\mathcal{U}$ is a _reproducing kernel Hilbert
space_ if it admits a reproducing kernel, defined below.

###### Definition 1

A map $k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ is a
_reproducing kernel_ for $\mathcal{H}$ if
$k(\cdot,u)v:\mathcal{U}\to\mathcal{U}$ is a member of $\mathcal{H}$ for all
$u,v\in\mathcal{U}$, and

$\langle v,Hu\rangle_{\mathcal{U}}=\langle H,k(\cdot,u)v\rangle_{\mathcal{H}}$
(13)

for all $u,v\in\mathcal{U}$ and $H\in\mathcal{H}$.

Property (13) is referred to as the _reproducing property_. The class of
reproducing kernels is completely characterized by two properties, namely,
symmetry and positive semidefiniteness, defined below.

###### Definition 2

The map $k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ is
_symmetric_ if $k(u,v)^{*}=k(v,u)$ for all $u,v\in\mathcal{U},$.

###### Definition 3

The map $k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ is
_positive semidefinite_ if

$\sum_{i=1}^{n}\langle v_{i},k(u_{i},u_{j})v_{j}\rangle\geq 0$ (14)

for all $n\in\mathbb{N}$, $u_{1},\dots,u_{n}\in\mathcal{U}$,
$v_{1},\dots,v_{n}\in\mathcal{U}$.

It is straightforward to show that a reproducing kernel needs to be symmetric
and positive semidefinite due to the reproducing property. More notably, the
converse also holds and is known as the Moore-Aronszajn theorem [5], see [16]
for the extension to the general case.

###  IV-A Gram operator

The properties of symmetry and positive semidefiniteness of the map
$k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ can be expressed
using the associated _Gram operator_. Given $n\in\mathbb{N}$ and
$u_{1},\dots,u_{n}\in\mathcal{U}$, we define the Gram operator
$K\in\mathscr{B}(\mathcal{U}^{n})$ as

$K=\begin{bmatrix}k(u_{1},u_{1})&\cdots&k(u_{1},u_{n})\\\
\vdots&\ddots&\vdots\\\ k(u_{n},u_{1})&\cdots&k(u_{n},u_{n})\end{bmatrix},$
(15)

Then, (14) can be written as

$\langle K(v_{1},\dots,v_{n}),(v_{1},\dots,v_{n})\rangle_{\mathcal{U}_{n}}\geq
0.$ (16)

Therefore, the map $k$ is symmetric and positive semidefinite if and only if,
for all $n\in\mathbb{N}$ and $u_{1},\dots,u_{n}\in\mathcal{U}$, the
corresponding Gram operator $K$ in (15) is self-adjoint and nonnegative.

###  IV-B Feature map

Symmetric positive definite maps
$k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ can be defined via
an auxiliary Hilbert space $\mathcal{W}$ and a map
$\phi:\mathcal{U}\to\mathscr{B}(\mathcal{U},\mathcal{W})$. In particular, it
can be shown that the map $k(u,v)=\phi(u)^{*}\phi(v)$ is symmetric and
positive semidefinite. The space $\mathcal{W}$ is typically referred to as a
_feature space_ and the map $\phi$ as a _feature map_. There is a close
relationship between symmetric positive definite maps $k$ and their associated
feature maps $\phi$. This is captured in the following proposition.

###### Proposition 1

The map $k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ is
symmetric and positive semidefinite if and only if there exists a Hilbert
space $\mathcal{W}$ and a feature map
$\phi:\mathcal{U}\to\mathscr{B}(\mathcal{U},\mathcal{W})$ such that
$k(u,v)=\phi(u)^{*}\phi(v)$.

The feature map $\phi$ is central in developing kernel-based algorithms and
can allow for simpler analysis. In particular, it can be shown that the
reproducing kernel Hilbert space $\mathcal{H}$ with reproducing kernel
$k(u,v)=\phi(u)^{*}\phi(v)$ consists of operators of the form

$Hu=\phi(u)^{*}w,$ (17)

where $w\in\bar{\mathcal{W}}$ and $\bar{\mathcal{W}}\subset\mathcal{W}$ is the
closed linear span of the set
$\left\\{\phi(v_{1})v_{2}\,\left|\,\vphantom{\phi(v_{1})v_{2}}v_{1},v_{2}\in\mathcal{U}\right.\right\\}$.
We refer to [17, Theorem 5 and Theorem 6] for a proof in the case where the
kernel is scalar-valued. The proof in the general case follows similar
reasoning.

###  IV-C Representer theorem

One of the most attractive features of the theory of reproducing kernel
Hilbert spaces is that operator estimation problems have computationally
tractable solutions. Here, we focus on the problem stated in Section III but
without the nonnegativity requirement. In particular, we consider the problem
of identifying an operator $G:\mathcal{U}\to\mathcal{U}$ such that the data
misfit (12) is small. Let $\mathcal{H}$ be a reproducing kernel Hilbert space
of operators from $\mathcal{U}$ to $\mathcal{U}$. We restrict our search to
operators $G$ that belong to $\mathcal{H}$. In general, under mild conditions,
the data $(u_{i},y_{i})\in\mathcal{U}\times\mathcal{U}$, $i\in[n]$, can be
interpolated exactly, i.e., there exists an operator $G\in\mathcal{H}$ such
that $Gu_{i}=y_{i}$ for all $i\in[n]$ and, thus, $L(G)=0$. However, we
typically expect the data to be noisy, in which case exact interpolation is
undesirable. In such cases, a well-established identification approach is to
instead consider the _regularized least squares_ problem

$\min_{G\in\mathcal{H}}\quad L(G)+\gamma\lVert G\rVert_{\mathcal{H}}.$ (18)

Here, the first term promotes small $L(G)$, i.e., a good fit of the data,
whereas the second term promotes small $\lVert G\rVert_{\mathcal{H}}$, which
is interpreted as low complexity. The parameter $\gamma>0$ regulates the
balance between these two terms.

The representer theorem, stated in the following proposition, shows that (18)
has a unique solution for any reproducing Hilbert space $\mathcal{H}$, any
parameter $\gamma>0$ and any data set
$(u_{i},y_{i})\in\mathcal{U}\times\mathcal{U}$, $i\in[n]$.

###### Proposition 2

There exists a unique solution $\hat{G}$ of (18), which is given by

$\hat{G}u=\sum_{i=1}^{n}k(u,u_{i})c_{i},$ (19)

with $c_{i}\in\mathcal{U}$, $i\in[n]$, given by the unique solution of

$(K+\gamma I)(c_{1},\dots,c_{n})=(y_{1},\dots,y_{n}),$ (20)

where $K\in\mathscr{B}(\mathcal{U}^{n})$ is the Gram operator associated with
$k$ and $u_{1},\dots,u_{n}$, and $I\in\mathscr{B}(\mathcal{U}^{n})$ is the
identity operator.

Note that, if $\mathcal{U}$ is finite-dimensional, then $\mathcal{U}^{n}$ is
finite-dimensional and, thus, solving (20) amounts to solving a finite-
dimensional system of linear equations.

As already mentioned in the previous subsection, there exists feature map
$\phi:\mathcal{U}\to\mathscr{B}(\mathcal{U},\mathcal{W})$ such that the
reproducing kernel for $\mathcal{H}$ is given by $k(u,v)=\phi(u)^{*}\phi(v)$.
Furthermore, every $G\in\mathcal{H}$ is of the form

$Gu=\phi(u)^{*}w,$ (21)

where $w\in\bar{\mathcal{W}}\subset\mathcal{W}$. With a minor abuse of
notation, we can treat the data misfit (12) as a function of $w$, such that

$L(w)=\sum_{i=1}^{n}\lVert\phi(u_{i})^{*}w-y_{i}\rVert_{\mathcal{U}}^{2}.$
(22)

Since $\lVert G\rVert_{\mathcal{H}}=\lVert w\rVert_{\mathcal{W}}$, we can
rewrite (18) as

$\min_{w\in\bar{\mathcal{W}}}\quad L(w)+\gamma\lVert w\rVert_{\mathcal{W}}.$
(23)

Then, Proposition 2 tells us that (23) has a unique solution
$\hat{w}\in\bar{\mathcal{W}}$ given by

$\hat{w}=\sum_{i=1}^{n}\phi(u_{i})c_{i},$ (24)

with $c_{i}\in\mathcal{U}$, $i\in[n]$, given by the unique solution of (20).

##  V Representer theorem for nonnegative operators

In this section, we will provide a solution to Problem 1. To do this, we take
inspiration from the theory of reproducing kernel Hilbert spaces and the sum
of squares idea developed in [14]. We will first motivate our approach by
considering a simple example.

###### Example 1

Consider a continuous function $f:\mathbb{R}\to\mathbb{R}$ that is
differentiable at zero. We view $f$ as an operator from $\mathbb{R}$ to
$\mathbb{R}$. As such, $f$ is nonnegative if and only if $f(x)x\geq 0$ for all
$x\in\mathbb{R}$. In particular, this means that $f(0)=0$, hence we can write
$f(x)=g(x)x$, where the function $g:\mathbb{R}\to\mathbb{R}$ given by

$g(x)=\begin{dcases*}\frac{f(x)}{x}&if $x\neq 0$,\\\ f^{\prime}(0)&if
$x=0$.\end{dcases*}$ (25)

is continuous. Since $f(x)$ is nonnegative as an operator, it follows that
$g(x)\geq 0$ for all $x\in\mathbb{R}$, i.e., $g$ is nonnegative as a function.
Conversely, if $f(x)=g(x)x$ for some nonnegative function $g$, then $f$ is
nonnegative as an operator. Now, suppose that we have a data set consisting of
$n\in\mathbb{N}$ pairs $(x_{i},f_{i})\in\mathbb{R}\times\mathbb{R}$,
$i\in[n]$, and consider the problem of finding a nonnegative operator
$f:\mathbb{R}\to\mathbb{R}$ that fits the data well, i.e., $f(x_{i})\approx
f_{i}$ for all $i\in[n]$. If we further require that $f$ is continuous and
differentiable at $0$, then, without loss of generality, we can assume that
$f(x)=g(x)x$ for some continuous nonnegative function
$g:\mathbb{R}\to\mathbb{R}$. Consequently, the problem reduces to finding a
nonnegative $g$ such that $g(x_{i})\approx f_{i}/x_{i}$ for all $i\in[n]$.
This can be solved using the sum-of-squares approach in [14]. In particular,
given a Hilbert space of features $\mathcal{W}$ and a feature map
$\phi:\mathbb{R}\to\mathcal{W}$, we can model a nonnegative function as
$g(x)=\phi(x)^{*}Q\phi(x)$, where the operator $Q\in\mathscr{B}(\mathcal{W})$
is nonnegative. Note that this yields

$f(x)=\phi(x)^{*}Q\phi(x)x$ (26)

As shown in [14], the problem can be reformulated as a regularized least
squares problem with an appropriately chosen cost functional. Furthermore, the
authors of [14] obtain a representer theorem for this problem that provides a
computationally tractable solution.

With Example 1 in mind, we take the following approach to solve Problem 1. Let
$\mathcal{W}$ be a Hilbert space of features and
$\phi:\mathcal{U}\to\mathscr{B}(\mathcal{U},\mathcal{W})$ a feature map. In
view of (26), we consider input-output operators $G:\mathcal{U}\to\mathcal{U}$
of the form

$Gu=\phi(u)^{*}Q\phi(u)u,$ (27)

where $Q\in\mathscr{B}(\mathcal{W})$. Since

$\langle
Gu,u\rangle_{\mathcal{U}}=\langle\phi(u)^{*}Q\phi(u)u,u\rangle_{\mathcal{U}}=\langle
Q\phi(u)u,\phi(u)u\rangle_{\mathcal{W}},$

it follows that that $G$ is nonnegative if $Q$ is nonnegative. With a minor
abuse of notation, we can treat the data misfit (12) as a function of $Q$,
such that

$L(Q)=\sum_{i=1}^{n}\lVert\phi(u_{i})^{*}Q\phi(u_{i})u_{i}-y_{i}\rVert_{\mathcal{U}}^{2}.$
(28)

We can now reformulate Problem 1 as the regularized least squares problem

$\min_{Q\in\mathscr{B}^{+}(\mathcal{W})}L(Q)+\gamma\lVert Q\rVert,$ (29)

where $\lVert\cdot\rVert$ is the operator norm and $\gamma>0$. We can obtain a
representer theorem for this problem under the condition that $\mathcal{U}$ is
finite-dimensional. Therefore, for the remainder of this paper, we will assume
that $\mathcal{U}$ is finite-dimensional.

Consider the subspace $\hat{\mathcal{W}}\subset\mathcal{W}$ given by

$\hat{\mathcal{W}}=\sum_{i=1}^{n}\operatorname{im}\phi(u_{i})$ (30)

Since $\mathcal{U}$ is finite-dimensional, it follows that $\hat{\mathcal{W}}$
is also finite-dimensional. Let $\Pi\in\mathscr{B}(\mathcal{W})$ be the
orthogonal projection onto $\hat{\mathcal{W}}$. This means that
$\operatorname{im}\Pi=\hat{\mathcal{W}}$, $\Pi^{2}=\Pi$ and $\Pi^{*}=\Pi$.
Consider the following lemma.

###### Lemma 1

The following statements hold:

  1. 1.

$L(\Pi Q\Pi)=L(Q)$ for all $Q\in\mathscr{B}(\mathcal{W})$;

  2. 2.

$\lVert\Pi Q\Pi\rVert\leq\lVert Q\rVert$ for all
$Q\in\mathscr{B}(\mathcal{W})$;

  3. 3.

$\Pi Q\Pi\in\mathscr{B}^{+}(\mathcal{W})$ for all
$Q\in\mathscr{B}^{+}(\mathcal{W})$.

###### Proof:

Statement 1) holds because $\Pi\phi(u_{i})=\phi(u_{i})$ and
$\phi(u_{i})^{*}\Pi=\phi(u_{i})^{*}$ for all $i\in[n]$. We also have that

$\langle\Pi Q\Pi w,w\rangle_{\mathcal{W}}=\langle Q\Pi w,\Pi
w\rangle_{\mathcal{W}}$ (31)

for all $Q\in\mathscr{B}(\mathcal{W})$ and $w\in\mathcal{W}$, hence statement
3) holds. To show that statement 2) holds as well, let
$Q\in\mathscr{B}(\mathcal{W})$ and note that $\lVert\Pi
w\rVert_{\mathcal{W}}\leq\lVert w\rVert_{\mathcal{W}}$ for all
$w\in\mathcal{W}$. Therefore, we have that $\lVert\Pi Q\Pi
w\rVert_{\mathcal{W}}\leq\lVert Q\Pi w\rVert_{\mathcal{W}}$ and $\lVert
w\rVert_{\mathcal{W}}\leq 1$ implies $\lVert\Pi w\rVert_{\mathcal{W}}\leq 1$
for all $w\in\mathcal{W}$. This implies that

$\displaystyle\lVert\Pi Q\Pi\rVert$ $\displaystyle=\sup_{\lVert w\rVert\leq
1}\lVert\Pi Q\Pi w\rVert_{\mathcal{W}}$ $\displaystyle\leq\sup_{\lVert
w\rVert\leq 1}\lVert Q\Pi w\rVert_{\mathcal{W}}$
$\displaystyle\leq\sup_{\lVert\Pi w\rVert\leq 1}\lVert Q\Pi
w\rVert_{\mathcal{W}}$ $\displaystyle\leq\lVert Q\rVert$

and, thus, statement 3) holds. ∎

The first two statements of Lemma 1 tell us that the cost in (29) does not
increase when $Q$ is replaced by $\Pi Q\Pi$. Together with the third
statement, this implies that

$\min_{Q\in\mathscr{B}^{+}(\mathcal{W})}L(Q)+\gamma\lVert
Q\rVert=\min_{\hat{Q}\in\hat{\mathcal{Q}}}L(\hat{Q})+\gamma\lVert\hat{Q}\rVert,$
(32)

where $\hat{\mathcal{Q}}=\left\\{\Pi Q\Pi\,\left|\,\vphantom{\Pi
Q\Pi}Q\in\mathscr{B}^{+}(\mathcal{W})\right.\right\\}\subset\mathscr{B}^{+}(\mathcal{W})$.
In the following, we will show that $\hat{\mathcal{Q}}$ has a finite
parametrization. To this end, let the operator
$\Phi\in\mathscr{B}(\mathcal{U}^{n},\mathcal{W})$ be given by

$\Phi=\begin{bmatrix}\phi(u_{1})&\cdots&\phi(u_{n})\end{bmatrix}$ (33)

and consider the following lemma.

###### Lemma 2

There exist a self-adjoint operator $N\in\mathscr{B}(\mathcal{U}^{n})$ such
that $\Pi=\Phi N\Phi^{*}$.

###### Proof:

Suppose that the dimension of $\hat{\mathcal{W}}$ is $K\in\mathbb{N}$ and let
$\\{w_{1},\dots,w_{K}\\}$ be an orthonormal basis for $\hat{\mathcal{W}}$. It
is well-known [18, Proposition 4.7] that $\Pi=\sum_{k=1}^{K}w_{i}w_{i}^{*}$.
Since $w_{k}\in\hat{\mathcal{W}}$ for all $k\in[K]$, there exist
$v_{k,i}\in\mathcal{U}$, $i\in[n]$, such that
$w_{k}=\sum_{i=1}^{n}\phi(u_{i})v_{k,i}$. Consequently, we obtain

$\Pi=\sum_{k=1}^{K}\sum_{i,j=1}^{n}\phi(u_{i})v_{k,i}v_{k,j}^{*}\phi(u_{j})^{*}$
(34)

hence the operators $N_{ij}=\sum_{k=1}^{K}v_{k,i}v_{k,j}^{*}$, $i,j\in[n]$,
are such that $\Pi=\sum_{i,j=1}^{n}\phi(u_{i})N_{ij}\phi(u_{j})^{*}$. In other
words, we have that $\Pi=\Phi N\Phi^{*}$ with
$N\in\mathscr{B}(\mathcal{U}^{n})$ given by

$N=\begin{bmatrix}N_{11}&\cdots&N_{1n}\\\ \vdots&\ddots&\vdots\\\
N_{n1}&\cdots&N_{nn}\end{bmatrix}$ (35)

Since $N_{ij}^{*}=N_{ji}$ for all $i,j\in[n]$, it follows that $N$ is self-
adjoint, which concludes the proof. ∎

The following lemma is a direct consequence of Lemma 2.

###### Lemma 3

We have that $\hat{\mathcal{Q}}=\left\\{\Phi M\Phi^{*}\,\left|\,\vphantom{\Phi
M\Phi^{*}}M\in\mathscr{B}^{+}(\mathcal{U}^{n})\right.\right\\}$.

###### Proof:

Let $\hat{Q}=\Phi M\Phi^{*}$ for some $M\in\mathscr{B}^{+}(\mathcal{U}^{n})$.
Since $\Pi\phi(u_{i})=\phi(u_{i})$ for all $i\in[n]$, it follows that
$\hat{Q}=\Pi\hat{Q}\Pi$. Furthermore, since $M$ is nonnegative, it follows
that

$\langle\hat{Q}w,w\rangle_{\mathcal{W}}=\langle\Phi
M\Phi^{*}w,w\rangle_{\mathcal{W}}=\langle
M\Phi^{*}w,\Phi^{*}w\rangle_{\mathcal{U}^{n}}\geq 0$

for all $w\in\mathcal{W}$, hence $\hat{Q}\in\mathscr{B}^{+}(\mathcal{W})$ and,
thus, $\hat{Q}\in\hat{\mathcal{Q}}$. For the converse, let
$\hat{Q}\in\hat{\mathcal{Q}}$, i.e., $\hat{Q}=\Pi Q\Pi$ with
$Q\in\mathscr{B}^{+}(\mathcal{W})$. Due to Lemma 2, there exists a self-
adjoint $N\in\mathscr{B}(\mathcal{U}^{n})$ such that $\Pi=\Phi N\Phi^{*}$,
hence $\hat{Q}=\Phi M\Phi^{*}$ with $M\in\mathscr{B}(\mathcal{U}^{n})$ given
by $M=N\Phi^{*}Q\Phi N$. As $Q$ is nonnegative and $N$ is self-adjoint, it
follows that $M\in\mathscr{B}^{+}(\mathcal{U}^{n})$, ∎

Note that $\mathscr{B}(\mathcal{U}^{n})$ is finite-dimensional since
$\mathcal{U}$ is finite-dimensional. Therefore, Lemma 3 shows that
$\hat{\mathcal{Q}}$ has a finite parametrization. Furthermore, due to Lemma 1,
Lemma 3 and (32), a solution of (18) can be obtained by solving

$\min_{M\in\mathscr{B}^{+}(\mathcal{U}^{n})}L(\Phi M\Phi^{*})+\gamma\lVert\Phi
M\Phi^{*}\rVert.$ (36)

With this in mind, we obtain the following representer theorem for the problem
(18), which is the main result of this paper.

###### Theorem 1

Suppose that $\mathcal{U}$ is finite-dimensional. A solution of (29) exists if
and only if a solution of (36) exists. Moreover, if it exists, a solution of
(29) is given by

$\hat{Q}=\Phi M\Phi^{*},$ (37)

where $M\in\mathscr{B}^{+}(\mathcal{U}^{n})$ is a solution of (36).

###### Proof:

Suppose that $Q\in\mathscr{B}^{+}(\mathcal{W})$ is a solution of (29). Due to
Lemma 1, it follows that $\Pi Q\Pi$ is nonnegative and

$L(\Pi Q\Pi)+\lVert\Pi Q\Pi\rVert\leq L(Q)+\lVert Q\rVert.$ (38)

Since $Q$ is a solution of (29), the latter holds with equality and
$\hat{Q}=\Pi Q\Pi\in\hat{\mathcal{Q}}$ is also a solution of (29). Due to
Lemma 3, there exists $M\in\mathscr{B}^{+}(\mathcal{U}^{n})$ such that
$\hat{Q}=\Phi M\Phi^{*}$. As $\hat{Q}$ is a solution of (29), we obtain

$L(\hat{Q})+\lVert\hat{Q}\rVert\leq L(Q^{\prime})+\lVert Q^{\prime}\rVert$
(39)

for all $Q^{\prime}\in\mathscr{B}^{+}(\mathcal{W})$ and, in particular, for
all $Q^{\prime}=\Phi M^{\prime}\Phi^{*}$, where
$M^{\prime}\in\mathscr{B}^{+}(\mathcal{U}^{n})$. This implies that

$L(\Phi M\Phi^{*})+\lVert\Phi M\Phi^{*}\rVert\leq L(\Phi
M^{\prime}\Phi^{*})+\lVert\Phi M^{\prime}\Phi^{*}\rVert$ (40)

for all $M^{\prime}\in\mathscr{B}^{+}(\mathcal{U}^{n})$ and, thus, $M$ is a
solution of (36).

To show the converse, suppose that $M$ is a solution of (36). We will show
that $\Phi M\Phi^{*}\in\mathscr{B}^{+}(\mathcal{W})$ is a solution of (29).
Let $Q\in\mathscr{B}^{+}(\mathcal{W})$ and note that (38) holds due to Lemma
1. Furthermore, due to Lemma 3, there exists
$M^{\prime}\in\mathscr{B}^{+}(\mathcal{U}^{n})$ such that $\Pi Q\Pi=\Phi
M^{\prime}\Phi^{*}$. Now, (40) holds because $M$ is a solution of (36).
Together with (38), this implies that

$L(\Phi M\Phi^{*})+\lVert\Phi M\Phi^{*}\rVert\leq L(Q)+\lVert Q\rVert$ (41)

Since the latter holds for arbitrary $Q\in\mathscr{B}^{+}(\mathcal{W})$, it
follows that $\hat{Q}=\Phi M\Phi^{*}$ is a solution of (29). ∎

Recall that any $M\in\mathscr{B}(\mathcal{U}^{n})$ is of the form (4), where
$M_{ij}\in\mathscr{B}(\mathcal{U})$, $i,j\in[n]$. Therefore, we can rewrite
(37) as

$\hat{Q}=\sum_{i,j=1}^{n}\phi(u_{i})M_{ij}\phi(u_{j})^{*}$ (42)

Note the parallel between (23) and (29), as well as (24) and (42). In
particular, while (24) is a linear combination of features, (42) can be
interpreted as a sum of squares of features. We point out that, unlike the
representer theorem stated in Proposition 2, Theorem 1 does not tell us that a
solution of (29) exists or that the solution is unique if it does exist.
Nevertheless, Theorem 1 paves the way to a computationally tractable solution
of Problem 1 in the case where $\mathcal{U}$ is finite-dimensional. Indeed, in
the next section we will show that a solution of Problem 1 can be obtained by
solving an associated semidefinite program.

Before we do that, we note that the operator $G:\mathcal{U}\to\mathcal{U}$
corresponding to (37) is given by

$Gu=\kappa(u)^{*}M\kappa(u)u,$ (43)

where $\kappa(u)\in\mathscr{B}(\mathcal{U},\mathcal{U}^{n})$ is given by

$\kappa(u)=\Phi^{*}\phi(u)=\begin{bmatrix}k(u_{1},u)\\\ \vdots\\\
k(u_{n},u)\end{bmatrix},$ (44)

and $k:\mathcal{U}\times\mathcal{U}\to\mathscr{B}(\mathcal{U})$ is the
reproducing kernel corresponding to the the feature map $\phi$, i.e.,
$k(v_{1},v_{2})=\phi(v_{1})^{*}\phi(v_{2})$. This means that evaluation of $G$
does not require evaluation of the feature map $\phi$, but only of the kernel
$k$ corresponding to $\phi$. In fact, it can be shown that solving (36) also
does not require evaluation of $\phi$. To this end, note that

$L(\Phi M\Phi^{*})=\sum_{i=1}^{n}\lVert
K_{i}^{*}MK_{i}u_{i}-y_{i}\rVert^{2}_{\mathcal{U}},$ (45)

where $K_{i}=\kappa(u_{i})\in\mathscr{B}(\mathcal{U}^{n},\mathcal{U})$ for all
$i\in[n]$. The Gram operator associated with $k$ and $u_{1},\dots,u_{n},$ is
given by

$K=\begin{bmatrix}K_{1}&\cdots&K_{n}\end{bmatrix}=\Phi^{*}\Phi.$ (46)

Since $K\in\mathscr{B}(\mathcal{U}^{n})$ is self-adjoint and nonnegative,
there exists a self-adjoint and nonnegative
$K^{\frac{1}{2}}\in\mathscr{B}(\mathcal{U}^{n})$ such that
$K^{\frac{1}{2}}K^{\frac{1}{2}}=K$, and we have the following lemma.

###### Lemma 4

We have that

$\lVert\Phi M\Phi^{*}\rVert=\|K^{\frac{1}{2}}MK^{\frac{1}{2}}\|$ (47)

for all $M\in\mathscr{B}(\mathcal{U}^{n})$.

###### Proof:

As $\mathcal{U}$ is finite-dimensional and
$\Phi\in\mathscr{B}(\mathcal{U}^{n},\mathcal{W})$, it follows that
$\operatorname{im}\Phi$ is finite-dimensional. Consequently, for all
$w\in\mathcal{W}$, we can write $w=\Phi x+z$, where $x\in\mathcal{U}^{n}$ and
$z\in(\operatorname{im}\Phi)^{\perp}=\ker\Phi^{*}$. Using this, we obtain

$\lVert\Phi M\Phi^{*}w\rVert^{2}_{\mathcal{W}}=\lVert\Phi
MKx\rVert^{2}_{\mathcal{W}},$ (48)

where we used the fact that $K=\Phi^{*}\Phi$. This implies that

$\lVert\Phi M\Phi^{*}\rVert^{2}=\sup_{\lVert\Phi x\rVert_{\mathcal{W}}\leq
1}\lVert\Phi MKx\rVert^{2}_{\mathcal{W}}.$ (49)

Since $K^{\frac{1}{2}}K^{\frac{1}{2}}=\Phi^{*}\Phi$ and $K^{\frac{1}{2}}$ is
self-adjoint, we have that

$\lVert\Phi x\rVert_{\mathcal{W}}^{2}=\langle\Phi x,\Phi
x\rangle_{\mathcal{W}}=\|{K^{\frac{1}{2}}x}\|_{\mathcal{U}^{n}}^{2},$ (50)

We also have that $\lVert\Phi
MKx\rVert^{2}_{\mathcal{W}}=\|{K^{\frac{1}{2}}MKx}\|_{\mathcal{U}^{n}}^{2}$
and, thus,

$\lVert\Phi
M\Phi^{*}\rVert^{2}=\sup_{\|{K^{\frac{1}{2}}x}\|_{\mathcal{U}^{n}}\leq
1}\|{K^{\frac{1}{2}}MKx}\|^{2}_{\mathcal{U}^{n}}.$ (51)

Since $\operatorname{im}K^{\frac{1}{2}}$ is finite-dimensional,
$z\in\mathcal{U}^{n}$ can be written as $z=K^{\frac{1}{2}}x+z^{\prime}$ with
$x\in\mathcal{U}^{n}$ and
$z^{\prime}\in\operatorname{im}(K^{\frac{1}{2}})^{\perp}=\ker
K^{\frac{1}{2}}$. Then, (51) implies that

$\lVert\Phi M\Phi^{*}\rVert^{2}=\sup_{\|{z}\|_{\mathcal{U}^{n}}\leq
1}\|{K^{\frac{1}{2}}MK^{\frac{1}{2}}z}\|^{2}_{\mathcal{U}^{n}}=\|{K^{\frac{1}{2}}MK^{\frac{1}{2}}}\|^{2},$

and, thus, (47) holds. ∎

As an immediate consequence of (45) and (47), we obtain the following
corollary of Theorem 1.

###### Corollary 1

If it exists, a solution of (29) is given by (37), where
$M\in\mathscr{B}(\mathcal{U}^{n})$ is a solution of

$\min_{M\in\mathscr{B}^{+}(\mathcal{U}^{n})}\sum_{i=1}^{n}\lVert
K_{i}^{*}MK_{i}u_{i}-y_{i}\rVert^{2}_{\mathcal{U}}+\lVert
K^{\frac{1}{2}}MK^{\frac{1}{2}}\rVert.$ (52)

Moreover, the operator $G:\mathcal{U}\to\mathcal{U}$ corresponding to this
solution is given by (43).

Corollary 1 shows that a solution of Problem 1 can be obtained by solving
(52). Note that all operators in (52) belong to
$\mathscr{B}(\mathcal{U}^{n})$, which is finite-dimensional, hence Corollary 1
provides a computationally tractable solution of Problem 1. In the next
section, we will show how this solution can be obtained by solving an
associated semidefinite program.

##  VI Computional aspects

In this section, we will show how to obtain a solution of Problem 1 by solving
an associated semidefinite program. To this end, since $\mathcal{U}$ is
finite-dimensional, it is isometrically isomorphic to $\mathbb{R}^{m}$ for
some $m\in\mathbb{N}$. Therefore without loss of generality, we can assume
that $\mathcal{U}=\mathbb{R}^{m}$ with the Euclidian inner-product
$\langle\cdot,\cdot\rangle_{2}$ and induced norm $\lVert\cdot\rVert_{2}$. Now,
consider (52). Note that $\mathscr{B}^{+}(\mathcal{U}^{n})$ consists of
matrices $M\in\mathbb{R}^{nm\times nm}$ such that $M+M^{\top}$ is symmetric
positive semidefinite, which we denote by $M+M^{\top}\geq 0$. Furthermore, we
have that

$K_{i}\in\mathbb{R}^{mn\times m},\quad K^{\frac{1}{2}}\in\mathbb{R}^{nm\times
nm},\quad K^{\frac{1}{2}}\in\mathbb{R}^{nm\times nm}$ (53)

where $K\geq 0$ and $K^{\frac{1}{2}}\geq 0$. It is well known, see, e.g.,
[19], that $\lVert K_{i}^{\top}MK_{i}u_{i}-y_{i}\rVert^{2}_{2}\leq p_{i}$,
$i\in[n]$, if and only if

$\begin{bmatrix}I&K_{i}^{\top}MK_{i}u_{i}-y_{i}\\\
u_{i}^{\top}K_{i}^{\top}M^{\top}K_{i}-y_{i}^{\top}&p_{i}\end{bmatrix}\geq 0.$
(54)

Similarly, $\lVert K^{\frac{1}{2}}MK^{\frac{1}{2}}\rVert\leq p_{0}$ if and
only if

$\begin{bmatrix}p_{0}I&K^{\frac{1}{2}}MK^{\frac{1}{2}}\\\
K^{\frac{1}{2}}M^{\top}K^{\frac{1}{2}}&p_{0}I\end{bmatrix}\geq 0.$ (55)

It can be shown that the latter is equivalent to

$\begin{bmatrix}p_{0}K&KMK\\\ KM^{\top}K&p_{0}K\end{bmatrix}\geq 0,$ (56)

whose evaluation does not require the computation of the matrix
$K^{\frac{1}{2}}$. Indeed, (55) holds if and only if

$p_{0}(x_{1}^{\top}x_{1}+x_{2}^{\top}x_{2})+2x_{1}^{\top}K^{\frac{1}{2}}MK^{\frac{1}{2}}x_{2}\geq
0$ (57)

for all $x_{1},x_{2}\in\mathbb{R}^{mn}$. Since every $x\in\mathbb{R}^{mn}$ can
be written as $x=K^{\frac{1}{2}}\bar{x}+z$, where $\bar{x}\in\mathbb{R}^{mn}$
and $z\in\ker K^{\frac{1}{2}}$, it follows that (55) holds if and only if

$p_{0}(\bar{x}_{1}^{\top}K\bar{x}_{1}+\bar{x}_{2}^{\top}K\bar{x}_{2}+z_{1}^{\top}z_{1}+z_{2}^{\top}z_{2})+2\bar{x}_{1}^{\top}KMK\bar{x}_{2}\geq
0$

for all $\bar{x}_{1},\bar{x}_{2}\in\mathbb{R}^{mn}$ and $z_{1},z_{2}\in\ker
K^{\frac{1}{2}}$. Since $z_{1}^{\top}z_{1}\geq 0$ and $z_{2}^{\top}z_{2}\geq
0$ for all $z_{1},z_{2}\in\ker K^{\frac{1}{2}}$, it follows that (55) holds if
and only if

$p_{0}(\bar{x}_{1}^{\top}K\bar{x}_{1}+\bar{x}_{2}^{\top}K\bar{x}_{2})+2\bar{x}_{1}^{\top}KMK\bar{x}_{2}\geq
0,$ (58)

for all $\bar{x}_{1},\bar{x}_{2}\in\mathbb{R}^{mn}$, that is, (56) holds. With
this in mind, the following corollary of Theorem 1 is an immediate consequence
of Corollary 1.

###### Corollary 2

Suppose that $\mathcal{U}=\mathbb{R}^{m}$. If it exists, a solution of (52)
can be obtained by solving the semidefinite program

$\displaystyle\min$ $\displaystyle\sum_{i=1}^{n}p_{i}+\gamma p_{0}$ s.t.
$\displaystyle M+M^{\top}\geq 0\text{ and
}\eqref{eq:SDP_pi},\eqref{eq:SDP_p0_re}\text{ hold for all }i\in[n]$

Moreover, the operator $G:\mathbb{R}^{m}\to\mathbb{R}^{m}$ corresponding to
this solution is given by (43).

##  VII Illustrative example

In this section, we will demonstrate how our results can be used in practice.
Consider the nonlinear system

$\displaystyle 2\ddot{q}+\ddot{\theta}\cos(\theta)$
$\displaystyle=\dot{\theta}^{2}\sin(\theta)-q$ (59) $\displaystyle
2\ddot{\theta}+\ddot{q}\cos(\theta)$ $\displaystyle=u$ $\displaystyle y$
$\displaystyle=\dot{\theta}$

The latter describes the motion of a rotational/translational proof mass
actuator [20]. For simplicity, we have neglected disturbances and taken all
parameters to be equal to 1.

Let $T>0$ and $\mathcal{U}=L_{2}([0,T],\mathbb{R})$. We can view (59) as an
operator $G_{\textup{true}}:\mathcal{U}\to\mathcal{U}$ that maps the input
signal $u\in\mathcal{U}$ to the corresponding output signal
$G_{\textup{true}}u\in\mathcal{U}$ generated by (59), where the system is
initially at rest, i.e.,

$q(0)=0,\quad\dot{q}(0)=0,\quad\theta(0)=0,\quad\dot{\theta}(0)=0.$ (60)

It can be shown that $G_{\textup{true}}$ is passive, hence, in particular,
$G_{\textup{true}}$ is nonnegative. Now, suppose that we are given a data set
consisting of $n\in\mathbb{N}$ input-output signals

$(u_{i},y_{i})\in\mathcal{U}\times\mathcal{U},\quad i\in[n],$ (61)

generated by the system (59). We are interested in identifying a nonnegative
operator $G:\mathcal{U}\to\mathcal{U}$ that fits the data well, i.e.,
$Gu_{i}\approx y_{i}$ for all $i\in[n]$. Since $\mathcal{U}$ is infinite-
dimensional, we cannot use our results directly. We circumvent this issue by
restricting to a finite-dimensional subspace of $\mathcal{U}$.

To this end, we can approximate signals in $\mathcal{U}$ to arbitrary
precision by a finite-degree polynomial. In particular, we can approximate
signals using the first $m$ Legendre polynomials [21], where $m$ is as large
as necessary to achieve a desired accuracy of the approximation. We refer the
reader to [22] for an example of the use of Legendre polynomials in control.

Recall [21, Section 2.3.2] that the Legendre polynomials on the interval
$[-1,1]$ are given by $L_{1}(t)=1$, $L_{2}(t)=t$, and the recurrence relation

$\frac{\textrm{d}}{\textrm{d}t}L_{i+2}=\frac{\textrm{d}}{\textrm{d}t}L_{i}+(2i+2)L_{i+1},\quad
i\in\mathbb{N}.$ (62)

The Legendre polynomials on the interval $[0,T]$ can be obtained via the
transformation $t\mapsto\frac{T}{2}(t+1)$. We assume that each Legendre
polynomial is scaled so that $\lVert L_{i}\rVert_{\mathcal{U}}=1$ for all
$i\in\mathbb{N}$. As such, the Legendre polynomials form an orthonormal basis
for $\mathcal{U}$, i.e., every $u\in\mathcal{U}$ can be written as
$u=\sum_{i=1}^{\infty}c_{i}L_{i}$ for some coefficients $c_{i}\in\mathbb{R}$,
$i\in\mathbb{N}$, which we call the _Legendre coefficients_ of $u$. Therefore,
$G_{\textup{true}}$ is associated with an operator $\tilde{G}_{\textup{true}}$
that maps the Legendre coefficients of $u$ to the Legendre coefficients of
$G_{\textup{true}}u$. Since the Legendre polynomials are orthonormal,
$G_{\textup{true}}$ is nonnegative if and only if $\tilde{G}_{\textup{true}}$
is nonnegative.

With this in mind, let $m\in\mathbb{N}$ be such that the first $m$ Legendre
polynomials can be used to accurately approximate the data set (61). Given a
desired precision, an appropriate $m$ can be determined by using existing
error bounds, see [21, Section 5.4] for details. The approximation yields a
data set consisting of $n\in\mathbb{N}$ coefficient vectors

$(\tilde{u}_{i},\tilde{y}_{i})\in\mathbb{R}^{m}\times\mathbb{R}^{m},\quad
i\in[n],$ (63)

such that $u_{i}\approx\sum_{j=1}^{m}\tilde{u}_{ij}L_{i}$ and
$y_{i}\approx\sum_{j=1}^{m}\tilde{y}_{ij}L_{i}$, where $\tilde{u}_{ij}$ and
$\tilde{y}_{ij}$ are the $j$’th entries of $\tilde{u}_{i}$ and
$\tilde{y}_{i}$, respectively. Now, we are interested in identifying a
nonnegative operator $\tilde{G}:\mathbb{R}^{m}\to\mathbb{R}^{m}$ that fits the
data well, i.e., $\tilde{G}\tilde{u}_{i}\approx\tilde{y}_{i}$ for all
$i\in[n]$. This would correspond to a nonnegative operator
$G:\tilde{\mathcal{U}}\to\tilde{\mathcal{U}}$, where
$\tilde{\mathcal{U}}\subset\mathcal{U}$ is given by the linear span of the
first $m$ Legendre polynomials. This operator $G$ is expected to be a good
approximation of $G_{\textup{true}}$ when the input signal is restricted (or
close) to $\tilde{\mathcal{U}}$.

To illustrate the effectiveness of this approach, we consider the following
specific example. Let $T=20$, $n=9$ and consider the data set (61), where

$u_{i}=\begin{dcases}L_{i}&i\in\\{1,\dots,5\\},\\\
L_{i-5}+L_{i-4}&i\in\\{6,\dots,9\\}.\end{dcases}$ (64)

This means that the first 5 Legendre polynomials can be used to exactly
represent the input signals $u_{i}$, $i\in[9]$. Approximating the
corresponding output signals $y_{i}$, $i\in[9]$, using the first 10 Legendre
polynomials yields relative errors less than $10^{-4}$. This is small enough
for the purposes of this example, hence we take $m=10$. Next, we solve the
semidefinite program in Corollary 2, where $\gamma=10^{-3}$ and the data set
is given by the corresponding Legendre coefficient vectors (63). Furthermore,
we use a simple Gaussian kernel

$k(\tilde{v}_{1},\tilde{v}_{2})=e^{\frac{-\lVert\tilde{v}_{1}-\tilde{v}_{2}\rVert^{2}_{2}}{100^{2}}}I,$
(65)

where $\lVert\cdot\rVert_{2}$ is the Euclidian norm and
$I\in\mathbb{R}^{10\times 10}$ is the identity matrix. As can be seen on
Figure 1, the identified operator fits the data quite well; the true and
estimated outputs are almost indistinguishable and the data misfit is
approximately $1.6547\cdot 10^{-4}$. To test the identified operator, we
consider 1000 input signals given by linear combinations of the first 5
Legendre polynomials with coefficients from a uniform distribution on the
interval $[0,1]$. Then, we compute the relative error between the true output
signal generated by (59) and the estimated output signal generated by the
identified operator. We find that the average relative error is approximately
$3.7949\cdot 10^{-2}$.

$0$$5$$10$$15$$20$$-0.5$$0$$0.5$$1$ Figure 1: True (black, solid) and
estimated data outputs with the Gaussian kernel (red, dashed).
$0$$5$$10$$15$$20$$-0.2$$0$$0.2$$0.4$ Figure 2: True (black, solid) and
estimated outputs with the Gaussian (red, dashed), Laplacian (red, dot-dashed)
and bilinear (red, dotted) kernels.

We perform the same tests with the identified operators when using the
Laplacian and bilinear kernels, given by

$k(\tilde{v}_{1},\tilde{v}_{2})=e^{\frac{-\lVert\tilde{v}_{1}-\tilde{v}_{2}\rVert_{2}}{100}}I\quad\text{and}\quad
k(\tilde{v}_{1},\tilde{v}_{2})=\tilde{v}_{1}^{\top}\tilde{v}_{2}I,$ (66)

respectively. We find that the data misfit and average relative error when
using the Laplacian kernel are approximately $2.2123\cdot 10^{-7}$ and
$8.3060\cdot 10^{-2}$, respectively. On the other hand, the data misfit and
average relative error when using the bilinear kernel are approximately
$3.5530\cdot 10^{-7}$ and 1.3889, respectively. An example comparison between
the true output signal and the estimated output signals of each of these
identified operators is seen on Figure 2. We see that the Gaussian kernel
performs the best, closely followed by the Laplacian kernel, whereas the
bilinear kernel performs significantly worse.

##  VIII Conclusion

In this paper, we treated the problem of identifying a nonnegative operator
from given input-output trajectories. We considered a class of input-output
operators defined via a feature map and an arbitrary nonnegative bounded
linear operator in a “sum of squares” fashion, such that nonnegativity of the
input-output operator is guaranteed. Then, we cast the identification problem
as a regularized least squares problem over a cone of nonnegative bounded
linear operators. As our main result, we proved a representer theorem for this
problem in the case where the input space is finite-dimensional. We also
showed that the latter provides a computationally tractable solution which can
be obtained by solving an associated semidefinite program. For future
research, in addition to nonnegativity, we will investigate the problem of
imposing causality of the identified input-output operator.

## References

  * [1] G. Pillonetto, M. H. Quang, and A. Chiuso, “A new kernel-based approach for nonlinear system identification,” IEEE Transactions on Automatic Control, vol. 56, no. 12, pp. 2825–2840, 2011.
  * [2] G. Pillonetto, F. Dinuzzo, T. Chen, G. De Nicolao, and L. Ljung, “Kernel methods in system identification, machine learning and function estimation: A survey,” Automatica, vol. 50, no. 3, pp. 657–682, 2014.
  * [3] F. Dinuzzo, “Kernels for linear time invariant system identification,” SIAM Journal on Control and Optimization, vol. 53, no. 5, pp. 3299–3317, 2015\.
  * [4] L. Ljung, T. Chen, and B. Mu, “A shift in paradigm for system identification,” International Journal of Control, vol. 93, no. 2, pp. 173–180, 2020.
  * [5] N. Aronszajn, “Theory of reproducing kernels,” Transactions of the American Mathematical Society, vol. 68, no. 3, pp. 337–404, 1950.
  * [6] V. I. Paulsen and M. Raghupathi, An Introduction to the Theory of Reproducing Kernel Hilbert Spaces.  Cambridge Studies in Advanced Mathematics, Cambridge University Press, 2016.
  * [7] G. Pillonetto and A. Chiuso, “Identification of stable linear systems via the sequential stabilizing spline algorithm,” IFAC-PapersOnLine, vol. 51, no. 15, pp. 19–24, 2018.
  * [8] C. Grussler, J. Umenberger, and I. R. Manchester, “Identification of externally positive systems,” in IEEE Conference on Decision and Control, pp. 6549–6554, 2017.
  * [9] M. Khosravi and R. S. Smith, “Kernel-based identification of positive systems,” in Proceedings of the 58th IEEE Conference on Decision and Control, pp. 1740–1745, 2019.
  * [10] P. Rapisarda and H. Trentelman, “Identification and data-driven model reduction of state-space representations of lossless and dissipative systems from noise-free data,” Automatica, vol. 47, no. 8, pp. 1721–1728, 2011\.
  * [11] H. J. van Waarde and R. Sepulchre, “Kernel-based models for system analysis,” IEEE Transactions on Automatic Control, vol. 68, no. 9, pp. 5317–5332, 2023\.
  * [12] J. Umenberger and I. R. Manchester, “Specialized interior-point algorithm for stable nonlinear system identification,” IEEE Transactions on Automatic Control, vol. 64, no. 6, pp. 2442–2456, 2019.
  * [13] M. F. Shakib, A. Y. Pogromsky, A. Pavlov, and N. van de Wouw, “Computationally efficient identification of continuous-time Lur’e-type systems with stability guarantees,” Automatica, vol. 136, p. 110012, 2022\.
  * [14] U. Marteau-Ferey, F. Bach, and A. Rudi, “Non-parametric models for non-negative functions,” in Proceedings of the 34th International Conference on Neural Information Processing Systems, 2020.
  * [15] C. A. Desoer and M. Vidyasagar, Feedback Systems.  Society for Industrial and Applied Mathematics, 2009.
  * [16] C. A. Micchelli and M. Pontil, “On Learning Vector-Valued Functions,” Neural Computation, vol. 17, no. 1, pp. 177–204, 2005.
  * [17] Y. Kalnishkan, “An introduction to kernel methods,” Technical Report, available at https://cml.rhul.ac.uk/publications/files/tr0901.pdf, 2009.
  * [18] J. B. Conway, A Course in Functional Analysis.  Springer New York, 2007.
  * [19] L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Review, vol. 38, no. 1, pp. 49–95, 1996.
  * [20] R. Bupp, D. Bernstein, and V. Coppola, “A benchmark problem for nonlinear control design: problem statement, experimental testbed, and passive nonlinear compensation,” in Proceedings of American Control Conference, vol. 6, pp. 4363–4367 vol.6, 1995.
  * [21] C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Zang, Spectral Methods: Fundamentals in Single Domains.  Springer Berlin Heidelberg, 2006.
  * [22] P. Rapisarda, H. van Waarde, and M. Camlibel, “Orthogonal polynomial bases for data-driven analysis and control of continuous-time systems,” IEEE Transactions on Automatic Control, pp. 1–12, 2023.