# Valued FIELDs WITH A total RESIDUE MAP

Konstantinos Kartas

###### Abstract.

When $k$ is a finite field, Becker-Denef-Lipschitz (1979) observed that the
total residue map $\text{res}:k(\\!(t)\\!)\to k$, which picks out the constant
term of the Laurent series, is definable in the language of rings with a
parameter for $t$. Driven by this observation, we study the theory
$\text{VF}_{\text{res},\iota}$ of valued fields equipped with a linear form
$\text{res}:K\to k$ which restricts to the residue map on the valuation ring.
We prove that $\text{VF}_{\text{res},\iota}$ does not admit a model companion.
In addition, we show that $(k(\\!(t)\\!),\text{res})$ is undecidable whenever
$k$ is an infinite field. As a consequence, we get that
$({\mathbb{C}}(\\!(t)\\!),\text{Res}_{0})$ is undecidable, where
$\text{Res}_{0}:f\mapsto\text{Res}_{0}(f)$ maps $f$ to its complex residue at
$0$.

During this research, the author was funded by EPSRC grant EP/20998761 and was
also supported by the Onassis Foundation - Scholarship ID: F ZP
020-1/2019-2020.

## Introduction

Let $k$ be a field. Consider the power series field $k(\\!(t)\\!)$ and let
$\text{res}:k(\\!(t)\\!)\to k$ be the total residue map

$\text{res}:\sum_{i=-N}^{\infty}c_{i}t^{i}\mapsto c_{0}$

Viewing $k(\\!(t)\\!)$ as a $k$-vector space, we see that
$\text{res}:k(\\!(t)\\!)\to k$ is a linear form which extends the usual
residue map $\pi:k[\\![t]\\!]\to k$ to all of $k(\\!(t)\\!)$ (hence the name
total). The motivation for studying the model-theory of this structure is
twofold:

  1. (1)

In complex analysis, one defines the residue of a complex meromorphic function
$f\in\mathbb{C}(\\!(t)\\!)$ at an isolated singularity $a\in\mathbb{C}$,
denoted by $\text{Res}(f,a)$ or $\text{Res}_{a}(f)$. The map res is
essentially a shifted version of
$\text{Res}_{0}:\mathbb{C}(\\!(t)\\!)\to\mathbb{C}:f\mapsto\text{Res}_{0}(f)$,
namely $\text{res}(t\cdot f)=\text{Res}_{0}(f)$.

  2. (2)

Becker-Denef-Lipschitz [BDL79] showed for $x\in\mathbb{F}_{p}(\\!(t)\\!)$ that
$\text{res}(x)=0$ precisely when there exist
$x_{0},x_{1},...,x_{p-1}\in\mathbb{F}_{p}(\\!(t)\\!)$ such that

$x=x_{0}^{p}-x_{0}+tx_{1}^{p}+....+t^{p-1}x_{p-1}^{p}$

This easily implies that
$\text{res}:\mathbb{F}_{p}(\\!(t)\\!)\to\mathbb{F}_{p}$ is definable in
$L_{\text{rings}}$ with a parameter for $t$. Becker-Denef-Lipschitz used this
to show that $\mathbb{F}_{p}(\\!(t)\\!)$ is undecidable in the language of
valued fields with a cross-section. This was in sharp contrast with the result
by Ax-Kochen [AK66] and Ershov [Ers65]: For any decidable field $k$ of
characteristic $0$, the power series field $k(\\!(t)\\!)$ is decidable in the
language of valued fields with a cross-section.

Towards understanding the model theory of $\mathbb{F}_{p}(\\!(t)\\!)$, it may
be instructive to isolate such definable functions (or predicates) and study
them over $k(\\!(t)\\!)$, where $k$ is not necessarily finite. This approach
is largely influenced by Cherlin [Che82], especially Problems 3 and 4 in §5
[Che82].

In the present paper, we study the model theory of $k(\\!(t)\\!)$ equipped
with $\text{res}:k(\\!(t)\\!)\to k$. We also take this a step further and
study valued fields—not necessarily power series fields—enriched with a total
residue map $\text{res}:K\to k$. In the axiomatic setting, the total residue
map $\text{res}:K\to k$ is assumed to be a linear form extending the usual
residue map $\pi:{\mathcal{O}}_{K}\to k$, where ${\mathcal{O}}_{K}$ is the
valuation ring of $K$. We consider the theory of equal characteristic valued
fields $K$ with a total residue map $\text{res}:K\to k$ and a lift $\iota:k\to
K$ of the residue field, namely $\iota$ is a field embedding such that
$\pi\circ\iota=\text{id}_{k}$. We call $\text{VF}_{\text{res},\iota}$ the
resulting theory.

At first glance, the theory $\text{VF}_{\text{res},\iota}$ seems like an
innocent variant of VF. However, we will show the following:

######  Theorem A.

The theory $\text{VF}_{\text{res},\iota}$ does not admit a model companion.

This should be contrasted with the fact (due to A. Robinson) that the theory
VF of valued fields admits a model companion, namely ACVF, the theory of
algebraically closed valued fields. The theory $\text{VF}_{\iota}$ of valued
fields with a lift of the residue field still admits a model companion, namely
the theory $\text{ACVF}_{\iota}$ described by Hrushovski-Kazhdan §6 [HK09]
(there it is called $T_{loc}$). Indeed, they prove a quantifier-elimination
result for $\text{ACVF}_{\iota}$, which in fact—according to §6.1 [HK09]—goes
back to F. Delon.

We also prove:

######  Theorem B.

Let $k$ be an infinite field. Then $k(\\!(t)\\!)$ is undecidable in
$L_{\text{res}}$.

Here $L_{\text{res}}$ is the three-sorted language $L_{\text{val}}$ of valued
fields together with a function symbol for $\text{res}:k(\\!(t)\\!)\to k$. In
fact, we prove that the $\exists\forall$-theory is undecidable—at least when
$t$ is added in the language—and also that $(\mathbb{N},+,\cdot)$ is
interpretable (without parameters). The proof also applies to the Hahn series
field $k(\\!(t^{\Gamma})\\!)$, where $\Gamma$ is any non-trivial ordered
abelian group, and also to the Puiseux series field
$k\\{\\!\\{t\\}\\!\\}=\bigcup_{n\in\mathbb{N}}k(\\!(t^{1/n})\\!)$. As an
application, we get that ${\mathbb{C}}(\\!(t)\\!)$ and
${\mathbb{C}}\\{\\!\\{t\\}\\!\\}$ are undecidable in the language of valued
fields together with a function symbol for
$\text{Res}_{0}:f\mapsto\text{Res}_{0}(f)$ which maps $f$ to its complex
residue at $0$ (see Corollary 2.2.5).

##  1\. Valued Fields with a total residue map

We study valued fields of equal characteristic, together with a lift
$\iota:k\to K$ and a total residue map $\text{res}:K\to k$, which is a linear
form extending the residue map $\pi:{\mathcal{O}}_{K}\to k$. To simplify
notation, we identify $x\in k$ with its image $\iota(x)$ in $K$. It will
always be clear from context where such an $x$ lives.

###  1.1. Axiomatization of $\text{VF}_{\text{res},\iota}$

Let $L_{\text{val}}$ be the three-sorted language of valued fields with sorts
for the field, the value group and the residue field and a function symbol for
$v:K\to\Gamma\cup\\{\infty\\}$. We call $L_{\text{res},\iota}$ the enrichment
of $L_{\text{val}}$ which includes function symbols for $\iota$ and res.
Consider the following set of axioms in $L_{\text{res},\iota}$:

  1. (1)

$(K,v)$ is a valued field of equal characteristic and $\iota:k\to K$ is a
field embedding such that $\pi\circ\iota=\text{id}_{k}$.

  2. (2)

We have that $\text{res}|_{{\mathcal{O}}_{K}}=\pi$.

  3. (3)

$\text{res}:K\to k$ is $k$-linear, i.e. $\text{res}(\lambda a+\mu
b)=\lambda\text{res}(a)+\mu r(b)$, for all $\lambda,\mu\in k$.

Let $\text{VF}_{\text{res},\iota}$ be the $L_{\text{res},\iota}$-theory
generated by the above axioms.

######  Example 1.1.1.

Let $k$ be a field.

  1. (i)

Let $\Gamma$ be an ordered abelian group and $k(\\!(t^{\Gamma})\\!)$ be the
Hahn series field over $k$ with value group $\Gamma$. We have
$(k(\\!(t^{\Gamma})\\!),v_{t},\text{res},\iota)\models\text{VF}_{\text{res},\iota}$,
where

$\text{res}:\sum_{q\in\Gamma}c_{q}t^{q}\mapsto c_{0}$

and $\iota:k\to k(\\!(t^{\Gamma})\\!)$ is the obvious lift.

  2. (ii)

Similarly,
$(k\\{\\!\\{t\\}\\!\\},v_{t},\text{res},\iota)\models\text{VF}_{\text{res},\iota}$,
where $k\\{\\!\\{t\\}\\!\\}=\bigcup_{n\in\mathbb{N}}k(\\!(t^{1/n})\\!)$ is the
Puiseux series field over $k$.

###  1.2. Extensions of $L_{\text{res},\iota}$-structures

######  Lemma 1.2.1.

Let $(K,v,\iota)\subseteq(K^{\prime},v^{\prime},\iota^{\prime})$ be an
extension of valued fields with lifts of their residue fields. If
$\beta_{1},...,\beta_{n}\in k^{\prime}$ are $k$-linearly independent and
$a_{1},...,a_{n}\in K$, then

$v^{\prime}(\sum_{i=1}^{n}\beta_{i}a_{i})=\min_{1\leq i\leq n}v(a_{i})$

###### Proof.

We may assume that $v(a_{1})=...=v(a_{n})$. For each $1\leq i\leq n$, there
exist $\alpha_{i}\in k$ and $\varepsilon_{i}\in\mathfrak{m}$, such that
$a_{i}=\alpha_{i}\cdot a_{1}+\varepsilon_{i}\cdot a_{1}$. It follows that

$\sum_{i=1}^{n}\beta_{i}a_{i}=a_{1}\cdot(\sum_{i=1}^{n}\alpha_{i}\beta_{i}+\sum_{i=1}^{n}\beta_{i}\varepsilon_{i})$

Since the $\beta_{i}$’s are $k$-linearly independent, we get that
$\sum_{i=1}^{n}\alpha_{i}\beta_{i}\neq 0$ and hence
$v^{\prime}(\sum_{i=1}^{n}\alpha_{i}\beta_{i})=0$. Since
$v^{\prime}(\sum_{i=1}^{n}\beta_{i}\varepsilon_{i})>0$, we get that

$v^{\prime}(\beta_{1}a_{1}+...+\beta_{n}a_{n})=v(a_{1})+v(\sum_{i=1}^{n}\alpha_{i}\beta_{i}+\sum_{i=1}^{n}\beta_{i}\varepsilon_{i})=v(a_{1})$

as needed. ∎

Given $(K,v,\iota)\subseteq(K^{\prime},v^{\prime},\iota^{\prime})$, we denote
by $\langle K\rangle_{k^{\prime}}$ the $k^{\prime}$-linear span of $K$ inside
$K^{\prime}$. Note that $\langle K\rangle_{k^{\prime}}$ is isomorphic to
$K\otimes_{k}k^{\prime}$ as an $k^{\prime}$-vector space.

######  Lemma 1.2.2.

Let $(K,v,\iota)\subseteq(K^{\prime},v^{\prime},\iota^{\prime})$ be an
extension of valued fields with lifts of their residue fields. Then
${\mathcal{O}}_{K^{\prime}}\cap\langle
K\rangle_{k^{\prime}}=\langle{\mathcal{O}}_{K}\rangle_{k^{\prime}}$.

###### Proof.

First, we prove the following:
Claim:  Let $a_{1},...,a_{n}\in K$ be $k$-linearly independent over
${\mathcal{O}}_{K}$. Then $a_{1},...,a_{n}$ are also $l$-linearly independent
over ${\mathcal{O}}_{K^{\prime}}$.

###### Proof.

Suppose $\beta_{1}^{\prime},...,\beta_{n}^{\prime}\in k^{\prime}$ are such
that

$\sum_{i=1}^{n}\beta_{i}^{\prime}a_{i}\in{\mathcal{O}}_{K^{\prime}}$

Let $\\{\beta_{1},...,\beta_{m}\\}$ be a $k$-linear basis of
$\langle\beta_{1}^{\prime},...,\beta_{n}^{\prime}\rangle_{k}$ and write
$\beta_{i}^{\prime}=\sum_{j=1}^{m}c_{ij}\cdot\beta_{i}$ with $c_{ij}\in k$. We
will then have that

$\sum_{i=1}^{n}\beta_{i}^{\prime}a_{i}=\sum_{i=1}^{n}(\beta_{i}\sum_{j=1}^{m}c_{ij}a_{j})$

Since the $\beta_{i}$’s are $k$-linearly independent, Lemma 1.2.1 implies that

$v^{\prime}(\sum_{i=1}^{n}(\beta_{i}\sum_{j=1}^{m}c_{ij}a_{j})))=\min_{1\leq
i\leq n}\\{v(\sum_{j=1}^{m}c_{ij}a_{j})\\}$

For $i=1,...,n$, it follows that

$\sum_{j=1}^{m}c_{ij}a_{j}\in{\mathcal{O}}_{K}$

Since the $a_{i}$’s are $k$-linearly independent over ${\mathcal{O}}_{K}$, we
get that $c_{ij}=0$ for all $i,j$. Therefore $\beta_{i}^{\prime}=0$ for all
$i$ and the $a_{i}$’s are $k^{\prime}$-linearly independent over
${\mathcal{O}}_{K^{\prime}}$. ∎${}_{\textit{Claim}}$

Now let $V$ be a complement of the $k$-vector subspace
${\mathcal{O}}_{K}\subseteq K$, i.e., we have $K={\mathcal{O}}_{K}\oplus V$.
We will then have that $\langle
K\rangle_{k^{\prime}}=\langle{\mathcal{O}}_{K}\rangle_{k^{\prime}}+V_{k^{\prime}}$.
By the claim, we get that
$V_{k^{\prime}}\cap{\mathcal{O}}_{K^{\prime}}=\\{0\\}$ and since
$\langle{\mathcal{O}}_{K}\rangle_{k^{\prime}}\subseteq{\mathcal{O}}_{K^{\prime}}$,
we conclude that ${\mathcal{O}}_{K^{\prime}}\cap\langle
K\rangle_{k^{\prime}}=\langle{\mathcal{O}}_{K}\rangle_{k^{\prime}}$. ∎

######  Lemma 1.2.3.

Let $(K,v,\text{res},\iota)\models\text{VF}_{\text{res},\iota}$ and
$(K,v,\iota)\subseteq(K^{\prime},v^{\prime},\iota^{\prime})$. Let
$\\{e_{i}:i\in I\\}\subseteq L$ be $k^{\prime}$-linearly independent over
${\mathcal{O}}_{K^{\prime}}+\langle K\rangle_{k^{\prime}}$. Then there exists
an $k^{\prime}$-linear map $\text{res}^{\prime}:K^{\prime}\to k^{\prime}$
extending $\pi_{K^{\prime}}:{\mathcal{O}}_{K^{\prime}}\to k^{\prime}$ with
$\text{res}^{\prime}(e_{i})=0$ for all $i\in I$ and such that
$(K^{\prime},v^{\prime},\text{res}^{\prime},\iota^{\prime})$ is a model of
$\text{VF}_{\text{res},\iota}$ extending $(K,v,\text{res},\iota)$.

###### Proof.

First we extend $\text{res}:K\to k$ to $\text{res}^{\prime}:\langle
K\rangle_{k^{\prime}}\to k^{\prime}$ by extension of scalars:

$\text{res}^{\prime}(\beta\cdot a)=\beta\cdot\text{res}(a)$

for $\beta\in k^{\prime}$ and $a\in K$. By Lemma 1.2.2, if
$b\in{\mathcal{O}}_{K^{\prime}}\cap\langle K\rangle_{k^{\prime}}$, we may
write $b=\sum_{i=1}^{n}\beta_{i}a_{i}$, with $\beta_{i}\in k^{\prime}$ and
$a_{i}\in{\mathcal{O}}_{K}$. We now compute that

$\text{res}^{\prime}(b)=\sum_{i=1}^{n}\beta_{i}\cdot\text{res}^{\prime}(a_{i})=\sum_{i=1}^{n}\beta_{i}\cdot\text{res}(a_{i})=\sum_{i=1}^{n}\beta_{i}\cdot\pi_{K}(a_{i})=\pi_{L}(b)$

We may therefore extend $\text{res}:K\to k$ to
$\text{res}^{\prime}:{\mathcal{O}}_{K^{\prime}}+\langle
K\rangle_{k^{\prime}}\to k^{\prime}$ so that it restricts to res on $K$ and
also to $\pi_{K^{\prime}}$ on ${\mathcal{O}}_{K^{\prime}}$. Finally, we extend
the linear map $\text{res}^{\prime}$ to $K^{\prime}$ by requiring that
$\text{res}(e_{i})=0$ and get a model
$(K^{\prime},v^{\prime},\text{res}^{\prime},\iota^{\prime})$ of
$\text{VF}_{\text{res},\iota}$ extending $(K,v,\text{res},\iota)$, as
required. ∎

###  1.3. Structures on the rational function field

####  1.3.1. Extension by an infinitesimal

######  Fact 1.3.2 (Corollary 2.2.3 [EP05]).

Let $(K,v)$ be a valued field with value group $\Gamma$ and residue field $k$.
Let $\Gamma^{\prime}$ be an ordered abelian group extending $\Gamma$ and
$\gamma\in\Gamma^{\prime}$ be torsion-free over $\Gamma$, i.e., if
$n\cdot\gamma\in\Gamma$, then $n=0$. Then there is exactly one valuation $w$
on $K(X)$ extending $v$ with $w(X)=\gamma$. We have
$\Gamma_{K(X)}=\Gamma\oplus\mathbb{Z}\gamma$, with the ordering induced by
$\Gamma^{\prime}$, and $k_{K(X)}=k$.

######  Remark 1.3.3.

  1. (i)

It follows that there is a unique valuation $w$ on $K(X)$ such that
$wx>\Gamma$. We will have $k_{K(X)}=k$ and
$\Gamma_{K(X)}=\mathbb{Z}\gamma\oplus_{lex}\Gamma$.

  2. (ii)

A lift $\iota:k\to K$ of the valued field $(K,v)$ naturally induces a lift of
$(K(X),w)$, namely $\iota_{K(X)}:k\to K(X):\alpha\mapsto\iota(\alpha)$.

######  Lemma 1.3.4.

Let $(K,v,\text{res},\iota)\models\text{VF}_{\text{res},\iota}$. Let $w$ be
the unique valuation on $K(X)$ such that $w(X)>\Gamma$ and also let
$\iota_{K(X)}:k\to K(X)$ be the induced lift. Then there is a map
$\text{res}_{K(X)}:K(X)\to k$ with $\text{res}_{K(X)}(X^{-m})=0$ for all
$m\in\mathbb{N}$, such that $(K(X);w,\text{res}_{K(X)},\iota_{K(X)})$ is a
model of $\text{VF}_{\text{res},\iota}$ extending $(K,v,\text{res},\iota)$.

###### Proof.

By Lemma 1.2.3, it suffices to show that the elements
$X^{-1},X^{-2},...,X^{-n}$ are $k$-linearly independent over
$K+{\mathcal{O}}_{K(X)}$. Indeed, for any $c\in K$ and
$\beta_{1},...,\beta_{n}\in k$ with $\beta_{n}\neq 0$, we get that

$w(\sum_{i=1}^{n}\beta_{i}X^{-i}+c)=-n\cdot w(X)<0$

using that $w(X)>\Gamma$. ∎

######  Corollary 1.3.5.

Let $(K,v,\text{res},\iota)$ be an e.c. model of
$\text{VF}_{\text{res},\iota}$ and $n\in\mathbb{N}$. Then there exists
$a\in\mathfrak{m}-\\{0\\}$ such that $\text{res}(a^{-m})=0$ for $m=1,...,n$.

###### Proof.

Immediate from Lemma 1.3.4. ∎

####  1.3.6. Gauss valuation

The valuation described below is known as the Gauss extension of $v$ from $K$
to $K(X)$.

######  Fact 1.3.7 (Corollary 2.2.2 [EP05]).

Let $(K,v)$ be a valued field with value group $\Gamma$ and residue field $k$.
There exists a unique valuation $w$ on $K(X)$ extending $v$ such that $w(X)=0$
and the residue $x$ of $X$ is transcendental over $k$. This valuation is
defined by the formula

$w(a_{0}+a_{1}X+....+a_{n}X^{n})=\min_{1\leq i\leq n}v(a_{i})$

for $a_{i}\in K$. We have $k_{K(X)}=k(x)$ and $\Gamma_{K(X)}=\Gamma$.

######  Remark 1.3.8.

A lift $\iota:k\to K$ automatically induces a lift

$\iota_{K(X)}:k(x)\to K(X):f(x)\mapsto\iota(f)(X)$

Namely, $\iota_{K(X)}$ agrees with $\iota$ on $K$ and maps $x$ to $X$. Thus,
the image of $\iota_{K(X)}$ equals $k(X)$, once again identifying $k$ with its
image $\iota(k)\subseteq K$ via $\iota$.

######  Lemma 1.3.9.

Let $(K,v,\text{res},\iota)\models\text{VF}_{\text{res},\iota}$ and $a,c\in K$
with $a\in\mathfrak{m}-\\{0\\}$ and $v(c)<\mathbb{Z}v(a)$. Let $w$ be the
Gauss extension of $v$ to $K(X)$ and $\iota_{K(X)}:k(x)\to K(X)$ be the
induced lift. There is a map $\text{res}_{K(X)}:K(X)\to k(x)$ with
$\text{res}_{K(X)}(\frac{c}{1-aX})=0$, such that
$(K(X);w,\text{res}_{K(X)},\iota_{K(X)})$ is a model of
$\text{VF}_{\text{res},\iota}$ extending $(K,v,\text{res},\iota)$.

###### Proof.

By Lemma 1.2.3, it suffices to show that $\frac{c}{1-aX}$ is $k(X)$-linearly
independent over ${\mathcal{O}}_{K(X)}+\langle K\rangle_{k(X)}$. Note that
$\langle K\rangle_{k(X)}=K[X]_{k[X]\backslash\\{0\\}}$, the latter being the
localization of $K[X]$ at $k[X]\backslash\\{0\\}\subseteq K[X]$.

Suppose for a contradiction that

$\frac{c}{1-aX}+\frac{f(X)}{g(X)}\in{\mathcal{O}}_{K(X)}$

for some $f(X)\in K[X]$ and $g(X)\in k[X]\backslash\\{0\\}$. Moreover, choose
$f(X)$ and $g(X)$ as above such that $\deg(f)$ is minimum. Note that $f(X)\neq
0$ because $w(\frac{c}{1-aX})<0$ and hence $\deg(f)$ is well-defined. Write
$f(X)=f_{0}+...+f_{n}X^{n}$ and $g(X)=g_{0}+....+g_{n}X^{n}$ with $f_{i}\in K$
and $g_{i}\in k$. Note that

$w((1-aX)g(X))=w(1-aX)+w(g(X))=0$

It follows that $w(cg(X)+(1-aX)f(X))\geq 0$. By the definition of $w$, this
means that

$(1)\ v(f_{0}+cg_{0})\geq 0,\ (2)\ v(f_{m}+cg_{m}-af_{m-1})\geq 0\mbox{ and
}(3)\ v(af_{n})\geq 0$

for $m=1,...,n$.
Claim 1: We have that $v(f_{0})<0$.

###### Proof.

Suppose that $v(f_{0})\geq 0$. We then have that

$\frac{c}{1-aX}+\frac{f(X)-f_{0}}{g(X)}\in{\mathcal{O}}_{K(X)}$

Write $f(X)-f_{0}=X\cdot\tilde{f}(X)$. If $g_{0}=0$, then $g(X)=X\tilde{g}(X)$
and therefore

$\frac{c}{1-aX}+\frac{\tilde{f}(X)}{\tilde{g}(X)}\in{\mathcal{O}}_{K(X)}$

Since $\text{deg}(\tilde{f})<\text{deg}(f)$, this contradicts our minimality
assumption. Therefore $g_{0}\neq 0$. But then $v(f_{0}+cg_{0})=vc<0$, which
contradicts (1). ∎${}_{\textit{Claim 1}}$

Next, we prove:
Claim 2: For each $m=0,...,n$, there exists $k_{m}\in\mathbb{N}$ such that
$v(f_{m})=v(c)+k_{m}\cdot v(a)$.

###### Proof.

We proceed inductively. For $m=0$: Recall from (1) that $v(f_{0}+cg_{0})\geq
0$. By Claim 1, we have $v(f_{0})<0$. Therefore $g_{0}\neq 0$ and
$v(f_{0})=v(cg_{0})=vc$, which settles the base case. For $m>0$: Recall that
we have

$(2)\ v(f_{m}+cg_{m}-af_{m-1})\geq 0$

By our induction hypothesis, we have

$v(f_{m-1})=v(c)+k_{m-1}\cdot v(a)$

for some $k_{m-1}\in\mathbb{N}$. Since $vc<\mathbb{Z}va$, this implies that
$v(af_{m-1})<0$. If $g_{m}=0$, we get from (2) that

$v(f_{m})=v(af_{m-1})=v(c)+(k_{m-1}+1)v(a)$

and we take $k_{m}=k_{m-1}+1$. Suppose that $g_{m}\neq 0$. Then
$v(cg_{m}-af_{m-1})=v(cg_{m})=v(c)$. By (2), we get that $v(f_{m})=v(c)$ and
we take $k_{m}=0$. ∎${}_{\textit{Claim 2}}$

For $m=n$, we get that $v(f_{n})=v(c)+k_{n}v(a)$, for some
$k_{n}\in\mathbb{N}$. Therefore

$v(af_{n})=v(c)+(k_{n}+1)v(a)<0$

because $v(c)<\mathbb{Z}v(a)$. This contradicts (3). ∎

######  Corollary 1.3.10.

Let $(K,v,\text{res},\iota)$ be an e.c. model of
$\text{VF}_{\text{res},\iota}$. Let $a\in\mathfrak{m}-\\{0\\}$ and $c\in K$ be
such that $v(c)<\mathbb{Z}v(a)$. Then there exists $\beta\in k^{\times}$ such
that

$\text{res}(\frac{c}{1-a\beta})=0$

###### Proof.

Immediate from Lemma 1.3.9. ∎

###  1.4. Non-existence of a model companion of $\text{VF}_{\text{res},\iota}$

####  1.4.1. Generalities on model companions

######  Definition 1.4.2 (Definition 3.2.8 [TZ12]).

Let $T$ be a theory. A theory $T^{*}$ is a model companion of $T$ if the
following conditions are satisfied:

  1. (i)

Every model of $T$ embeds into a model of $T^{*}$.

  2. (ii)

Every model of $T^{*}$ embeds into a model of $T$.

  3. (iii)

$T^{*}$ is model-complete

######  Fact 1.4.3 (Theorem 3.2.9 [TZ12]).

A theory $T$ has, up to equivalence, at most one model companion $T^{*}$.

######  Definition 1.4.4.

  1. (i)

Let $M,N$ be $L$-structures. Suppose that $N\models\phi\Rightarrow
M\models\phi$ for any existential sentence $\phi\in L(M)$. Then we say that
$M$ is existentially closed (or e.c.) in $N$ and write $M\preceq_{\exists}N$.

  2. (ii)

Let $T$ be a theory. A model $M\models T$ is said to be an existentially
closed (or e.c.) model of $T$ if $M\preceq_{\exists}N$, for all $N\models T$.

######  Fact 1.4.5 (Theorem 3.2.14 [TZ12]).

For any theory $T$, the following are equivalent:

  1. (i)

$T$ has a model companion $T^{*}$.

  2. (ii)

The e.c. models of $T$ form an elementary class. Moreover, if $T^{*}$ exists,
then $T^{*}$ is the theory of e.c. models of $T$.

####  1.4.6. Proof of Theorem A

######  Theorem A.

The theory $\text{VF}_{\text{res},\iota}$ does not admit a model companion.

###### Proof.

Assume otherwise and let $T$ be the model companion of
$\text{VF}_{\text{res},\iota}$. By Fact 1.4.5, the theory $T$ is precisely the
theory of e.c. models of $\text{VF}_{\text{res},\iota}$. Let
$(K_{0},v_{0},\text{res}_{0},\iota_{0})\models T$ be $\aleph_{1}$-saturated.
By Corollary 1.3.5 and $\aleph_{1}$-saturation, there is
$a\in\mathfrak{m}_{0}-\\{0\\}$ such that $\text{res}_{0}(a^{-m})=0$ for $m>0$.
Let

$(K,v,\text{res},\iota):=(K_{0},v_{0},\text{res}_{0},\iota_{0})^{U}$

where $U$ is a non-principal ultrafilter on $\mathbb{N}$. By Łoś’ Theorem, we
will have that
$(K_{0},v_{0},\text{res}_{0},\iota_{0})\preceq(K,v,\text{res},\iota)$. In
particular, we get that $(K,v,\text{res},\iota)\models T$ and therefore
$(K,v,\text{res},\iota)$ is an e.c. model of $\text{VF}_{\text{res},\iota}$.

Set $a^{*}:=\text{ulim }a^{-n}$. Since $U$ is non-principal, we get that
$va^{*}<\mathbb{Z}va$. By Corollary 1.3.10, there is $\beta\in k-\\{0\\}$ such
that $\text{res}(\frac{a^{*}}{1-a\beta})=0$. By Łoś’ Theorem, we get that

$\\{n\in\mathbb{N}:K_{0}\models\exists y\in
k^{\times}(\text{res}_{0}(\frac{a^{-n}}{1-ay})=0)\\}\in U$

In particular, there exists $n\in\mathbb{N}$ and
$\beta_{0}\in\iota(k_{0})-\\{0\\}$ such that
$\text{res}(\frac{a^{-n}}{1-a\beta_{0}})=0$. Note that

$\frac{a^{-n}}{1-a\beta_{0}}\equiv\beta_{0}^{n}+a^{-1}\beta_{0}^{n-1}+...+a^{-n}\mod\mathfrak{m}$

Since $\text{res}:K\to k$ is $k$-linear and $\text{res}(\mathfrak{m})=\\{0\\}$
and $\text{res}(a^{-m})=0$ for all $m\in\mathbb{N}$, we compute that

$\text{res}(\frac{a^{-n}}{1-a\beta_{0}})=\text{res}(\beta_{0}^{n}+a^{-1}\beta_{0}^{n-1}+...+a^{-n})=\sum_{m=0}^{n}\beta_{i}^{m-i}\text{res}(a^{-m})=\beta_{0}^{n}$

This forces $\beta_{0}=0$, which is a contradiction. It follows that
$\text{VF}_{\text{res},\iota}$ does not admit a model companion. ∎

##  2\. Undecidability of $k(\\!(t^{\Gamma})\\!)$ with a total residue map

Let $k(\\!(t^{\Gamma})\\!)$ be the Hahn field with residue field $k$ and value
group $\Gamma$. Recall that an element $f\in k(\\!(t^{\Gamma})\\!)$ is of the
form

$f=\sum_{q\in\Gamma}c_{q}t^{q}$

where ${\mathop{\operatorname{\rm supp}\,}}(f)=\\{q\in\Gamma:c_{q}\neq 0\\}$
is well-ordered. Throughout, we fix some element $1\in\Gamma^{>0}$, thereby
identifying a copy of $\mathbb{Z}$ inside $\Gamma$. We write $t$ for $t^{1}$.

###  2.1. Definability in $k(\\!(t^{\Gamma})\\!)$ in $L_{\text{res}}$

######  Lemma 2.1.1.

Let $k$ be any field and $\Gamma$ be any ordered abelian group. The subfield
$k\subseteq k(\\!(t^{\Gamma})\\!)$ is $\emptyset$-definable in
$L_{\text{res}}$. In particular, the lift $\iota:k\to k(\\!(t^{\Gamma})\\!)$
is $\emptyset$-definable in $L_{\text{res}}$.

###### Proof.

We claim that

$k=\\{x\in k(\\!(t^{\Gamma})\\!):\forall y(\text{res}(x\cdot
y)=\text{res}(x)\cdot\text{res}(y))\\}$

The inclusion "$\subseteq$" is clear. For "$\supseteq$", suppose that $x\notin
k$ and write $x=\alpha+x^{\prime}$ with $\alpha\in k$,
$\text{res}(x^{\prime})=0$ and $x^{\prime}\neq 0$. Note that
$v(x^{\prime})\neq 0$. For $q=v(x^{\prime})$, we compute that

$\text{res}(x\cdot
t^{-q})=\alpha\cdot\text{res}(t^{-q})+\text{res}(x^{\prime}\cdot
t^{-q})=\text{res}(x^{\prime}\cdot t^{-q})\neq 0$

On the other hand, we have $\text{res}(x)\cdot\text{res}(t^{-q})=0$ and hence

$\text{res}(x\cdot t^{-q})\neq\text{res}(x)\cdot\text{res}(t^{-q})$

Finally, for $\iota$ simply note that $\iota(\alpha)=a$ if and only if
$a\in\iota(k)$ and $\text{res}(a)=\alpha$. ∎

######  Definition 2.1.2.

Given

$a=\sum_{q\in A}c_{q}t^{q}\in k(\\!(t^{\Gamma})\\!)$

we define the polynomial $p_{a}(X)\in k[X]$ given by

$p_{a}(X)=\sum_{n\in\mathbb{N}}c_{-n}X^{n}$

Note that $p_{a}(X)$ is indeed a polynomial because
${\mathop{\operatorname{\rm supp}\,}}(a)\cap\mathbb{Z}^{\leq 0}$ is finite.

######  Lemma 2.1.3.

For any $a\in k(\\!(t^{\Gamma})\\!)$ and $y\in k$, we have

$\text{res}(\frac{a}{1-ty})=p_{a}(y)$

###### Proof.

Write $a=\sum_{q\in\Gamma}c_{q}t^{q}\in k(\\!(t^{\Gamma})\\!)$. For each
$q_{0}\in\Gamma$, note that

$\text{res}(t^{q_{0}}\cdot\sum_{q\in A}c_{q}t^{q})=c_{-q_{0}}$

We now have

$\frac{a}{1-ty}=(1+ty+...+t^{n}y^{n}+...)\cdot\sum_{q\in\Gamma}c_{q}t^{q}\equiv\sum_{i=1}^{n}t^{i}y^{i}\cdot\sum_{q\in\Gamma}c_{q}t^{q}\mod\mathfrak{m}$

where $n$ is maximum such that $-n\in\text{supp}(a)$. By $k$-linearity of res
and since $\text{res}(\mathfrak{m})=\\{0\\}$, we get that

$\text{res}(\frac{a}{1-ty})=\sum_{i=1}^{n}\text{res}(t^{i}\cdot\sum_{q\in\Gamma}c_{q}t^{q})y^{i}=\sum_{i=1}^{n}c_{-i}y^{i}=p_{a}(y)$

as needed. ∎

###  2.2. Infinite residue field

Let $k$ be an infinite field.

####  2.2.1. Undecidability of $k(\\!(t^{\Gamma})\\!)$ in $L_{\text{res},t}$

We isolate the following elementary fact from algebra to pinpoint exactly
where our proof fails when $k$ is finite:

######  Lemma 2.2.2.

Let $k$ be any infinite field and $f(X)\in k[X]$. Then $f(X)\equiv 0$ if and
only if $f(k)=\\{0\\}$.

###### Proof.

Any non-zero polynomial over any field has finitely many roots. ∎

######  Fact 2.2.3 (Denef).

Let $R=k[t]$, where $k$ is any field. Then Hilbert’s tenth problem over $R$
with coefficients in $\mathbb{Z}[t]$ is unsolvable.

###### Proof.

See [Den79] and [Den78]. ∎

######  Theorem B.

Let $k$ be an infinite field and $\Gamma$ be any non-trivial ordered abelian
group. Then $(k(\\!(t^{\Gamma})\\!),\text{res})$ is
$\exists\forall$-undecidable in $L_{\text{res},t}$. The same is true for the
Puiseux series field $k\\{\\!\\{t\\}\\!\\}$.

###### Proof.

Let
$f_{1}(X_{1},...,X_{m},T),...,f_{n}(X_{1},...,X_{m},T)\in\mathbb{Z}[X_{1},...,X_{m},T]$,
where $n,m\in\mathbb{N}$. The system

$f_{1}(X_{1},...,X_{m},T)=....=f_{n}(X_{1},...,X_{m},T)=0$

has a solution in $k[T]$ if and only if there exist $a_{1},...,a_{m}\in
k(\\!(t^{\Gamma})\\!)$ such that

$f_{1}(p_{a_{1}}(t^{-1}),...,p_{a_{m}}(t^{-1}),t^{-1})=....=f_{n}(p_{a_{1}}(t^{-1}),...,p_{a_{m}}(t^{-1}),t^{-1})=0$

By Lemma 2.2.2, this is also equivalent to the existence of
$a_{1},...,a_{m}\in k(\\!(t^{\Gamma})\\!)$ such that

$f_{1}(p_{a_{1}}(y),...,p_{a_{m}}(y),y)=....=f_{n}(p_{a_{1}}(y),...,p_{a_{m}}(y),y)=0$

for all $y\in k$. This is expressible in $L_{\text{res},t}$ by Lemma 2.1.3 and
Lemma 2.1.1 and we conclude from Fact 2.2.3. The proof works verbatim for the
Puiseux series field. ∎

In §7.2.21 [Kar22], it is also shown that $k[t]\subseteq k(\\!(t)\\!)$ is
definable in $L_{\text{res},t}$.

####  2.2.4. A natural example from complex analysis

In complex analysis, one defines the residue of a complex function
$f\in\mathbb{C}(\\!(t)\\!)$ at an isolated singularity $a\in\mathbb{C}$,
denoted by $\text{Res}(f,a)$ or $\text{Res}_{a}(f)$. Numerically, if
$f=\sum_{i=-n}^{\infty}c_{i}(t-a)^{i}$, we have that $\text{Res}(f,a)=c_{-1}$.

######  Corollary 2.2.5.

We have that $\mathbb{C}(\\!(t)\\!)$ is $\exists\forall$-undecidable in
$L_{\text{Res}_{0},t}$. The same is true for the Puiseux series field
${\mathbb{C}}\\{\\!\\{t\\}\\!\\}$.

###### Proof.

Note that $\text{Res}_{0}(a)=\text{res}(t\cdot a)$ and conclude from Theorem
B. ∎

###  2.3. Eliminating $t$

We now give a different proof of the undecidability of
$(k(\\!(t^{\Gamma})\\!),+,\cdot,\text{res})$, where $k$ is an infinite field
and $\Gamma$ is an ordered abelian group of rank $1$. The proof discussed here
does not require a parameter for $t$ and even shows that
$(\mathbb{N},+,\cdot)$ is interpretable without parameters.

####  2.3.1. Interpreting the weak monadic second-order theory of $k$

Weak monadic second-order logic is the fragment of second-order logic where
second-order quantification is restricted to quantification over finite
subsets.

######  Lemma 2.3.2.

Let $\Gamma$ be an ordered abelian group of rank $1$. Let $a\in
k(\\!(t^{\Gamma})\\!)$ and $b\in\mathfrak{m}$. Then the set

$S_{a,b}=\\{\beta\in k:\text{res}(\frac{a}{1-b\beta})=0\\}$

is either finite or equal to $k$.

###### Proof.

Since $\Gamma$ is of rank $1$, there exists $n\in\mathbb{N}$ such that
$ab^{n}\in\mathfrak{m}$. We then have that

$\frac{a}{1-b\beta}\equiv a(1+b\beta+...+b^{n-1}\beta^{n-1})\mod\mathfrak{m}$

Since res is $k$-linear and $\text{res}(\mathfrak{m})=\\{0\\}$, we get that

$\text{res}(\frac{a}{1-b\beta})=0\iff p_{a,b}(\beta)=0$

where

$p_{a,b}(X)=\sum_{i=0}^{n-1}\text{res}(ab^{i})\cdot X^{i}\in k[X]$

If $p_{a,b}(X)\equiv 0$, then $S_{a,b}=k$ and otherwise $S_{a,b}$ is finite. ∎

######  Lemma 2.3.3.

Let $\Gamma$ be an ordered abelian group of rank $1$. Then the weak monadic
second-order theory of $(k,+,\cdot)$ is $\emptyset$-interpretable in
$k(\\!(t^{\Gamma})\\!)$ in $L_{\text{res}}$. The same is true for the Puiseux
series field $k\\{\\!\\{t\\}\\!\\}$.

###### Proof.

By Lemma 2.1.1, we have that the first-order theory $(k,+,\cdot)$ is
$\emptyset$-interpretable in $k(\\!(t^{\Gamma})\\!)$ in $L_{\text{res}}$. By
Lemma 2.3.2, we have a uniformly $\emptyset$-definable family

$\\{S_{a,b}:a\in k(\\!(t^{\Gamma})\\!)\mbox{ and }b\in\mathfrak{m}\\}$

of finite subsets of $k$ together with $k$ itself. We claim that every finite
$S\subseteq k$ arises as $S_{a,b}$, for some $a\in k(\\!(t^{\Gamma})\\!)\mbox{
and }b\in\mathfrak{m}$. Given a finite $S\subseteq k$, we set

$a=\prod_{s\in S}(t^{-1}-s)\mbox{ and }b=t$

By Lemma 2.1.3, we get indeed that

$S_{a,b}=\\{y:p_{a}(y)=0\\}=S$

We thus encode the weak monadic second-order theory of $(k,+,\cdot)$. The
proof works verbatim for the Puiseux series field. ∎

######  Lemma 2.3.4.

Let $k$ be an infinite field. Then the weak monadic second-order theory of
$(k,+,\cdot)$ interprets $(\mathbb{N},+,\cdot)$. In particular, it is
undecidable.

###### Proof.

See §1 [Che82]. ∎

######  Theorem C.

Let $k$ be an infinite field and $\Gamma$ be an ordered abelian group of rank
$1$. Then $(k(\\!(t^{\Gamma})\\!),\text{res})$ interprets
$(\mathbb{N},+,\cdot)$. In particular, $k(\\!(t^{\Gamma})\\!)$ is undecidable
in $L_{\text{res}}$. The same is true for the Puiseux series field
$k\\{\\!\\{t\\}\\!\\}$.

###### Proof.

From Lemma 2.3.3 and Lemma 2.3.4. ∎

######  Remark 2.3.5.

In case $k$ is an infinite perfect field of positive characteristic, the
undecidability of $(k(\\!(t)\\!),+,\cdot,\text{res})$ also follows from Lemma
2.1.1 and §2 [Che82] which shows that $k(\\!(t)\\!)$ is undecidable with a
predicate for $k\subseteq k(\\!(t)\\!)$.

### Acknowledgements

I wish to thank E. Hrushovski for suggesting the problem and for an
instructive discussion on the elimination of the parameter. I also thank J.
Koenigsmann for careful readings of earlier drafts.

## References

  * [AK66] James Ax and Simon Kochen.  Diophantine problems over local fields: III. Decidable fields.  Annals of Mathematics , Second Series, Vol. 83, No. 3, pp. 437-456, 1966.
  * [BDL79] Joseph Becker, Jan Denef, and Leonard Lipshitz.  Further remarks on the elementary theory of formal power series rings.  Model theory of algebra and arithmetic, Proceedings Karpacz, Poland, Lecture Notes in Mathematics, Vol. 834. Berlin, Heidelberg, New York: Springer 1979, 1979.
  * [Che82] Gregory Cherlin.  Undecidability of rational function fields in nonzero characteristic.  Logic Colloq., no. 82, North-Holland, Amsterdam., 1982.
  * [Den78] Jan Denef.  The Diophantine problem for polynomial rings of positive characteristic.  Transactions of the American Mathematical Society, 1978.
  * [Den79] Jan Denef.  The Diophantine problem for polynomial rings and rings of rational functions.  Logic Colloquium, North-Holland Publishing Company, 1979.
  * [EP05] Antonio J. Engler and Alexander Prestel.  Valued Fields.  Springer, Berlin, Heidelberg, 2005.
  * [Ers65] Ju.L. Ershov.  On elementary theories of local fields.  Algebra i Logika 4, No. 2, 5-30, 1965.
  * [HK09] Ehud Hrushovski and David Kazhdan.  Motivic Poisson summation.  Mosc. Math. J., Volume 9, Number 3, Pages 569-623, 2009.
  * [Kar22] Konstantinos Kartas.  Contributions to the model theory of henselian fields.  PhD thesis, University of Oxford, 2022.
  * [TZ12] Katrin Tent and Martin Ziegler.  A Course in Model Theory.  Lecture Notes in Logic. Cambridge University Press, 2012.

Mathematical Institute, Woodstock Road, Oxford OX2 6GG.

E-mail address<EMAIL_ADDRESS>


# Masked Multi-Query Slot Attention for Unsupervised Object Discovery
††thanks: This research was supported by the National Science and Engineering
Research Council of Canada (NSERC), via its Discovery Grant program and MITACS
through the Globalink program. The authors acknowledge the support provided in
part by Calcul Quebéc and the Digital Research Alliance of Canada.

Rishav Pramanik  Jadavpur University
Kolkata, India
<EMAIL_ADDRESS>José-Fabian Villa-Vásquez  ÉTS Montréal
Montréal, Canada
<EMAIL_ADDRESS>Marco Pedersoli  ÉTS Montréal
Montréal, Canada
<EMAIL_ADDRESS>
###### Abstract

Unsupervised object discovery is becoming an essential line of research for
tackling recognition problems that require decomposing an image into entities,
such as semantic segmentation and object detection. Recently, object-centric
methods that leverage self-supervision have gained popularity, due to their
simplicity and adaptability to different settings and conditions. However,
those methods do not exploit effective techniques already employed in modern
self-supervised approaches. In this work, we consider an object-centric
approach in which DINO ViT features are reconstructed via a set of queried
representations called slots. Based on that, we propose a masking scheme on
input features that selectively disregards the background regions, inducing
our model to focus more on salient objects during the reconstruction phase.
Moreover, we extend the slot attention to a multi-query approach, allowing the
model to learn multiple sets of slots, producing more stable masks. During
training, these multiple sets of slots are learned independently while, at
test time, these sets are merged through Hungarian matching to obtain the
final slots. Our experimental results and ablations on the PASCAL-VOC 2012
dataset show the importance of each component and highlight how their
combination consistently improves object localization. Our source code is
available at: github.com/rishavpramanik/maskedmultiqueryslot

###### Index Terms:

Object discovery, Object localization, Multi-query attention, Semantic
segmentation, Unsupervised learning

##  I Introduction

Modern-day computer vision technologies demand robust object localization
methods for contemporary AI systems to understand and comprehend the ever-
growing visual data. As our world transitions to become more dependent on AI-
based systems, we observe that tasks like autonomous driving [1], drone
surveillance [2], and traffic monitoring [3] rely significantly on the
generalization ability of object discovery tasks like object detection and
segmentation. Current state-of-the-art approaches for object localization
tasks heavily depend on meticulously labelled high-quality training data [4,
5]. Supervised approaches specialize in discovering a small subset of classes
present in the physical world, thereby adversely impacting generalization. As
an evolving subfield of representation learning, object-centric representation
learning considers a visual scene to encompass multiple objects, potentially
offering greater robustness against out-of-distribution data [6]. In this
work, we consider unsupervised object discovery as object-centric
representation learning.

Conventional approaches focusing on unsupervised localization of objects
explore saliency [7] or similarity within patches [8] of an image. In
contrast, other studies focus on utilizing data from an entire image
collection by exploiting inter-image similarities via ranking [9], component
analysis [10], and probabilistic matching [11], but these methods hardly scale
to large datasets. The latest methods use pre-trained self-supervised features
[12, 13] to localize objects. Generally, these methods [14, 15] assume the
presence of a single object that covers the majority of the image. However,
such assumptions limit the application areas of these methods. The literature
also includes works that use spectral clustering [16, 17]; these methods
typically necessitate an extra segmentation network to obtain the segmentation
masks.

In DINOSAUR [18], the authors propose to use an object-centric learning
approach through slot attention [19]. The authors use self-supervised features
from DINO to reconstruct features with slot groupings. Although the authors
highlight the usefulness of DINO features and slot attention groupings in
decomposing a real-life visual scene into a collection of objects, the
proposed approach does not fully exploit the potential of the DINO features
and slot groupings. In this paper, we investigate the impact of masked
modelling on DINO features in contributing to generalization towards more
complex real-life images by leveraging object-centric representations. Instead
of relying on single object groupings, we introduce additional inductive
biases by producing multiple object groupings against a single write head to
improve the stability and robustness of the framework. During training, we
feed non-overlapping patches to extract patch tokens from the last attention
layer of a vision transformer (ViT) pre-trained with DINO [12]. We then
selectively mask with zeros, $m\%$ of the patches with the highest means.
These patches mostly belong to the background; thus, we leave the salient
regions of the image unmasked. This allows the model to learn complex semantic
information about the object. Next, we propose an extension of slot attention
[19]. During training, we consider the slots as queries and independently
train multiple sets of slots against a single key-value pair. Then, we
randomly select a single head of slot representations to be decoded. This
strategy helps to produce independent representations at test time. During
inference, we perform a fusion of the multiple heads by maximizing the cosine
similarity among the slots to obtain the best matching amongst the learned
representations. Finally, we obtain the aligned representations and compute an
average across all the heads to produce the final set of output slots.

Our main contributions are as follows: (1) We introduce a strategy for
selective masking of DINO features during training, which helps to better
discriminate between different objects. (2) We propose to extend slot
attention with multi-query attention along with different combinations
training and inference techniques which help to stabilize the framework and
enhance generalization. (3) We demonstrate the usefulness of each component of
our approach for unsupervised object discovery, through different performance
metrics.

##  II Related Work

###  II-A Unsupervised Object Discovery

Unsupervised object discovery aims to identify and group similar objects,
subsequently localizing them within an image. Traditionally in literature, the
initial task had been to find binary masks for object identification and
grouping [20, 21], while the subsequent task had involved outlining bounding
boxes around these objects [22, 23].

It is not until very recently, that these distinct tasks have been tackled
simultaneously by leveraging features from large-scale pre-trained methods. In
this domain there have been some attempts that employ CNN activations for
object discovery. [24, 25]. LOST [14] was one of the early works which
leveraged self-supervised trasnformer features for this task. The authors used
a seed expansion strategy based on a graph constructed by using feature
similarity extracted from self-supervised ViTs. Further extending this line of
research, the work reported in Tokencut [15] and Deep spectral methods [17]
use normalized graph-cuts on this graph. These methodologies operate under the
assumption that only one object is present in the image, modelling it as a
bipartition problem in the graph, separating the background and foreground.
Although these methods typically do not consider training due to their
simplistic nature, FOUND [26] uses a $1\times 1$ convolution filter to refine
coarse background masks to a more refined mask. DINOSAUR [18] is more closely
related to our work and performs representation learning by reconstructing the
self-supervised features extracted from the ViTs. Our work offers substantial
improvement in performance and stability over DINOSAUR through selective
masking strategies and multi-query attention.

###  II-B Self-Supervised learning

The rapid advancement of self-supervised visual representation learning has
opened ways to cut dependence on large-scale labelled datasets. Initially,
such pretext training tasks were based on jigsaw puzzles, colorization and
inpainting [27, 28, 29]. Recently, contrastive learning approaches which
strongly rely on data augmentations are getting popular. These approaches
require one or more image views, which are contrasted to learn feature
representations [30, 31, 32]. Clustering-based approaches use discriminative
training objectives between groups of images to learn feature representations
[33, 34]. In these approaches, a computed pseudo label acts as the cluster.
All these techniques focus on downstream tasks such as image classification,
emphasizing the extraction of global features. Self-supervised methods like
DINO [12] enable the extraction of dense features for image patches,
containing precise information about object presence in a patch.

###  II-C Masked Autoencoders

Masked image modelling learns visual representations from corrupted or
incomplete images, often deliberately performed. One of the early works [35]
that spearheaded research in this domain considers masking as noise for
denoising autoencoders. Recently, frameworks like [36, 37] proposed using ViTs
for masked language modelling. Masked Autoencoders (MAE) [13] is one of the
recent advancements in self-supervised learning. MAEs randomly mask ViT
patches at a relatively higher ratio than their language counterparts. To the
best of our knowledge, there is no previous work which uses masked image
modelling for object discovery without labels.

###  II-D Multi-Query Attention

Neural attention is one of the most effective strategies in modern
representation learning. This process involves comparing queries with keys to
derive weights for the output, generally calculated as a weighted sum of value
vectors. Multi-head attention introduced with the transformer model [38]
splits the keys, queries and values into multiple heads to derive the weights
for the attention layer outputs. This idea was improved in further work by
Shazeer [39] which proposed the use of a single key and value pair for faster
inference and reduced memory footprint. We exploit the idea of having multiple
heads with a single key and value pair to improve on Slot Attention [19].

##  III Methodology

Figure 1: Overview of our proposed architecture. The top part describes the
training pipeline that highlights two of our main contributions: Patch Masking
Strategy and Multi-Query Attention. The bottom part illustrates the inference
phase, which unlike the training phase, does not include the patch masking
module and includes an additional Fusion module to perform Slot Alignment via
Hungarian Matching to produce the output slots.

In this section, we discuss our proposed method in detail. We start by
introducing the masking strategy and the multi-query slot attention approach.
Then, in the subsequent sub-sections, we discuss the combination of the
multiple queries. We also discuss about how we build the entire end-to-end
framework for unsupervised object discovery. We present an overview of our
method in Fig. 1.

###  III-A Masking

We devise our masking strategy with inspiration from the MAEs literature [13].
Let us consider an image $x$ with spatial resolution $H\times W$ pixels
reshaped into $N=\frac{H\cdot W}{P^{2}}$ non-overlapping patches and with $P$
the patch size in pixels. Each patch token extracted from ViT-S/16 pre-trained
with DINO is represented by a vector $p\in\mathbb{R}^{D_{\text{feats}}}$, with
dimensionality $D_{\text{feats}}$. We compute the mean
($\frac{1}{D_{\text{feats}}}\sum_{i=1}^{D_{\text{feats}}}p_{i}$) for each
patch token to obtain a rough estimate of the saliency of the patch w.r.t. to
the entire image. We then sort the patches in increasing order and filter out
the top $m\%$ of the patches with the highest means. We mask these patches by
replacing the patch tokens with a zero vector $\vec{0}$. Implementation-wise,
we use the $arg\,sort$ operator from standard libraries to obtain the indices
in increasing order. We then filter out the last $m\%$ of the indices to mask
them. Under this framework, we assume the objects usually have a more complex
semantic structure when compared to their background counterparts. Thus, we
leave the majority of the objects unmasked. This strategy permits the model to
learn invariant object-centric representations, allowing us to generate
generalizable semantic masks. As an added advantage of primarily masking the
background, our method discriminates well between different sets of objects.
We present a few examples of our masking process in Fig. 2.

Figure 2: Masking visualization. These figures show the original image (first
row) and the corresponding masked version used during training. As expected,
masking removes a large portion of the background leaving only parts of the
object of interest and forcing the model to reconstruct the missing parts.

###  III-B Multi-Query Slot Attention

Our multi-query slot attention approach is based on slot attention [19]. Each
slot $s$ in a slot attention module is a representation of dimension
$(D_{\text{slots}})$ that serves to bind an object to different categories
through an iterative dot-product attention process. An encoder network $(E)$
encodes a given image into features $(F)$ based on which slot attention mimics
a competition process among $K$ slots (queries) initialized randomly using:

$\displaystyle slots\sim\mathcal{N}(\mu,diag(\sigma))\in\mathbb{R}^{K\times
D_{\text{slots}}}$ (1)

Here $\mu$ and $\sigma$ are the learnable mean and variance of a Gaussian. The
mean and variance are shared amongst the slots, i.e., we use the same mean and
variance to initialize all the slots. In our formulation, we define $h$ heads
of slots and we initialize these sets of slots $(s^{j}:j\in(1,2...h))$ with
mean and variance $\mu^{j}$ and $\sigma^{j}$, respectively. We then use
learnable linear projections $(K,V,Q^{j})$ for attention. To learn the
projections on keys $(k)$, values $(v)$ and queries (slots $s^{j}$) on inputs
$x$ we use:

$\displaystyle k=K(x)\;,\;v=V(x)\;,\;s^{j}=Q^{j}(s^{j})$ (2)

Our multi-query attention module uses only a single key-value pair; therefore,
we apply a single set of transformations for all heads, as opposed to the
queries for which we use different transformations for each head. We follow
the strategy of Multi-Query Attention [39], which proposes using only one
write head. We also consider that slot attention is an iterative process and
hence, in each iteration, the projection is learned using the same
transformation on the slots.

We compute the dot product attention for each head $j$ using:

$\displaystyle
A^{j}=\frac{e^{\lambda^{j}}}{\sum_{\forall\lambda^{j}}e^{\lambda^{j}}}\;:\;\lambda^{j}=(\frac{1}{\sqrt{D_{\text{slots}}}})k\cdot(s^{j})^{T}\in\mathbb{R}^{K\times
D_{\text{slots}}}$ (3) $\displaystyle\upsilon^{j}=(\mathcal{W}^{j})^{T}\cdot
v\;:\;\mathcal{W}^{j}=\frac{A^{j}+\epsilon}{\sum_{\forall
A^{j}}(A^{j}+\epsilon)}$ (4)

In our approach, we evaluate independent attention weights for each head.
These weights help us focus on relevant regions in the image against the set
of queries (slots) that we initialize with mean and variance for a particular
head. By introducing this mechanism of having independent heads, we average
out the negative impact of seed selection over different regions, which we
observe as a problem in various previous works [14, 15, 18]. This idea of
having different slot proposals improves the stability of the entire
framework. The slot representations in each head are learned through an
iterative process with $t\in(1,2...T)$ iterations. We update the slots
$s_{t}^{j}$ at the $t^{th}$ iteration using a Gated Recurrent Unit (GRU) and
multi-layer perceptron (MLP) using:

$\displaystyle
s_{t}^{j}\mathrel{+}=\text{MLP}^{j}(s_{t}^{j}):s^{j}_{t}=\text{GRU}^{j}(\text{state}=s_{t-1}^{j},\text{input}=\upsilon^{j})$
(5)

###  III-C Combination of Multiple Queries

The multi-query attention process demands a mechanism to aggregate the slot
representations across various heads. In this regard, we consider a crucial
property of Slot Attention: it maintains permutation equivariance concerning
the order of the slots [19]. This property implies that rearranging the slot
order after initialization equates to rearranging the output order of the
module. Another key factor that we take into account while combining the slots
is the computational cost, as well as, the time required for both training and
inference.

####  III-C1 Training

During the training phase, we prioritize the ability of each head to offer
independent slot representations. To accomplish this, we ensure that all
parameters related to a particular head—such as the means, variance, MLP
projections, and GRU—are trained independently. During batch training at
runtime, we randomly select a head to be processed by the decoder. This random
selection enables each parameter associated with each head to learn
distinctive features while maintaining a low computational cost.

Figure 3: Segmentation masks created with different slot attention
configurations. From left to right: Original image, normal Slot Attention,
Slot Attention with our masking approach, Slot Attention with masking and
Multi-Queries (Ours). All configurations involve a ViT-S/16 pre-trained with
DINO as the encoder backbone.

####  III-C2 Inference

Since we know, that changing the slot order is sufficient to align the two
given slots, let us consider a set of slot representations $(s^{j})$ for head
$j\in(1,2...h)$. We randomly select a reference head $(s^{r})$ within the $h$
heads, based on which we align the remaining sets of slots. We consider a
single slot representation from $s^{j}$ as $c^{j}_{i}$ for the slot
$i\in(1,2...K)$. Then, to align the slot representations, we obtain the
similarity matrix using cosine similarity according to:

$\displaystyle S_{jr}=\frac{c^{j}_{a}\cdot
c^{r}_{b}}{||c^{j}_{a}||_{2}||c^{r}_{b}||_{2}}\;\forall\;a,b$ (6)

We match the respective slots from head $j$ to the reference head $r$ using
Hungarian Matching [40]. We maximize the cosine similarity to obtain the
matching. To obtain the final set of slot representations $(s^{f})$ that will
be decoded we use:

$\displaystyle s^{f}=\frac{1}{h}(s^{r}+\sum_{\forall
s^{j}}\text{aligned}(s^{j}))\;:\;j\neq r$ (7)

i.e. the averaged representations corresponding to the aligned slots. In this
work, we also compare a few other combination criteria, which are discussed in
the Results section.

###  III-D Architecture

####  III-D1 Encoding

The encoder extracts feature representations from the ViT-S/16 model trained
in a self-supervised fashion using DINO [12]. It learns three linear
projections—Keys, Queries, and Values—based on non-overlapping patches from
the input image. Of the multiple self-attention layers, we extract the patch
tokens from the last self-attention layer, typically composed of many heads.
In this paper, we concatenate all keys from these heads. Although we refrain
from fine-tuning the ViT in this paper, our efforts to do so were
computationally impractical.

####  III-D2 Decoding

We use a decoder to transform each slot representation into patch tokens. We
use the spatial broadcast decoder [41], a common decoding strategy [19, 18]
for the latent vectors in variational autoencoders. Initially, we broadcast a
given slot into the number of patches. We then add additive positional
encodings to the slot representations similar to the positional encodings in
ViT. We further process these features through a 3-layer MLP with a hidden
depth of $1024$ to obtain the patch tokens for each slot. We follow a process
similar to previous works [19, 42] to normalize the patch tokens across the
slots using the $softmax$ operation. Finally, we use these weights to produce
the reconstructed patch tokens as a weighted sum of all the decoded slot
representations. We use a mean squared error ($\mathcal{L}_{2}$) loss to
optimize our network.

##  IV Results

In this section, we present our experimental results and their corresponding
analysis. We begin by discussing the importance of our masking strategy
compared to other methods. We provide results related to different multi-head
combination strategies. Following that, we conduct an ablation study to
explore the impact of various aspects of our approach. In the latter part of
this section, we present the associated computational cost. Finally, we
compare our method to the current state-of-the-art unsupervised object
discovery methods to conclude our results. All our experiments are conducted
on the PASCAL-VOC 2012 dataset [43].

###  IV-A Preliminaries

We enlist some important implementation details and the metrics we use to
evaluate our method as follows:

####  IV-A1 Implementation Details

We train the masked multi-query slot attention using the Adam optimizer. We
use a learning rate of $4\times 10^{-4}$, and we set $2\%$ of the total
optimization steps to linearly warm up the optimization process. We then use
an exponential decay to allow our method to converge. We train for $500$
epochs on $4\times$ $16$ GB NVIDIA-V100 GPUs with a local batch size of $4$.
For reporting each result, we run each method $3$ times and report the mean
and standard deviation. During training for the reconstruction, the
probability of masking a patch is $m=70\%$, which is determined empirically.

####  IV-A2 Evaluation Metrics

To fairly assess our experimental findings, we report Correct Localization
(CorLoc), mean intersection over union (mIoU), and mean best overlap (mBo). In
the CorLoc metric, we gauge the percentage of correct bounding boxes,
selecting the predicted boxes with IoU greater than 0.5 with any of the ground
truth boxes. We calculate mIoU and mBo by comparing the class-agnostic
segmentation masks to the ground truth masks. For this task, we perform
Hungarian matching by maximizing the IoUs to obtain the matching. The mIoU
measures the IoU per class and averages it over all the classes per image for
the entire dataset. The mBo is the average IoU over the assigned mask pairs.

###  IV-B Baselines

In Table I and Fig. 3, we compare our method against two other baselines. For
each method, we use ViT-S/16 pre-trained with DINO as the feature extractor.
The masking strategy we use for comparison in Table I and Fig. 3 is the
background masking. We show that our masking produces substantially better
results both quantitatively and qualitatively. Through masking background
(Fig. 2), we ensure our model learns to group the objects within an image in
the absence of background noise. Finally, by introducing the multi-query
approach, we further boost performance.

TABLE I: Comparative results with different masking and multi-query
configurations. All configurations use a ViT-S/16 pre-trained with DINO as the
backbone network

Masking Multi-Query CorLoc mIoui mBoi ✘ ✘ 50.38 $\pm$ 0.9 32.82 $\pm$ 0.1
32.92 $\pm$ 0.1 ✓ ✘ 64.48 $\pm$ 0.4 36.35 $\pm$ 1.3 37.34 $\pm$ 0.4 ✓ ✓ 68.99
$\pm$ 0.7 39.42 $\pm$ 0.3 39.74 $\pm$ 0.3

###  IV-C Masking

We also compare our masking approach against the commonly used [13] random
masking strategy. We randomly select the patch indices in the runtime and
replace the patch tokens with zeros. In Table II, we observe that background
masking produces better and more stable results for all three metrics used for
comparison here. The improvement can be explained noting that, unlike
background masking, random masking masks patch features for both the object
and the background, thus not allowing the model to learn semantic information
about a specific object. While background masking is a bit more expensive than
random masking in the training phase, the inference time remains the same for
both.

TABLE II: Results with different masking strategies. ✓ indicates if multiple
heads was used during both training and evaluation

Strategy Multiple Heads CorLoc mIoui mBoi No Masking ✘ 50.38 $\pm$ 0.9 32.82
$\pm$ 0.1 32.92 $\pm$ 0.1 ✓ 51.22 $\pm$ 0.8 33.06 $\pm$ 0.1 30.96 $\pm$ 0.2
Random ✘ 67.35 $\pm$ 6.2 34.60 $\pm$ 2.5 34.68 $\pm$ 2.4 ✓ 66.60 $\pm$ 1.7
32.64 $\pm$ 0.1 32.79 $\pm$ 0.1 Background ✘ 64.48 $\pm$ 1.4 36.35 $\pm$ 0.4
37.34 $\pm$ 0.4 ✓ 68.99 $\pm$ 0.7 39.42 $\pm$ 0.3 39.74 $\pm$ 0.3

Figure 4: Segmentation masks of the different heads for the multi-query
approach. The first column on the left is the original Image. The next 8
images show the different segmentations for each head and the rightmost column
shows the combined results with Hungarian matching.

###  IV-D Multi Query Attention and Combination

We show the visualizations in Fig. 4 concerning each head and the
corresponding visualization post combination through Hungarian matching. We
observe that a few heads produce noisy masks and note that our strategy of
training with independent heads helps reduce this bias with other heads
helping to stabilize the final output.

TABLE III: Analysis of different combination schemes for multi-query
attention. Note that all models involve background masking as the masking
strategy

Distance Matching Training CorLoc mIoui mBoi Euclidean Greedy ✘ 58.62 $\pm$
1.0 27.84 $\pm$ 0.9 21.88 $\pm$ 1.1 ✓ 50.75 $\pm$ 2.3 33.39 $\pm$ 0.8 23.08
$\pm$ 1.4 Hungarian ✘ 67.03 $\pm$ 1.8 38.1 $\pm$ 0.6 29.89 $\pm$ 1.8 ✓ 58.04
$\pm$ 0.7 28.64 $\pm$ 0.3 23.68 $\pm$ 0.6 Cosine Greedy ✘ 60.50 $\pm$ 0.6
29.93 $\pm$ 1.0 23.59 $\pm$ 1.1 ✓ 43.80 $\pm$ 1.4 31.73 $\pm$ 0.3 20.13 $\pm$
0.5 Hungarian ✘ 68.99 $\pm$ 0.7 39.42 $\pm$ 0.3 39.74 $\pm$ 0.3 ✓ 61.44 $\pm$
3.8 32.26 $\pm$ 1.4 32.49 $\pm$ 1.3

We compare various head combination strategies in Table III. In our analysis,
we compare Euclidean and Cosine distance metrics. We use this distance to
compute the similarity amongst different pairs of heads to align them.
Additionally, we employ a Hungarian or Greedy matching strategy to pair each
slot. In the greedy strategy, after computing the similarity matrix, we
perform the matching greedily. We iterate over the reference head and identify
the best-matching slot from the head under consideration based on the
similarity matrix.

We also compare based on training; the checkmark in the table indicates
whether we use this matching strategy during training. The ✘ mark illustrates
that we select a random head during training, and the combination is performed
only during the inference phase. We observe that if we combine heads during
the training phase, the performance of the model significantly drops. This
drop indicates that each head does not produce independent object
representations that stabilize the negative impact produced by other heads. We
also observe that using the Hungarian matching strategy improves the result
compared to other combination strategies.

###  IV-E Additional Ablations

We present an ablation study on the number of heads in Table IV and the use of
different patch tokens in Fig. 5. In Table IV we observe that by increasing
number of heads the performance of the model increases and converges to a
certain value. Notably, we also observe that the standard deviation also
decreases as we increase the number of heads.

TABLE IV: Ablation study concerning the number of heads in multi-query slot
attention

#Heads CorLoc mIoui mBoi 1 64.48 $\pm$ 0.4 36.35 $\pm$ 1.3 37.34 $\pm$ 0.4 2
67.40 $\pm$ 2.0 38.19 $\pm$ 0.4 37.54 $\pm$ 1.3 4 69.79 $\pm$ 1.2 39.14 $\pm$
0.4 39.46 $\pm$ 0.3 8 68.99 $\pm$ 0.7 39.42 $\pm$ 0.3 39.74 $\pm$ 0.3 16 68.21
$\pm$ 1.2 39.46 $\pm$ 0.1 39.82 $\pm$ 0.04

In Fig. 5 we observe the performance of our model against using different
patch tokens. We clearly notice that key tokens give slightly better results
than the value tokens and that the query tokens produce sub-optimal results
when compared to the other tokens.

Figure 5: Ablation study concerning the use of different patch tokens namely
key, query and value.

###  IV-F Computational Cost

We discuss the computational cost associated with our model in Table V. We
compare total and trainable parameters, floating point operations per second
(FLOPs), and the time required for forward and backward passes during training
and inference.

TABLE V: Computational cost analysis with different configurations for a batch
size of 4. We report the floating point operations per second (FLOPs) in
millions, the number of parameters in millions and time required in
milliseconds

Configuration FLOPs (M) Parameters (M) Time (in ms) Total Trainable Forward
Backward Inference Slot Attention 151.16 26.82 5.2 17.69 24.92 20.02 Maksed
Slot Attention 151.16 26.82 5.2 18.18 28.85 20.02 Muti Query Attention 151.23
36.84 15.2 30.36 38.20 55.72

In Table V, we observe an increase in training time for models involving
masking, which we attribute to evaluating each patch token to decide whether
masking is required. However, it is noteworthy that the time required remains
constant because masking is not involved in the inference phase. Finally, the
inference time for our multi-query slot attention increases by a significant
factor. However, our implementation is not optimized for speed. With a better
implementation, we expect the cost of multi-query slot attention to become
negligible. Our proposed multi-query attention and combination involves a
slight increase in computational cost, while the improvement in the result is
quite significant.

###  IV-G Comparison with previous methods

We compare our method with several previous works in unsupervised object
discovery. For this task, we compare our method against methods ranging from
pre-deep learning era [8, 7, 24] to CNN-based localization [24, 10] and graph-
based methods [9]. We also compare our method with self-supervised ViT-based
works [14, 17, 44, 15, 18].

TABLE VI: Comparative performance of our method against existing works in
unsupervised object discovery

Method CorLoc Selective Search [8] 20.9 Edge Boxes [7] 31.6 Kim et al. [23]
46.4 Zhang et al. [24] 50.5 Wei et al. [10] 53.1 rOSD [9] 55.3 DINO-seg
(ViT-S/16) [12, 14] 46.2 LOST (ViT-S/8) [14] 57.0 LOST (ViT-S/16) [14] 64.0
Deep Spectral Methods [17] 66.4 TokenCut [15] 72.1 FreeSOLO [44] 56.7 DINOSAUR
[18] 69.8 $\pm$ 4.9 Ours 68.99 $\pm$ 0.7

We enlist the quantitative results in Table VI. Compared to methods from the
pre-deep learning period, the performance of our approach is significantly
improved. CNN-based methods [24, 10] perform relatively well, but self-
supervised ViT-based methods perform much better. One possible explanation for
this can be traced to the fact that ViT implicitly induces an additional
structural bias of decomposing each image into non-overlapping patches, which
helps to evaluate each patch representation and correlate better with
neighboring regions to localize an object. Among modern ViT approaches, only
Tokencut [15] and DINOSAUR [18] obtain better results than our method. Most
methods have an inclination to use a larger ViT model or a smaller patch size,
while our experiments used ViT-Small with a patch size of 16.

##  V Conclusion

In this paper, we presented some strategies to improve object discovery
without labels in an object-centric representation learning approach. Contrary
to the previous approaches, we mask the background during training, forcing
the model to learn discriminative object representations by reconstructing the
background. We then use multiple queries (slots), trained independently and
combined during inference to produce more stable masks. Our detailed
investigation with different settings showcases the strength and usability of
each of the modules.

One obvious limitation of our method is the fixed number of slots. In future
work, it would be interesting to investigate how models can dynamically select
the number of slots based on an input image. In our analysis, we find how
different masking strategies influence the model. Hence, we wish to
investigate how we control the fine-grained knowledge that we introduce
through these masking strategies. Another related line of work that we look
forward to exploring is the robustness of our method towards out-of-
distribution data and its ability to handle domain shifts.

## Acknowledgment

This research was supported by the National Science and Engineering Research
Council of Canada (NSERC), via its Discovery Grant program and MITACS through
the Globalink program. The authors acknowledge support provided in part by
Calcul Quebéc and the Digital Research Alliance of Canada.

## References

  * [1] B. Wu, F. Iandola, P. H. Jin, and K. Keutzer, “Squeezedet: Unified, small, low power fully convolutional neural networks for real-time object detection for autonomous driving,” in _CVPRw_ , 2017.
  * [2] G.-S. Xia, X. Bai, J. Ding, Z. Zhu, S. Belongie, J. Luo, M. Datcu, M. Pelillo, and L. Zhang, “Dota: A large-scale dataset for object detection in aerial images,” in _CVPR_ , 2018.
  * [3] T. Wang, X. He, S. Su, and Y. Guan, “Efficient scene layout aware object detection for traffic surveillance,” in _ICCVw_ , 2017, pp. 53–60.
  * [4] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft coco: Common objects in context,” in _ECCV_ , 2014.
  * [5] R. Girshick, “Fast r-cnn,” in _ICCV_ , 2015.
  * [6] A. Dittadi, S. S. Papa, M. De Vita, B. Schölkopf, O. Winther, and F. Locatello, “Generalization and robustness implications in object-centric learning,” in _ICML_ , 2022.
  * [7] C. L. Zitnick and P. Dollár, “Edge boxes: Locating object proposals from edges,” in _ECCV_ , 2014.
  * [8] J. R. Uijlings, K. E. Van De Sande, T. Gevers, and A. W. Smeulders, “Selective search for object recognition,” _IJCV_ , 2013.
  * [9] V. H. Vo, E. Sizikova, C. Schmid, P. Pérez, and J. Ponce, “Large-scale unsupervised object discovery,” _NeurIPS_ , 2021.
  * [10] X.-S. Wei, C.-L. Zhang, J. Wu, C. Shen, and Z.-H. Zhou, “Unsupervised object discovery and co-localization by deep descriptor transformation,” _PR_ , 2019.
  * [11] M. Cho, S. Kwak, C. Schmid, and J. Ponce, “Unsupervised object discovery and localization in the wild: Part-based matching with bottom-up region proposals,” in _CVPR_ , 2015.
  * [12] M. Caron, H. Touvron, I. Misra, H. Jégou, J. Mairal, P. Bojanowski, and A. Joulin, “Emerging properties in self-supervised vision transformers,” in _ICCV_ , 2021.
  * [13] K. He, X. Chen, S. Xie, Y. Li, P. Dollár, and R. Girshick, “Masked autoencoders are scalable vision learners,” in _CVPR_ , 2022.
  * [14] O. Siméoni, G. Puy, H. V. Vo, S. Roburin, S. Gidaris, A. Bursuc, P. Pérez, R. Marlet, and J. Ponce, “Localizing objects with self-supervised transformers and no labels,” in _BMVC_ , 2021.
  * [15] Y. Wang, X. Shen, S. X. Hu, Y. Yuan, J. L. Crowley, and D. Vaufreydaz, “Self-supervised transformers for unsupervised object discovery using normalized cut,” in _CVPR_ , 2022.
  * [16] A. Zadaianchuk, M. Kleindessner, Y. Zhu, F. Locatello, and T. Brox, “Unsupervised semantic segmentation with self-supervised object-centric representations,” in _ICLR_ , 2022.
  * [17] L. Melas-Kyriazi, C. Rupprecht, I. Laina, and A. Vedaldi, “Deep spectral methods: A surprisingly strong baseline for unsupervised semantic segmentation and localization,” in _CVPR_ , 2022.
  * [18] M. Seitzer, M. Horn, A. Zadaianchuk, D. Zietlow, T. Xiao, C.-J. Simon-Gabriel, T. He, Z. Zhang, B. Schölkopf, T. Brox, and F. Locatello, “Bridging the gap to real-world object-centric learning,” in _ICLR_ , 2023.
  * [19] F. Locatello, D. Weissenborn, T. Unterthiner, A. Mahendran, G. Heigold, J. Uszkoreit, A. Dosovitskiy, and T. Kipf, “Object-centric learning with slot attention,” in _NeurIPS_ , 2020.
  * [20] N. Li, B. Sun, and J. Yu, “A weighted sparse coding framework for saliency detection,” in _CVPR_ , 2015.
  * [21] Q. Yan, L. Xu, J. Shi, and J. Jia, “Hierarchical saliency detection,” in _CVPR_ , 2013.
  * [22] P. Jiang, H. Ling, J. Yu, and J. Peng, “Salient region detection by ufo: Uniqueness, focusness and objectness,” in _CVPR_ , 2013.
  * [23] G. Kim and A. Torralba, “Unsupervised detection of regions of interest using iterative link analysis,” in _NeurIPS_ , 2009.
  * [24] R. Zhang, Y. Huang, M. Pu, J. Zhang, Q. Guan, Q. Zou, and H. Ling, “Object discovery from a single unlabeled image by mining frequent itemsets with multi-scale features,” _TIP_ , 2020.
  * [25] E. Collins, R. Achanta, and S. Susstrunk, “Deep feature factorization for concept discovery,” in _ECCV_ , 2018.
  * [26] O. Siméoni, C. Sekkat, G. Puy, A. Vobeckỳ, É. Zablocki, and P. Pérez, “Unsupervised object localization: Observing the background to discover objects,” in _CVPR_ , 2023.
  * [27] C. Doersch, A. Gupta, and A. A. Efros, “Unsupervised visual representation learning by context prediction,” in _ICCV_ , 2015.
  * [28] M. Noroozi and P. Favaro, “Unsupervised learning of visual representations by solving jigsaw puzzles,” in _ECCV_ , 2016.
  * [29] D. Pathak, P. Krahenbuhl, J. Donahue, T. Darrell, and A. A. Efros, “Context encoders: Feature learning by inpainting,” in _CVPR_ , 2016.
  * [30] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick, “Momentum contrast for unsupervised visual representation learning,” in _CVPR_ , 2020.
  * [31] I. Misra and L. v. d. Maaten, “Self-supervised learning of pretext-invariant representations,” in _CVPR_ , 2020.
  * [32] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton, “A simple framework for contrastive learning of visual representations,” in _ICML_ , 2020.
  * [33] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, “Unsupervised learning of visual features by contrasting cluster assignments,” in _NeurIPS_ , 2020.
  * [34] Y. M. Asano, C. Rupprecht, and A. Vedaldi, “Self-labelling via simultaneous clustering and representation learning,” in _ICLR_ , 2020.
  * [35] P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol, “Extracting and composing robust features with denoising autoencoders,” in _ICML_ , 2008.
  * [36] H. Bao, L. Dong, S. Piao, and F. Wei, “BEit: BERT pre-training of image transformers,” in _ICLR_ , 2022.
  * [37] Z. Xie, Z. Zhang, Y. Cao, Y. Lin, J. Bao, Z. Yao, Q. Dai, and H. Hu, “Simmim: A simple framework for masked image modeling,” in _CVPR_ , 2022.
  * [38] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NeurIPS_ , 2017.
  * [39] N. Shazeer, “Fast transformer decoding: One write-head is all you need,” _arXiv preprint arXiv:1911.02150_ , 2019.
  * [40] H. W. Kuhn, “The hungarian method for the assignment problem,” _Naval research logistics quarterly_ , 1955.
  * [41] N. Watters, L. Matthey, C. P. Burgess, and A. Lerchner, “Spatial broadcast decoder: A simple architecture for learning disentangled representations in vaes,” in _ICLRw_ , 2019.
  * [42] K. Greff, R. L. Kaufman, R. Kabra, N. Watters, C. Burgess, D. Zoran, L. Matthey, M. Botvinick, and A. Lerchner, “Multi-object representation learning with iterative variational inference,” in _ICML_ , 2019.
  * [43] M. Everingham, S. A. Eslami, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman, “The pascal visual object classes challenge: A retrospective,” _IJCV_ , 2015.
  * [44] X. Wang, Z. Yu, S. De Mello, J. Kautz, A. Anandkumar, C. Shen, and J. M. Alvarez, “Freesolo: Learning to segment objects without annotations,” in _CVPR_ , 2022.