$\mathcal{D}_{1},\mathcal{D}_{2}$ are close in relative error, i.e.,
$\max\Big{\\{}\|1-\mathcal{D}_{1}/\mathcal{D}_{2}\|_{\infty},\|1-\mathcal{D}_{2}/\mathcal{D}_{1}\|_{\infty}\Big{\\}}\leq\epsilon$.

###### Proof _of_ Lemma 18.

Let $\epsilon>0$ sufficiently small and assume that
$\|\bm{z}_{1}-\bm{z}_{2}\|_{\infty}\leq\epsilon$, i.e.,

$\max_{x\in[n]}\Big{|}\log\Big{(}\frac{\mathcal{D}_{1}(x)}{\mathcal{D}_{2}(x)}\Big{)}\Big{|}\leq\epsilon\,.$

For $x>0$, it holds that $1-\frac{1}{x}\leq\log_{e}(x)$888This inequality
holds when the base of the logarithm is $e$, the base that we have assumed
that we work with.. Hence, for any $x\in[n]$, we get that

$1-\frac{\mathcal{D}_{2}(x)}{\mathcal{D}_{1}(x)}\leq\log\Big{(}\frac{\mathcal{D}_{1}(x)}{\mathcal{D}_{2}(x)}\Big{)}\leq\epsilon\,,$

and

$1-\frac{\mathcal{D}_{1}(x)}{\mathcal{D}_{2}(x)}\leq\log\Big{(}\frac{\mathcal{D}_{2}(x)}{\mathcal{D}_{1}(x)}\Big{)}\leq\epsilon\,.$

This gives that

$\frac{\mathcal{D}_{1}(x)}{\mathcal{D}_{2}(x)}\geq 1-\epsilon~{}\text{ and
}~{}\frac{\mathcal{D}_{2}(x)}{\mathcal{D}_{1}(x)}\geq 1-\epsilon\,.$

This implies that both ratios are upper bounded by $1+\epsilon$. For
contradiction, assume that

$\frac{\mathcal{D}_{1}(x)}{\mathcal{D}_{2}(x)}>1+\epsilon\iff\frac{\mathcal{D}_{2}(x)}{\mathcal{D}_{1}(x)}<\frac{1}{1+\epsilon}\,.$

But, the Taylor expansion of the function $x\mapsto\frac{1}{1+x}$ is equal to
$1-x+O(x^{2})$ for $|x|<1$. Hence, for sufficiently small $\epsilon,$ the
desired bound follows. ∎

To wrap up, the proof of Theorem 4 goes as follows:

###### Proof _of_ Theorem 4.

Assume that $\bm{z}^{\star}\in\mathbb{R}^{n}$ is the true natural parameter
vector for the target distribution $\mathcal{D}$. By Lemma 18, in order to
obtain the desired relative error, it suffices to control $\bm{z}^{\star}$ in
$L_{\infty}$. Also, let $\bm{z}\in\mathbb{R}^{n}$ be a shifted variant of
$\bm{z}^{\star}$ so that $\langle\bm{1},\bm{z}\rangle=0$, i.e.,
$\bm{z}^{\star}=\bm{z}+C\bm{1}$ for some $C$. First, the algorithm draws
$N=\Theta\left(\frac{n}{\lambda(\bm{Q})\epsilon^{2}}\log(\frac{1}{\delta})\right)$
i.i.d. samples from the LSS with Laplacian matrix $\bm{Q}$. Using the
concentration of the Fiedler eigenvalue (Lemma 17), we have that this number
of samples is sufficient to apply Theorem 16. This will yield a vector
$\widehat{\bm{z}}$ so that $\|\bm{z}-\widehat{\bm{z}}\|_{2}\leq\epsilon$ with
probability $1-\delta$. We then apply the transformation described in Section
F.2 (which corresponds to Line 5-6 of Algorithm 5). This yields the desired
$L_{\infty}$ bound and completes the proof. ∎

##  Appendix F The Proof of Theorem 16 (Variant of [SBB+16])

In this section, we prove a slight variant of the algorithm of [SBB+16] where
the target weight vector satisfies the conditions
$\langle\bm{1},\bm{z}^{\star}\rangle=0$ and $|z^{\star}_{x}-z^{\star}_{y}|\leq
B$ for some constant $B$.

###  F.1 Description of the Learning Algorithm for Abstract Weight Vectors

In this section, we provide a complete description of the learning algorithm
of [SBB+16] (with a slight modification). We remark that the technical steps
required in order to establish our result follow the analysis of [SBB+16]. It
suffices to present an efficient learning algorithm that estimates the target
weights vector $\bm{z}^{\star}=(z_{1}^{\star},\ldots,z_{n}^{\star})$ in
$L_{\infty}$ norm. _We underline that for this section, the target vector
$\bm{z}^{\star}$ is an abstract weight vector and not the natural parameter
vector induced by a distribution._ We assume that $\bm{z}^{\star}$ lies in the
subspace $\Omega_{\phi},$ defined in Equation (F.1). Hence, it suffices that
the learning algorithm computes an estimate $\widehat{\bm{z}}$ such that
$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{2}\leq\epsilon$, with high probability,
for some accuracy parameter $\epsilon>0$.

###### Proof _of_ Theorem 16.

The algorithm minimizes the empirical negative log-likelihood over a subspace
$\Omega_{\phi}\subseteq\mathbb{R}^{n}$ of the natural parameter vectors. The
empirical negative log-likelihood objective with $N$ draws from the Local
Sampling Scheme corresponds to the function

$L_{N}(\bm{z};\\{((x_{i},y_{i}),q_{i})\\}_{i\in[N]})=-\frac{1}{N}\sum_{i=1}^{N}\bm{1}\\{q_{i}=1\\}z_{x_{i}}+\bm{1}\\{q_{i}=0\\}z_{y_{i}}-\log(\exp(z_{x_{i}})+\exp(z_{y_{i}}))\,,$

where $x_{i},y_{i}\in[n]$ and $q_{i}\in\\{0,1\\}$ for any $i\in[N]$. We
optimize this objective using gradient descent in the subspace
$\Omega_{\phi}$, where

$\Omega_{\phi}=\\{\bm{z}\in\mathbb{R}^{n}:\langle\bm{1},\bm{z}\rangle=0,\max_{(x,y)\in\mathcal{E}}|z_{x}-z_{y}|\leq\log(\phi)\\}\,.$
(F.1)

The first constraint $\langle\bm{1},\bm{z}\rangle=0$ is imposed in order to
work in the subspace where Laplacian matrices are positive definite (since any
Laplacian matrix has its first eigenvalue equal to $0$ with corresponding
eigenvector $\bm{1}$). The second constraint999As we mentioned, our learning
algorithm almost exactly follows the algorithm of [SBB+16]. The only
difference appears in the _second_ constraint of the set $\Omega_{\phi}$,
where [SBB+16] optimize over vectors with upper bounded $L_{\infty}$ norm.  is
equivalent to 2. Since any valid target distribution satisfies
$\frac{1}{\phi}\leq\frac{\mathcal{D}(x)}{\mathcal{D}(y)}\leq\phi$ for
$(x,y)\in\mathcal{E}$, we have that

$-\log(\phi)\leq z_{x}-z_{y}\leq\log(\phi)~{}\text{ for any
}x,y\in\mathcal{E}\,.$

Let $\bm{L}$ be the empirical Laplacian matrix whose Fiedler eigenvalue
$\lambda_{2}(\bm{L})$ is close to the true $\lambda_{2}(\bm{Q})$ (see Lemma
17). We introduce the following notation for the quadratic form
$\|\bm{v}\|_{L}^{2}:=\bm{v}^{T}\bm{L}\bm{v}$ for any vector
$\bm{v}\in\mathbb{R}^{n}$. The key idea of the algorithm of [SBB+16] is to
compute an estimate $\widehat{\bm{z}}$ in the $\|\cdot\|_{L}$ semi-norm.
Afterwards, by the min-max principle for Hermitian matrices, we have that

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}\geq\lambda_{2}(\bm{L})\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{2}^{2}\,.$
(F.2)

Hence, the estimation of the true natural parameter vector in $L_{2}$ norm is
directly implied. The analysis for the estimation in the $\bm{L}$ semi-norm is
based on the following fact about $M$-estimators. A proof of this result can
be found in [SBB+16].

######  Fact 3 (see [SBB+16]).

Let $\Omega_{1}=\\{\bm{z}\in\mathbb{R}^{n}:\langle\bm{1},\bm{z}\rangle=0\\}$
and let $\Omega\subseteq\Omega_{1}$. Consider the $M$-estimator

$\widehat{\bm{z}}\in\operatorname*{argmin}_{\bm{z}\in\Omega}\ell(\bm{z})\,,$

and let $\ell$ be a differentiable objective that is $\kappa$-strongly
convex101010A function $f:\mathcal{X}\rightarrow\mathbb{R}$ is
$\kappa$-strongly convex with respect to a norm $\|\cdot\|$ if, for all $x,y$
in the relative interior of the domain of $f$ and $\lambda\in(0,1)$, we have
$f(\lambda x+(1-\lambda)y)\leq\lambda
f(x)+(1-\lambda)f(y)-\frac{1}{2}\kappa\lambda(1-\lambda)\|x-y\|^{2}\,.$ If the
function $f$ is differentiable, then a second definition for $\kappa$-strong
convexity with respect to a norm $\|\cdot\|$ is that for all points $x,y$, we
have that $f(y)-f(x)-\langle\nabla f(x),y-x\rangle\geq\kappa\|x-y\|^{2}$.
Recall that the relative interior of a set $S$ is defined as its interior
within the affine hull of $S$, i.e., $\mathrm{relint}(S)=\\{x\in
S:\exists\epsilon>0,\mathcal{N}_{\epsilon}(x)\cap\mathrm{aff}(S)\subseteq
S\\}$.  at $\bm{z}^{\star}\in\Omega$ with respect to the $\bm{L}$ semi-norm.
Then, it holds that

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}\leq\frac{1}{\kappa}\|\nabla\ell(\bm{z}^{\star})\|_{L^{\dagger}}\,,$

where $\bm{L}^{\dagger}$ is the Moore-Penrose pseudo-inverse of $\bm{L}$.

Using the above result, it suffices to verify that the empirical negative log-
likelihood objective is strongly convex in the true parameter vector
$\bm{z}^{\star}\in\Omega_{\phi}$ and to upper bound the dual norm $\|\nabla
L_{N}(\bm{z}^{\star})\|_{L^{\dagger}}=\nabla
L_{N}(\bm{z}^{\star})^{T}\bm{L}^{\dagger}\nabla L_{N}(\bm{z}^{\star})$. Recall
that $\bm{L}$ is the empirical estimate of the true Laplacian matrix $\bm{Q}$.
We continue with two claims, that are sufficient in order to control the
$\bm{L}$ semi-norm of the vector $\bm{z}^{\star}-\widehat{\bm{z}}.$

######  Claim 8 (Strong Convexity at $\bm{z}^{\star}$).

The empirical negative log-likelihood $L_{N}(\bm{z})$ is $\kappa$-strongly
convex at $\bm{z}^{\star}\in\Omega_{\phi}$ with respect to the $\bm{L}$ semi-
norm with $\kappa=\mathrm{poly}(1/\phi)$.

###### Proof.

It suffices to lower bound the quadratic form $\bm{w}^{T}\nabla
L_{N}(\bm{z})\bm{w}$ for all vectors $\bm{w}\in\mathbb{R}^{n}$ and
$\bm{z}\in\Omega_{\phi}$. As in Lemma 17, we introduce the measurement vector
notation $\bm{v}_{i}\in\\{-1,0,1\\}^{n}$ in order to represent each drawn
sample $((x_{i},y_{i}),q_{i})$ (recall that the edges in this training set lie
in $\mathcal{E}$ and $q_{i}\in\\{0,1\\}$). We set
$\bm{v}_{i}(x_{i})=2q_{i}-1,\bm{v}_{i}(y_{i})=-\bm{v}_{i}(x_{i})$ and the
other coordinates are set to $0$. These measurement vectors are the building
blocks of the empirical matrix (see Lemma 17), since we have that

$\bm{L}=\frac{1}{N}\sum_{i=1}^{N}\bm{v}_{i}\bm{v}_{i}^{T}:=\frac{1}{N}\bm{X}^{T}\bm{X}\,.$

Note that the matrix $\bm{X}\in\\{-1,0,1\\}^{N\times n}$ has the $i$-th
measurement vector $\bm{v}_{i}^{T}$ as its $i$-th row. Using this notation and
following the computations of [SBB+16] for the Hessian of $L_{N}$, we get that

$\nabla^{2}L_{N}(\bm{z})=\frac{1}{N}\sum_{i=1}^{N}\Big{\\{}\bm{1}\\{v_{i}=1\\}A_{1}+\bm{1}\\{v_{i}=0\\}A_{0}\Big{\\}}\bm{v}_{i}\bm{v}_{i}^{T}\,,$

where

$A_{1}=(\log
F)^{\prime\prime}(\langle\bm{z},\bm{v}_{i}\rangle),A_{0}=(\log(1-F))^{\prime\prime}(\langle\bm{z},\bm{v}_{i}\rangle)~{}\text{
and }~{}F(x)=1/(1+\exp(-x))\,.$

The function $F(x)=1/(1+\exp(-x))$ is the Bradley-Terry function. The function
$F$ is strongly-log concave in the interval $[-\log(\phi),\log(\phi)].$
Specifically, we have that

$\frac{d^{2}}{dx^{2}}\Big{(}-\log
F(x)\Big{)}=\frac{e^{x}}{(1+e^{x})^{2}}\geq\frac{\phi}{(1+\phi)^{2}}=:\kappa(\phi)\,,$

since the mapping $x\mapsto\exp(x)/(1+\exp(x))^{2}$ is symmetric and, so,
focusing on the interval $[0,\log(\phi)]$, its minimum is attained at
$\log(\phi)$.

$-5$$5$$10$$5\cdot 10^{-2}$$1\cdot
10^{-1}$$0.15$$0.2$$0.25$$y=\frac{\exp(x)}{(1+\exp(x))^{2}}$ Figure 3: The
second derivative of the negative logarithm of the Bradley-Terry function $F$.

The physical interpretation of these properties is that for the pair $i,j$, it
does not matter whether $i\succ j$ or $j\succ i$ (symmetry) but if the
comparison gap (i.e., $|z_{i}-z_{j}|$) attains very large values, then the
strong convexity will be very low. Intuitively, note also that, since
$\exp(x)/(1+\exp(x))^{2}\leq 1/4$, the desired objective is also smooth and it
is known that strong convexity and smoothness of a function over a domain of
the form
$\\{\bm{z}\in\mathbb{R}^{n}:\langle\bm{1},\bm{z}\rangle=0\\}\cap\mathcal{Z}$,
where $\mathcal{Z}$ is convex, imply that the function satisfies the PL
inequality over $\mathcal{Z}$. Hence, for this function, gradient-based
methods will converge with fast rates (see e.g., [VYZ20]).

Since any $\bm{z}\in\Omega_{\phi}$, we conclude that for any $\bm{w}$

$\bm{w}^{T}\nabla
L_{N}(\bm{z})\bm{w}\geq\frac{\kappa(\phi)}{N}\|\bm{X}\bm{w}\|_{2}^{2}\,,$

where $\bm{X}$ the above measurement matrix and $\bm{z}\in\Omega_{\phi}$.
Hence, if we define $\bm{\Delta}=\widehat{\bm{z}}-\bm{z}^{\star}$, we get (in
order to form the definition of strong convexity) that

$L_{N}(\bm{z}^{\star}+\bm{\Delta})-L_{N}(\bm{z}^{\star})-\langle\nabla
L_{N}(\bm{z}^{\star}),\bm{\Delta}\rangle\geq\frac{\kappa(\phi)}{N}\|\bm{X}\bm{\Delta}\|_{2}^{2}=\kappa(\phi)\|\bm{\Delta}\|_{L}^{2}\,,$

since
$\|\bm{\Delta}\|_{L}^{2}=\bm{\Delta}^{T}\bm{L}\bm{\Delta}=\frac{1}{N}\bm{\Delta}^{T}\bm{X}^{T}\bm{X}\bm{\Delta}=\frac{1}{N}\|\bm{X}\bm{\Delta}\|_{2}^{2}$.
Hence, the empirical negative log-likelihood objective is
$\kappa(\phi)$-strongly convex at the true natural parameter vector
$\bm{z}^{\star}$ with respect to the $\bm{L}$ semi-norm. ∎

From the strong-convexity guarantee and, using 3, we get that

$\|\bm{\Delta}\|_{L}^{2}\leq\frac{1}{\kappa(\phi)}\|\nabla
L_{N}(\bm{z}^{\star})\|_{L^{\dagger}}\,.$ (F.3)

######  Claim 9 (Dual norm).

Let $\bm{L}$ be the empirical Laplacian estimate matrix of $\bm{Q}$ and let
$\bm{L}^{\dagger}$ the Moore-Penrose pseudo-inverse of $\bm{L}$. There exists
a random vector $\bm{Y}\in\mathbb{R}^{n}$ such that

$\|\nabla
L_{N}(\bm{z}^{\star})\|_{L^{\dagger}}=\frac{1}{N^{2}}(\bm{X}^{T}\bm{Y})^{T}\bm{L}^{\dagger}(\bm{X}^{T}\bm{Y})\,,$

where $\bm{X}$ is the $N\times n$ measurements matrix.

###### Proof.

We first provide a compact form the the gradient $\nabla
L_{N}(\bm{z}^{\star})$. Again, following the analysis of [SBB+16], we define a
random vector $\bm{Y}\in\mathbb{R}^{n}$ with independent coordinates
$(Y_{1},\ldots,Y_{n})$ where we set
$Y_{i}=F^{\prime}(\langle\bm{z}^{\star},\bm{v}_{i}\rangle)/F(\langle\bm{z}^{\star},\bm{v}_{i}\rangle)$
with probability $F(\langle\bm{z}^{\star},\bm{v}_{i}\rangle)$ and we set
$Y_{i}=-F^{\prime}(\langle\bm{z}^{\star},\bm{v}_{i}\rangle)/(1-F(\langle\bm{z}^{\star},\bm{v}_{i}\rangle))$
otherwise. Recall that $F$, in our setting, is the Bradley-Terry function
$F(x)=1/(1+\exp(-x))$ and $\bm{v}_{i}\in\\{-1,0,1\\}^{n}$ is the $i$-th
comparison vector indicating the drawn edge. Hence, after computing the
gradient at the true parameter vector $\bm{z}^{\star}$, one gets

$\nabla L_{N}(\bm{z}^{\star})=-\frac{1}{N}\bm{X}^{T}\bm{Y}\,.$

Using the above, 9 follows. ∎

We now introduce the matrix
$\bm{J}:=\frac{1}{\kappa(\phi)N^{2}}\bm{X}\bm{L}^{\dagger}\bm{X}^{T}$ .
Combining Equation (F.3) with 9, we get that

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}\leq\bm{Y}^{T}\bm{J}\bm{Y}\,.$

Hence, in order to bound the $\bm{L}$ semi-norm estimation error, it suffices
to control the quadratic form of the right hand side. Similarly to [SBB+16],
our goal is to apply the Hanson-Wright inequality (see Lemma 19) in order to
control the quadratic form.

######  Lemma 19 ([HW71, RV13]).

Let $\bm{Y}\in\mathbb{R}^{n}$ be a random vector with independent zero-mean
components, which are sub-Gaussian with parameter $K$ and let
$\bm{J}\in\mathbb{R}^{n\times n}$ be an arbitrary matrix. Then there is a
universal constant $c>0$ such that

$\Pr\left[\left|\bm{Y}^{T}\bm{J}\bm{Y}-\mathbb{E}[\bm{Y}^{T}\bm{J}\bm{Y}]\right|>t\right]\leq
2\exp\left(-c\min\left\\{\frac{t^{2}}{K^{4}\|\bm{J}\|^{2}_{F}},\frac{t}{K^{2}\|\bm{J}\|_{\mathrm{2}}}\right\\}\right)\,,$

for any $t>0$.

Observe that $\mathbb{E}[\bm{Y}]=0$ and, for any $i\in[n]$, we have that

$|Y_{i}|\leq\sup_{\bm{z}\in\Omega_{\phi}}\sup_{\bm{x}\in\mathbb{X}}\max\left\\{\frac{F^{\prime}(\langle\bm{z},\bm{x}\rangle)}{F(\langle\bm{z},\bm{x}\rangle)},\frac{F^{\prime}(\langle\bm{z},\bm{x}\rangle)}{1-F(\langle\bm{z},\bm{x}\rangle)}\right\\}\,,$

where $\mathbb{X}\subseteq\\{-1,0,1\\}^{n}$ is the space of all valid
measurement vectors (they should induce edges in $\mathcal{E}$). Hence, we get
that

$|Y_{i}|\leq\max_{x\in[-\log(\phi),\log(\phi)]}\max\Big{\\{}\frac{\exp(-x)/(1+\exp(-x))^{2}}{1/(1+\exp(-x))},\frac{\exp(-x)/(1+\exp(-x))^{2}}{\exp(-x)/(1+\exp(-x))}\Big{\\}}=:u(\phi)\,.$

Note that $u(\phi)\leq 1$, since, for $0<b<1$, it holds that
$\max\left\\{\frac{1}{b},\frac{1}{1-b}\right\\}\leq\frac{1}{b(1-b)}$. Since
each $|Y_{i}|$ is bounded, we get that the random variables are $u(\phi)$-sub-
Gaussian. Also, we have that

$\mathbb{E}[\bm{Y}^{T}\bm{J}\bm{Y}]\leq\mathbb{E}\Big{[}\|\bm{Y}\|_{\infty}^{2}\mathrm{tr}(\bm{J})\Big{]}\leq\frac{u(\phi)^{2}}{\mathrm{poly}(\kappa(\phi))}\frac{n}{N}\,.$

It remains to compute the two matrix norms. As in [SBB+16], one gets that

$\|\bm{J}\|^{2}_{F}=\sum_{i,j}|\bm{J}_{ij}|^{2}=\frac{n-1}{\mathrm{poly}(\kappa(\phi))N^{2}}=\Theta(n/N^{2})\,,$

and

$\|\bm{J}\|_{\mathrm{2}}=\max_{\bm{x}\neq\bm{0}}\|\bm{J}\bm{x}\|_{2}/\|\bm{x}\|_{2}=\frac{1}{\mathrm{poly}(\kappa(\phi))N}=\Theta(1/N)\,.$

Applying the Hanson-Wright concentration inequality, we conclude that

$\Pr\Big{[}\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}>c\cdot
t\frac{u(\phi)^{2}}{\mathrm{poly}(\kappa(\phi))}\frac{n}{N}\Big{]}\leq
e^{-t}\,,$

for all $t\geq 1$ and some universal constant $c>0$. Recall that $\phi$ is the
constant of 2 and hence the term
$\frac{u(\phi)^{2}}{\mathrm{poly}(\kappa(\phi))}\in\Theta(1)$. Finally, note
that integrating the above tail bound, one gets the desired on expectation
bound. ∎

###  F.2 Application of Algorithm 6 to Distributions

Given a target distribution $\mathcal{D}$, the associated natural parameters
vector $\bm{z}=\log(\mathcal{D})$ satisfies $\langle\bm{1},\bm{z}\rangle\leq
0$. Hence, we have to shift it appropriately in order to apply Algorithm 6.
Recall that the condition $\langle\bm{1},\bm{z}\rangle=0$ is only useful for
identifiability purposes of the BTL model.

Given a target distribution $\mathcal{D}\in\Delta^{n}$, we convert it to the
following weights vector: let $A=\sum_{x\in[n]}\log(\mathcal{D}(x))$ and set
$\mathcal{D}^{\prime}(x)=\exp(-A/n)\mathcal{D}(x)$. So, we have to shift
$\bm{z}$ in the direction $(-A/n)\cdot\bm{1}$ and obtain the weight vector
$\bm{z}^{\prime}$. For the weights $(\mathcal{D}^{\prime}(x))_{x\in[n]}$ with
weight vector $\bm{z}^{\prime}$, it holds that

  1. 1.

$\langle\bm{1},\bm{z}^{\prime}\rangle=\sum_{x\in[n]}(-A/n+\log(\mathcal{D}(x)))=0$
and

  2. 2.

for any $x,y\in[n]$, it holds that
$\mathcal{D}^{\prime}(x)/\mathcal{D}^{\prime}(y)=\mathcal{D}(x)/\mathcal{D}(y)$.

Given an estimate for $\bm{z}^{\prime}$, one can extract a good approximation
for the natural parameter vector $\bm{z}$ of $\mathcal{D}.$ In particular, the
following properties hold: first, given two distributions $\bm{p}\neq\bm{q}$,
it holds that $\bm{z}^{\prime}(\bm{p})\neq\bm{z}^{\prime}(\bm{q})$, i.e., any
$\bm{z}^{\prime}$ is uniquely identified by its distribution since one of the
following will hold: if
$\sum_{i\in[n]}\log(p_{i})=A=\sum_{i\in[n]}\log(q_{i})$, then since there
exists $j\in[n]$ so that $p_{j}\neq q_{j}$, we have that
$z(\bm{p})^{\prime}_{j}=\log(p_{j})-A/n\neq\log(q_{j})-A/n=z(\bm{q})^{\prime}_{j}$.
Otherwise, if, without loss of generality,
$A_{p}=\sum_{i}\log(p_{i})>\sum_{i}\log(q_{i})=A_{q}$, we have that there
exists $j\in[n]$ so that $p_{j}<q_{j}$ and so
$z(\bm{p})^{\prime}_{j}=\log(p_{j})-A_{p}/n<\log(q_{j})-A_{q}/n=z(\bm{q})^{\prime}_{j}$.
Hence, any distribution $\mathcal{D}$ uniquely induces a vector
$\bm{z}^{\prime}$. Moreover, the actual natural parameter vector $\bm{z}$ can
be estimated having an estimation for $\bm{z}^{\prime}$. Assume that we have
an estimate $\widehat{\bm{z}^{\prime}}$ that satisfies
$\|\bm{z}^{\prime}-\widehat{\bm{z}^{\prime}}\|_{2}\leq\epsilon$. We can
estimate $\bm{z}$ using a vector $\widehat{\bm{z}}$ (that can be extracted
from our estimate $\widehat{\bm{z}^{\prime}}$) as follows: Let
$\bm{z}^{\prime}=\bm{z}+C\bm{1}$, where $C=-A/n.$ In order to initiate our
exact sampling algorithm, an $L_{\infty}$ estimate for $\bm{z}$ is only
required. We have that

$\|\bm{z}-\widehat{\bm{z}}\|_{\infty}=\|(\bm{z}^{\prime}-C\bm{1})-(\widehat{\bm{z}^{\prime}}-C^{\prime}\bm{1})\|_{\infty}\leq\|\bm{z}^{\prime}-\widehat{\bm{z}^{\prime}}\|_{\infty}+|C-C^{\prime}|\,,$

where the estimate $\widehat{\bm{z}^{\prime}}$ satisfies
$\|\bm{z}^{\prime}-\widehat{\bm{z}^{\prime}}\|_{\infty}\leq\|\bm{z}^{\prime}-\widehat{\bm{z}^{\prime}}\|_{2}\leq\epsilon$
via Algorithm 6 and the shift constant can be estimated since we know that
$\mathcal{D}$ is a distribution:

$\sum_{x\in[n]}\exp(\widehat{z}_{x})=1\iff\sum_{x\in[n]}e^{\widehat{z^{\prime}}_{x}-C^{\prime}}=1\iff
e^{C^{\prime}}=\sum_{x\in[n]}e^{\widehat{z^{\prime}}_{x}}\,.$

Note that the right hand side of the above equation contains only our
estimates. We have that $\sum_{x\in[n]}\exp(z_{x})=1$ and so we set
$e^{C}:=\sum_{x\in[n]}e^{z^{\prime}_{x}}$. Since it holds that
$|z^{\prime}_{x}-\widehat{z^{\prime}}_{x}|\leq\epsilon$ for any $x\in[n]$, we
have that $|C-C^{\prime}|\leq O(\epsilon)$. This gives that for the actual
natural parameters it holds that $\|\bm{z}-\widehat{\bm{z}}\|_{\infty}\leq
O(\epsilon)$.

Hence, given a distribution $\mathcal{D}$, we can learn the weights
$\bm{z}^{\prime}$ in $L_{2}$ norm, satisfying the conditions of Algorithm 6.
From this estimation, we can get the estimation for the natural parameters
$\bm{z}$ by removing the introduced shift. We remark that the above shifting
methodology can be applied to any score vector $\bm{z}$ satisfying
$\langle\bm{1},\bm{z}\rangle=B\neq 0$.

##  Appendix G Local Sampling Schemes and Hypergraphs

In this section, we discuss how to extend our analysis to sets of size larger
that 2. The hypergraph structure of Local Sampling Schemes can be settled as
follows:

######  Definition 20 (Hypergraph Structure of LSS).

Let $\mathcal{Z}$ be a finite discrete domain and let $\mathcal{Q}$ be a
distribution supported on subsets of $\mathcal{Z}$. Then, the hypergraph
$G=(V,E)$ with vertex set $V=\mathcal{Z}$ and hyperedge set
$E=\mathrm{supp}(\mathcal{Q})$ is called a Local Sampling Scheme hypergraph.
If $\mathcal{Q}$ is a pair distribution supported on
$\mathcal{Z}\times\mathcal{Z}$, $G$ corresponds to a graph.

The general Markov Chain for distributions $\mathcal{Q}$, supported on sets
$S\subseteq 2^{[n]}$ has the following transition probabilities:

$p_{xy}=\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)\frac{\mathcal{D}(y)}{\mathcal{D}(S)}=\mathcal{D}(y)\sum_{S\supseteq\\{x,y\\}}\frac{\mathcal{Q}(S)}{\mathcal{D}(S)}\,.$
(G.1)

For the transition $x\rightarrow y$, we can think of a flow $f_{xy}$ with mass
$p_{xy}$ and, hence, induce a (simple) graph structure on a flow graph
$F=(f_{xy})_{xy}$. Observe that any pair $(x,y)$ shares the same collection of
hyperedges and, hence, we have that:

$\frac{p_{xy}}{p_{yx}}=\frac{\mathcal{D}(y)}{\mathcal{D}(x)}\frac{\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)/\mathcal{D}(S)}{\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)/\mathcal{D}(S)}=\frac{\mathcal{D}(y)}{\mathcal{D}(x)}\,.$

The ergodicity of the flow graph implies that the stationary distribution
corresponds to $\mathcal{D}$ and is unique. For what follows, we consider the
case where any hyperedge has size $k$, i.e., $k$-uniform hypergraphs. The
Laplacian of the distribution $\mathcal{Q}$ can be generalized over hyperedges
and have that

$\bm{Q}_{xy}=-\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)~{}\text{ for any
}x,y\in[n]~{}\text{ and }\bm{Q}_{xx}=(k-1)\sum_{S\ni x}\mathcal{Q}(S)~{}\text{
for any }x\in[n]\,.$

In the following section, we describe some necessary notation.

###  G.1 Notation

We denote the set $\binom{[n]}{k}$ the family of size $k$ subsets of the
ground set $[n]$. Let $\mathcal{Q}$ be a distribution on $\binom{[n]}{k}$.
Such a distribution will be called a $k$-set distribution. Recall that a pair
distribution is simply a $2$-set distribution. A sample from the Local
Sampling Scheme $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$, where
$\mathcal{Q}$ is a $k$-set distribution, will be denoted

$(S,\bm{v})\sim\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})\,,$

where $S\in\mathrm{supp}(\mathcal{Q})$ and, in the case where $i\in S$ won
between the elements of $S$, we have that $\bm{v}=\bm{e}_{i}\in\mathbb{R}^{n}$
($\bm{v}$ is the indicator vector of the winning node) and we have that
$\Pr[\bm{v}=\bm{e}_{i}]=\mathcal{D}(i)/\mathcal{D}(S)\bm{1}\\{i\in S\\}$. For
the hypergraph case, the canonical transition matrix induced by the Local
Sampling Scheme will be denoted by $\bm{P}$. In the case $k=2$, this matrix
was denoted by $\bm{M}$ (recall Equation (2.1)). Let $\bm{P}$ denote the
transition matrix of the Markov chain, associated with the Local Sampling
Scheme $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$, where $\mathcal{Q}$
corresponds to a $k$-set distribution. The entries of
$\bm{P}=[\bm{P}_{xy}]_{x,y\in[n]}$ are defined as:

$\bm{P}_{xy}=\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)\frac{\mathcal{D}(y)}{\mathcal{D}(S)}~{}\text{
for }~{}x\neq y~{}\text{ and }~{}\bm{P}_{xx}=1-\sum_{y\neq
x}\bm{P}_{xy}~{}\text{ for }x\in[n]\,.$ (G.2)

Observe that the transition from $x$ to $y$ is performed when

  1. 1.

a hyperedge $S\in\mathrm{supp}(\mathcal{Q})$ is chosen (with probability
$\mathcal{Q}(S)$) and both $x$ and $y$ lie in $S$,

  2. 2.

and the vertex $y\in[n]$ is the ’winning’ node among the nodes of $S$, i.e.,
$y$ is drawn from the conditional distribution $\mathcal{D}_{S}$.

There is a natural reduction to the graph case. Consider the marginals of
$\mathcal{Q}$ to $2$-sets (i.e., edges). Then, one can define a Markov chain
over a graph with $[n]$ nodes, whose transition probabilities are described by
$\bm{P}$. The random walk has the following properties: Since any pair of
vertices shares the same collection of hyperedges, we get that

$\frac{\bm{P}_{xy}}{\bm{P}_{yx}}=\frac{\mathcal{D}(y)}{\mathcal{D}(x)}\frac{\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)/\mathcal{D}(S)}{\sum_{S\supseteq\\{x,y\\}}\mathcal{Q}(S)/\mathcal{D}(S)}=\frac{\mathcal{D}(y)}{\mathcal{D}(x)}\,,$

for any pair of vertices. Moreover, the Markov chain is ergodic, since it is
irreducible, since by the structure of $\mathcal{Q}$ and since $\mathcal{D}$
is supported on $[n]$, one eventually can get from every state to every other
state with positive probability; and aperiodic, since it contains self-loops.
Hence, it has a unique stationary distribution which coincides with
$\mathcal{D}$, using the detailed balance equations.

##### Modifications of the LSS Conditions.

We can modify the information-theoretic connectivity condition (1) for
$k$-uniform hypergraphs and let $\mathcal{E}$ the support of $\mathcal{Q}$.
Also, we have to consider the variation of 2 over the support $\mathcal{E}$
with

$1/\phi\leq\max_{(x,y)\in
S\in\mathcal{E}}\mathcal{D}(x)/\mathcal{D}(y)\leq\phi\,,$

for some constant $\phi$. We remark that the learning results of [SBB+16] hold
for $k=O(1)$. Similar, our learning tools which are modifications of the work
of [SBB+16] hold for the same regime.

###  G.2 Learning Phase for Hypergraphs

As in the learning phase of the $2$-set case, the learning algorithm for the
$k$-set problem is essentially a variation of the analysis of [SBB+16], but
the steps are similar. Consider $N$ i.i.d. samples $(S_{i},\bm{v}_{i})$ drawn
from the sampling oracle $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$ with
natural parameter vector $\bm{z}^{\star}\in\mathbb{R}^{n}$. The analysis that
follows assumes that any $k$-set sample in the empirical likelihood lies in
$\mathcal{E}$, i.e., the support of $\mathcal{Q}$. Our goal is to estimate the
true parameter vector. We consider the negative empirical log-likelihood
objective

$L_{N}(\bm{z};\\{S_{i},\bm{v}_{i}\\}_{i\in[N]})=-\frac{1}{N}\sum_{i=1}^{N}\langle\bm{z},\bm{v}_{i}\rangle-\log\sum_{j\in
S_{i}}\exp(z_{j})\,,$

and we optimize it over the parameter space

$\Omega_{\phi}=\\{\bm{z}\in\mathbb{R}^{n}:\langle\bm{1},\bm{z}\rangle=0,~{}\max_{(x,y)\in
S\in\mathcal{E}}|z_{x}-z_{y}|\leq\log(\phi)\\}\,.$

##### Likelihood Objective and PL model.

We now observe that the above likelihood objective is directly connected to
the Plackett-Luce model, which captures the process of choosing a single
alternative from a given set, i.e., given a set $S$ of $m$ alternatives with
values $w_{1},\ldots,w_{m}$, the likelihood of choosing the $i$-th item is

$F(w_{i},w_{1},...,w_{i-1},w_{i+1},...,w_{m})=\exp(w_{i})/\sum_{j=1}^{m}\exp(w_{j})\,.$

Note that the negative log-likelihood of the Plackett-Luce model is exactly
the same as the single sample version of our objective function. Observe that
this function is shift-invariant and its value is independent of the ordering
of the last $(m-1)$ elements. Shift invariance is crucial: if one does not
work in the subspace $\\{\bm{z}:\langle\bm{1},\bm{z}\rangle=0\\}$, then
neither our problem nor the problem of determining the values of the
alternatives in the Plackett-Luce model are identifiable, since any solution
of the form $\bm{z}^{\star}+c\bm{1}$ is valid. Technically, shift invariance
implies that $\bm{1}$ lies in the nullspace of the Hessian of the negative
log-likelihood (and this is where the first constraint of the set
$\Omega_{\phi}$ arises).

##### Hessian matrix.

Let us introduce the vector $\bm{e}^{z}(S)=(\exp(z_{i}))_{i\in
S}\in\mathbb{R}^{k}$ for an arbitrary set $S\subseteq\binom{[n]}{k}$. After
standard computations (see also [SBB+16]), we get that

$\nabla^{2}_{\bm{z}}\Big{(}-\langle\bm{z},\bm{v}\rangle+\log\sum_{j\in
S}\exp(z_{j})\Big{)}=\frac{\Big{(}\sum_{j\in
S}\exp(z_{j})\Big{)}\mathrm{diag}(\bm{e}^{z}(S))-\bm{e}^{z}(S)\bm{e}^{z}(S)^{T}}{\Big{(}\sum_{j\in
S}\exp(z_{j})\Big{)}^{2}}\,,$

and hence

$\nabla^{2}_{\bm{z}}L_{N}(\bm{z};\\{S_{i},\bm{v}_{i}\\}_{i\in[N]})=\frac{1}{N}\sum_{i=1}^{N}\frac{\langle\bm{e}^{z}(S),\bm{1}\rangle\mathrm{diag}(\bm{e}^{z}(S_{i}))-\bm{e}^{z}(S_{i})\bm{e}^{z}(S_{i})^{T}}{\Big{(}\langle\bm{e}^{z}(S_{i}),\bm{1}\rangle\Big{)}^{2}}\,.$

##### Quantitative Strong Convexity of PL model.

Consider an arbitrary direction $\bm{v}\in\mathbb{R}^{k}$. Without loss of
generality, assume that $S=[k]$. Then, it holds that

$\bm{v}^{T}\Big{(}\bm{e}^{z}(S)\bm{e}^{z}(S)^{T}\Big{)}\bm{v}=\sum_{i,j=1}^{k}v_{i}v_{j}\exp(z_{i}+z_{j})\leq\sum_{i=1}^{k}\exp(z_{i})\sum_{j=1}^{k}v_{j}^{2}\exp(z_{j})=\langle\bm{e}^{z}(S),\bm{1}\rangle\mathrm{diag}(\bm{e}^{z}(S))\,,$

using the Cauchy-Schwarz inequality, where equality holds if and only if
$\bm{v}\in\mathrm{span}(\bm{1})$. Hence, for the Plackett-Luce function
$F:\mathbb{R}^{k}\rightarrow\mathbb{R}$, we have that

$\lambda_{2}(-\log(F(\bm{w})))>0,~{}\text{ for any
}~{}\bm{w}\in\Omega_{\phi}\,.$

In order to quantify the strong convexity parameter, we will make use of the
second constraint. For the Plackett-Luce function $F$, we have that

$\nabla^{2}(-\log(F(\bm{w}))\succeq\bm{H}\,,$

for some $k\times k$ symmetric matrix $\bm{H}$ with $\lambda_{2}(\bm{H})>0.$
We can observe that the matrix

$\bm{H}=\beta(\phi)(\bm{I}-\bm{1}\bm{1}^{T})\,,$

where
$\beta(\phi)=\min_{\bm{z}\in\Omega_{\phi}}\lambda_{2}\left(\frac{\langle\bm{e}^{z}(S),\bm{1}\rangle\mathrm{diag}(\bm{e}^{z}(S))-\bm{e}^{z}(S)\bm{e}^{z}(S)^{T}}{\Big{(}\langle\bm{e}^{z}(S),\bm{1}\rangle\Big{)}^{2}}\right)$,
satisfies the strong log-concavity condition for the Plackett-Luce model,
i.e., the function $F:\mathbb{R}^{k}\rightarrow\mathbb{R}$.

##### Underlying Laplacian matrix and estimation.

Similarly to the case $k=2$, our goal is to establish strong convexity for the
empirical negative log-likelihood around the true parameters
$\bm{z}^{\star}\in\Omega_{\phi}$ with respect to the $\bm{L}$ semi-norm.
Hence, we have to first introduce the appropriate Laplacian matrix $\bm{L}$.
In the $k$-set setting, we have that

$\bm{Q}_{x,y}=-\sum_{S\ni x,y}\mathcal{Q}(S)\text{ for
any}~{}x,y\in[n],~{}\bm{Q}_{x,x}=(k-1)\sum_{S\ni x}\mathcal{Q}(S)\text{ for
any}~{}x\in[n]\,.$

Observe that $\bm{Q}\bm{1}=0$ (since each set $S\subseteq\binom{[n]}{k}$ that
contains $x$, also contains other $k-1$ elements). Recall that for the case
$k=2$, the estimate for the Laplacian matrix $\bm{Q}$ is given by the
empirical matrix
$\bm{L}=\frac{1}{N}\sum_{i=1}^{N}\bm{v}_{i}\bm{v}_{i}^{T}=\frac{1}{N}\bm{X}^{T}\bm{X}$
(see Section F.1). In the case $k>2$ case, the Laplacian estimate for the
matrix $\bm{Q}$ is given by the $n\times n$ matrix

$\bm{L}=\frac{1}{N}\sum_{i=1}^{N}\bm{E}_{i}(k\bm{I}-\bm{1}\bm{1}^{T})\bm{E}_{i}^{T}\,,$

where the vectors $\bm{v}_{i}$ are substituted by the $(n\times k)$ matrices
$\bm{E}_{i}$, where each one of the $k$ columns of $\bm{E}_{i}$ is a unit
vector. The $k$ non-zero elements of $\bm{E}_{i}$ correspond to the $k$
elements that lie in the $i$-th drawn set $S_{i}$, i.e.,
$\bm{E}_{i}=\Big{[}\bm{e}_{i_{1}}\Big{|}\bm{e}_{i_{2}}\Big{|}\ldots\Big{|}\bm{e}_{i_{k}}\Big{]}$
for $S_{i}=\\{i_{1},i_{2},\ldots,i_{k}\\}.$

In the estimation part111111Recall that the learning algorithm does not
require the knowledge of the Laplacian matrix $\bm{Q}$. The concentration
result for the empirical estimation of the matrix $\bm{Q}$ using the matrix
$\bm{L}$ enables us to express our sample complexity results using the second
smallest eigenvalue of the true (population) matrix $\bm{Q}$ and not its
empirical estimate., our goal is to estimate the unknown matrix $\bm{Q}$.
Using concentration results of the Fiedler eigenvalue of sums of Hermitian
matrices [Tro15], using $O(\log(n)/\lambda(\bm{Q}))$ samples, one can compute
an estimate $\bm{L}$ (that corresponds to the above empirical estimate) that
approximates the true $\lambda(\bm{Q})$ with $(1+\epsilon)$ multiplicative
error.

We have that

$\bm{L}=\frac{1}{N}\sum_{i=1}^{N}\bm{X}_{i}\,,$

where121212For instance, let $n=5,k=3$ and $S=\\{1,2,3\\}$.
We have that
$\bm{E}=[\bm{e}_{1}|\bm{e}_{2}|\bm{e}_{3}]=\begin{bmatrix}1&0&0\\\ 0&1&0\\\
0&0&1\\\ 0&0&0\\\ 0&0&0\end{bmatrix}$ and
$\bm{X}=\begin{bmatrix}2&-1&-1&0&0\\\ -1&2&-1&0&0\\\ -1&-1&2&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\end{bmatrix}$
$\bm{X}_{i}=\bm{E}_{i}(k\bm{I}-\bm{1}\bm{1}^{T})\bm{E}_{i}^{T}$, i.e., the
estimate $\bm{L}$ is a sum of independent Hermitian matrices with
$\lambda_{max}(\bm{X}_{i})=\Theta(k).$ Using Proposition 7 in a similar manner
as in Lemma 17, we get that

$\Pr_{\bm{X}_{1..m}\sim\mathcal{Q}^{\otimes
m}}\left[\lambda(\bm{L})\leq(1-\epsilon)\lambda(\bm{Q})\right]\leq
n\exp\left(-\epsilon^{2}m\frac{\lambda(\bm{Q})}{2k}\right)\,.$

Hence, it suffices to draw at least

$m=O\left(\frac{k}{\epsilon^{2}\cdot\lambda(\bm{Q})}\log(n/\delta)\right)$

in order to guarantee the desired concentration bound with confidence at least
$1-\delta$.

##### Strong Convexity of Empirical NLL w.r.t. $\|\cdot\|_{L}$.

Having introduced the empirical Laplacian matrix, we are able to get the
desired strong convexity result for the empirical negative log-likelihood with
respect to the $\bm{L}$ semi-norm. Following the analysis of [SBB+16], we get
that, for any vector $\bm{w}\in\mathbb{R}^{d}$ and parameter
$\bm{z}\in\Omega_{\phi}$,

$\bm{w}^{T}\nabla^{2}L_{N}(\bm{z})\bm{w}\geq\frac{\lambda_{2}(\bm{H})}{k}\frac{1}{N}\sum_{i=1}^{N}\sum_{j=1}^{k}\bm{1}\\{\bm{v}_{i}=\bm{e}_{j}\\}\bm{w}^{T}\bm{E}_{i}(k\bm{I}-\bm{1}\bm{1}^{T})\bm{E}_{i}^{T}\bm{w}\,,$

where $\bm{H}=\beta(\phi)(\bm{I}-\bm{1}\bm{1}^{T})$. Hence, we get that

$\bm{w}^{T}\nabla^{2}L_{N}(\bm{z})\bm{w}\geq\frac{\lambda_{2}(\beta(\phi)(\bm{I}-\bm{1}\bm{1}^{T}))}{k}\|\bm{w}\|_{L}^{2}\,.$

Note that $\lambda_{2}(\bm{I}-\bm{1}\bm{1}^{T})=1$. 131313The characteristic
polynomial of $\bm{A}=\bm{I}-\bm{1}\bm{1}^{T}$ is
$\det(\bm{A}-\lambda\bm{I})=(\lambda-1)^{n-1}(\lambda+n-1).$ Consequently, the
empirical negative log-likelihood is $\beta(\phi)/k$-strongly convex around
the true parameters $\bm{z}^{\star}\in\Omega_{\phi}.$ Using 3, we get that

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}\leq\frac{k^{2}}{\beta(\phi)^{2}}\|\nabla
L_{N}(\bm{z}^{\star})\|_{L^{\dagger}}^{2}\,.$

##### Bounding the (expected) dual norm $\|\cdot\|_{L^{\dagger}}$.

Following the exact analysis of [SBB+16] for the expected value of the dual
norm, we get that for our setting

$\mathbb{E}\Big{[}\langle\nabla L_{N}(\bm{z}^{\star}),\bm{L}^{\dagger}\nabla
L_{N}(\bm{z}^{\star})\rangle\Big{]}\leq\frac{n}{N}\sup_{\bm{z}\in\mathbb{R}^{k}:|z_{x}-z_{y}|\leq\log(\phi)}\|\nabla\log
F(\bm{z})\|_{2}^{2}\,,$

where $F$ is the Plackett-Luce function and assuming that $S=[k]$ (and $S$
satisfies the modified mass condition, i.e., $S$ lies in the support of
$\mathcal{Q}$). We have that

$\nabla_{\bm{z}}\log
F(\bm{z})=\bm{e}_{i}-\frac{(\exp(z_{1}),...,\exp(z_{k}))^{T}}{\sum_{j\in[k]}\exp(\bm{z}_{j})}\,,$

for some $i\in[k]$. Hence, we get that

$\|\nabla_{\bm{z}}\log
F(\bm{z})\|_{2}^{2}=\left(1-\frac{e^{z_{i}}}{\sum_{j\in[k]}e^{z_{i}}}\right)^{2}+\frac{\sum_{j\in[k]\setminus\\{i\\}}e^{2z_{j}}}{(\sum_{j\in[k]}e^{z_{j}})^{2}}=\frac{(\sum_{j\in[k]\setminus\\{i\\}}\exp(z_{j}))^{2}+\sum_{j\in[k]\setminus\\{i\\}}\exp(2z_{j})}{(\sum_{j\in[k]}\exp(z_{j}))^{2}}$

Over the optimization space $\Omega_{\phi}$ and since the natural parameters
$\bm{z}_{x}=\log(\mathcal{D}(x))\leq 0$, we have that

$\frac{1}{k\phi}\leq\frac{\mathcal{D}(x)}{k\max_{j\in
S}\mathcal{D}(j)}\leq\frac{\mathcal{D}(x)}{\sum_{j\in
S=[k]}\mathcal{D}(j)}\leq\frac{\mathcal{D}(x)}{k\min_{j\in
S}\mathcal{D}(j)}\leq\phi/k$

Hence, we have that

$\left(\frac{\sum_{j\in[k]\setminus\\{i\\}}\mathcal{D}(j)}{\sum_{j\in[k]}\mathcal{D}(j)}\right)^{2}\leq((1-1/k)\phi)^{2}\,,$

and

$\frac{\sum_{j\in[k]\setminus\\{i\\}}\mathcal{D}(j)^{2}}{(\sum_{j\in[k]}\mathcal{D}(j))^{2}}=\sum_{j\in[k]\setminus\\{i\\}}\frac{\mathcal{D}(j)}{\sum_{j^{\prime}\in[k]}\mathcal{D}(j^{\prime})}\frac{\mathcal{D}(j)}{\sum_{j^{\prime}\in[k]}\mathcal{D}(j^{\prime})}\leq(k-1)\frac{\phi^{2}}{k^{2}}\,.$

Finally, we get that

$\|\nabla_{\bm{z}}\log F(\bm{z})\|_{2}^{2}\leq\phi^{2}\frac{k-1}{k}\,.$

##### Conclusion of the Learning Phase in $k$-sets.

We get that we can estimate the true parameters in $\bm{L}$ semi-norm, i.e.,

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{L}^{2}\leq\frac{k^{2}}{\beta(\phi)^{2}}\frac{n}{N}\phi^{2}\frac{k-1}{k}.$

Hence, we can transfer this result to an $L_{2}$ bound and get

$\|\bm{z}^{\star}-\widehat{\bm{z}}\|_{2}^{2}\leq\frac{k^{2}}{\beta(\phi)^{2}}\frac{n}{N\lambda_{2}(\bm{L})}\phi^{2}\frac{k-1}{k}.$

Using
$N=O\Big{(}\frac{nk^{2}}{\lambda_{2}(\bm{L})\beta(\phi)^{2}}\cdot\frac{1}{\epsilon^{2}}\Big{)}=_{\epsilon}O\Big{(}\frac{nk^{2}}{\lambda(\bm{Q})\beta(\phi)^{2}}\cdot\frac{1}{\epsilon^{2}}\Big{)}$
samples from the oracle $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$ on the
support set $\mathcal{E}$, we can learn the parameter vector in $L_{2}$. At
this point, the proof of the learning phase is similar to the $k=2$ case: We
can apply the trick of Section F.2 and get an $L_{\infty}$ bound. Hence, using
Lemma 18, we can estimate the target distribution with relative error.

###  G.3 Downscaling Phase for Hypergraphs

Let $\widehat{\bm{z}}$ be the estimate of the natural parameters vector and
let $\widetilde{\mathcal{D}}$ the correspond distribution. We use the estimate
$\widetilde{\mathcal{D}}$ of the target distribution $\mathcal{D}$ to
transform the Markov chain of the $k$-set Local Sampling Scheme into another
almost uniform stationary distribution, as in the case $k=2$. Using the
Bernoulli downscaling mechanism, for the pair $(x,y)$, we have that

$\widetilde{p}_{xy}=\mathcal{D}(y)\frac{\widetilde{\mathcal{D}}(x)}{\widetilde{\mathcal{D}}(y)}\sum_{S\ni
x,y}\frac{\mathcal{Q}(S)}{\mathcal{D}(S)}\approx\mathcal{D}(x)\sum_{S\ni
x,y}\frac{\mathcal{Q}(S)}{\mathcal{D}(S)}=p_{yx}\,.$

We have that

$\frac{\widetilde{p}_{xy}}{\widetilde{p}_{yx}}=\frac{\mathcal{D}(y)\frac{\widetilde{\mathcal{D}}(x)}{\widetilde{\mathcal{D}}(y)}\sum_{S\ni
x,y}\frac{\mathcal{Q}(S)}{\mathcal{D}(S)}}{\mathcal{D}(x)\sum_{S\ni
x,y}\frac{\mathcal{Q}(S)}{\mathcal{D}(S)}}=\frac{\mathcal{D}(y)/\widetilde{\mathcal{D}}(y)}{\mathcal{D}(x)/\widetilde{\mathcal{D}}(x)}\,.$

The modified transition matrix (as in the $k=2$ case) has an almost uniform
stationary distribution. Also, it has an absolute spectral gap of same order
as the matrix $\widetilde{\bm{P}}$ that can be expressed as

$\widetilde{\bm{P}}_{xy}=\Big{(}\frac{1}{2}+\epsilon_{xy}\Big{)}\sum_{S\ni
x,y}\mathcal{Q}(S)\,,~{}~{}\widetilde{\bm{P}}_{yx}=\Big{(}\frac{1}{2}+\epsilon_{yx}\Big{)}\sum_{S\ni
x,y}\mathcal{Q}(S)\,,$

and $\widetilde{\bm{P}}_{xx}=1-\sum_{y\neq x}\widetilde{\bm{P}}_{xy}$. Hence,
we get that

$\widetilde{\bm{P}}=\bm{I}-\frac{1}{2}\bm{Q}+\bm{Q}\circ[\epsilon_{xy}]\,.$

The expression of the modified transition matrix $\widetilde{\bm{P}}$ is
exactly similar to the $k=2$ case (see Equation (D.2)). Spectral analysis as
in Lemma 15 of this matrix will result to the following properties:

  * $(i)$

The transition matrix $\widetilde{\bm{P}}$ has stationary distribution
$\widetilde{\pi}_{0}(x)=\Theta(1/n)$ for all $x\in[n]$, i.e., an _almost_
uniform probability measure.

  * $(ii)$

The absolute spectral gap $\Gamma(\widetilde{\bm{P}})$ of $\widetilde{\bm{P}}$
and the minimum non-zero eigenvalue $\lambda(\bm{Q})$ of the Laplacian matrix
$\bm{Q}$ satisfy $\Gamma(\widetilde{\bm{P}})=\Omega(\lambda(\bm{Q}))$.

  * $(iii)$

The mixing time of the transition matrix $\widetilde{\bm{P}}$ is
$T_{\mathrm{mix}}(\widetilde{\bm{P}};1/4)=O(\log(n)/\lambda(\bm{Q})),$ where
$\lambda(\bm{Q})$ is the minimum non-zero eigenvalue of the Laplacian matrix
$\bm{Q}$.

###  G.4 CFTP Phase for Hypergraphs

The structure of the $k$-set algorithm remains similar to the $k=2$ case, with
the exception that the drawn samples are now hyperedges. We continue with the
modified Algorithm 7. Recall that, for each drawn sample
$(S,\bm{v})\sim\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$, the vector
$\bm{v}\in\\{\bm{e}_{1},...,\bm{e}_{n}\\}$ is the indicator vector of the
winning node of the set $S\subseteq\binom{[n]}{k}$.

Algorithm 7 Exact Sampling from $k$-set Local Sampling Schemes

1:procedure ExactSampler-$k$-Set($\bm{p}$) $\triangleright$ _Sample access to
the LSS oracle $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$._

2: $t\leftarrow 0$

3: $F_{0}(x)\leftarrow x$, for any $x\in[n]$

4: $\textbf{while}~{}F_{t}~{}\text{has not coalesced}~{}\textbf{do}$
$\triangleright$ _While no coalescence has occured._

5: $~{}~{}~{}~{}~{}~{}~{}~{}t\leftarrow t-1$

6: Draw $(S,\bm{v})$ where $S\in\mathcal{E}$ and $\bm{v}=\bm{e}_{i}$ for some
$i\in[n]$

7: $y\leftarrow$ position where $\bm{v}[y]=1$ $\triangleright$ _Find the
winning node $y\in S$._

8: for $x=1\ldots n$ do $\triangleright$ _In order to update state $x$._

9: if $x\notin S~{}\mathrm{or}~{}x=y$ then $F_{t}(x)\leftarrow F_{t+1}(x)$

10: else
$F_{t}(x)\leftarrow\left\\{\begin{array}[]{lr}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}F_{t+1}(w),&\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\text{with
probability
}\min\\{p(x)/p(w),1\\}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\\\
\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}F_{t+1}(x),&\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\text{otherwise
}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color<EMAIL_ADDRESS>
11: end

12: end

13: Draw $C\sim\mathrm{Be}(p(F_{t}(1)))$ $\triangleright$ _$\mathrm{Be}(p)$ is
a $p$-biased Bernoulli coin._

14: if $C=1$ then Output $F_{t}(1)$ else Output $\perp$ $\triangleright$
_Output the perfect sample or reject._

15:

16:procedure ExactSampler-$k$-Set-WithLearning($\delta$) $\triangleright$ _The
algorithm of Corollary 21_.

17:
$\widetilde{\mathcal{D}}\leftarrow\textsc{Learn}(\epsilon:=1/\sqrt{n},\delta)$
$\triangleright$ _Learn $\mathcal{D}$ in relative error as in Section G.2_.

18: x $\leftarrow\perp$

19: while x $=\perp$ repeat

20: x $\leftarrow$ ExactSampler-$k$-Set$(\widetilde{\mathcal{D}})$

21: Output x

###  G.5 Conclusion

Let $N_{\mathrm{Learn}}$ and $N_{\mathrm{CFTP}}$ be the expected number of
samples required for a single execution of the learning algorithm for $k$-sets
and of the parameterized CFTP algorithm respectively (see Algorithm 7). Under
1 (for the distribution $\mathcal{Q}$ over hyperedges) and the modified
version of 2, the expected sample complexity of the generalized algorithm for
the $k$-set case is

$N_{\mathrm{Learn}}(\epsilon:=1/\sqrt{n})+\Theta(n)\cdot
N_{\mathrm{CFTP}}=O\left(\frac{n^{2}k^{2}}{\lambda(\bm{Q})\beta(\phi)^{2}}\right)\,.$

Note that $\beta(\phi)$ is constant under 2. As explained in [SBB+16], it is
natural to consider the regime where $k=O(1)$. In this regime, the learning
bounds match the CFTP dependence on $n$ under $\widetilde{O}$ notation.

######  Corollary 21 (Exact Sampling from $k$-Set LSS).

For any positive constant integer $k>2$, under 1 (for the distribution
$\mathcal{Q}$ over $k$-sets) and 2, there exists an algorithm (Algorithm 7)
that draws an expected number of
$\widetilde{O}\left(\frac{n^{2}k^{2}}{\lambda(\bm{Q})}\right)$ samples from a
$k$-Set Local Sampling Scheme $\mathrm{Samp}_{k}(\mathcal{Q};\mathcal{D})$,
and generates a sample distributed as in $\mathcal{D}$.


# Zero-Shot Monocular Motion Segmentation in the Wild by Combining Deep
Learning with Geometric Motion Model Fusion

Yuxiang Huang Yuhao Chen John Zelek
Vision and Image Processing Lab, University of Waterloo
Waterloo, ON, Canada
{yuxiang.huang, yuhao.chen1<EMAIL_ADDRESS>
###### Abstract

Detecting and segmenting moving objects from a moving monocular camera is
challenging in the presence of unknown camera motion, diverse object motions
and complex scene structures. Most existing methods rely on a single motion
cue to perform motion segmentation, which is usually insufficient when facing
different complex environments. While a few recent deep learning based methods
are able to combine multiple motion cues to achieve improved accuracy, they
depend heavily on vast datasets and extensive annotations, making them less
adaptable to new scenarios. To address these limitations, we propose a novel
monocular dense segmentation method that achieves state-of-the-art motion
segmentation results in a zero-shot manner. The proposed method
synergestically combines the strengths of deep learning and geometric model
fusion methods by performing geometric model fusion on object proposals.
Experiments show that our method achieves competitive results on several
motion segmentation datasets and even surpasses some state-of-the-art
supervised methods on certain benchmarks, while not being trained on any data.
We also present an ablation study to show the effectiveness of combining
different geometric models together for motion segmentation, highlighting the
value of our geometric model fusion strategy.

##  1 Introduction

Motion segmentation is a fundamental problem in computer vision. It has an
essential role in many applications such as action recognition, autonomous
navigation, object tracking, and scene understanding in general. The objective
of motion segmentation is to divide a video frame into regions segmented by
common motions. Motion segmentation becomes particularly challenging when
utilizing a single camera that is also moving, as this introduces issues such
as degenerate motions, motion parallax, motion on the epipolar plane [18].
Existing motion segmentation methods often fails when facing these challenges
since they usually rely on only a single motion cue [35, 49, 43, 11, 45, 53,
39, 16, 28], limiting their effectiveness across the diverse tapestry of real-
world environments. While a few deep learning based methods are able to
incorporate additional motion cues in an end-to-end manner, their reliance on
large annotated datasets and the need for substantial computational resources
for training limit their adaptability and application in novel environments
[36, 19]. When facing these challenges, existing methods usually fail to
detect the correct motion patterns and also fail to produce coherent
segmentation masks for the moving objects.

In order to overcome these limitations and achieve in-the-wild monocular
motion segmentation regardless of motion types and scene structures, it is
necessary to have a robust and comprehensive motion model. We draw inspiration
from two branches of well studied motion segmentation approaches: and point
trajectory based methods and optical flow based methods. These two types of
motion cues are not only complementary in nature (long-term vs short-term
motion), but they can also be used to derive highly complementary geometric
motion models for different motion types and scene structures. Point
trajectory based methods, when analyzed using epipolar geometry, will fail if
the motion is mainly on the epipolar plane or degenerate (e.g., pure forward
motion), but are robust to depth variations, perspective effects and motion
parallax. On the other hand, optical flow based methods do not handle these
challenges well, but are robust to motions on the epipolar plane. We propose
to combine these two motion cues and monocular depth information at the object
level using multi-view spectral clustering, to obtain a coherent and
comprehensive motion representation of the scene. By doing so, we are able to
distinguish a variety of complex object motions (e.g., degenerate motions,
motion parallax and non-rigid motion), even in complex scenes.

In addition to having a comprehensive geometric motion model for effectively
analysis of object motions, it is also essential to obtain accurate object
proposals for tracking potential moving objects throughout the video. This
step is not only fundamental for accurate assessment of object motion, but
also vital for generating precise and coherent segmentation masks for moving
objects. To accomplish this, we leverage the strong zero-shot ability of the
recent computer vision foundation models to identify, segment and track any
potential moving objects throughout the video. We then calculate pairwise
motion affinity scores for every object pair in the proposal, assessing how
well each object-specific motion cue fits its corresponding geometric motion
model. The motion affinity scores are used to construct motion affinity
matrices, which can be fused by multi-view spectral clustering techniques to
obtain the final clustering of objects in different motions

Figure 1: Motion segmentation results from the proposed method using different
motion cues on a scene with motion parallax and degeneracy. Motion cues used:
(a) point trajectory. (b) optical flow. (c) optical flow + depth. (d)
trajectory + optical flow + depth. Using a single motion cue is insufficient
to correctly segment out the moving cyclist.

Our method was evaluated on three benchmarks: DAVIS-Moving, YTVOS-Moving [11],
and an extended version of the KT3DMoSeg dataset we proposed. Our method
achieves competitive results on all benchmarks and even surpasses the state-
of-the-art supervised method on DAVIS-Moving.

##  2 Related Work

Research on monocular motion segmentation has been ongoing for several
decades, leading to varying interpretations of the problem among different
studies. Commonly, it is defined as the process of dividing a video frame into
regions that share similar motions. Alternatively, many studies also approach
motion segmentation as the task of clustering predefined feature point
trajectories across two or more video frames based on their distinct motions.
In this paper, we focus on performing motion segmentation directly from input
video frames, with the goal of segmenting entire moving objects, including
those exhibiting multiple rigid motions. This approach aims at attaining a
high-level understanding of the scene.

Monocular motion segmentation can be broadly divided into three distinct
categories, each defined by the type of motion cues utilized. The first group
consists of optical flow based methods, which rely on optical flow as their
primary source of motion information [45, 52, 39, 3, 49, 4, 46, 43, 11, 5, 35,
33]. The second group includes the feature point trajectory based methods,
which rely exclusively on motion information derived from manually corrected
feature point trajectories throughout the video [12, 24, 23, 7, 13, 37, 30,
55, 1]. The last category comprises fusion-based methods, which combine
multiple types of motion cues as well as appearance cues, to enhance the
segmentation results [36, 19, 22].

###  2.1 Optical Flow Based Methods

Optical flow based methods can be further categorized into traditional and
deep learning based methods. Traditional methods [45, 52, 39, 3] rely on
optical flow masks input, and produce a pixel-wise segmentation mask
indicating different motion groups. These methods usually adopt iterative
optimization approaches or statistical inference techniques to estimate the
motion models and motion regions simultaneously. In contrast, numerous deep
learning based methods [43, 14, 6, 8, 35] use a CNN encoder to extract motion
cues from optical flow and uses a decoder to produce the final segmentation.
More advanced deep learning models use two CNN encoders – one to extract
motion information from optical flow and the other one to extract appearance
features directly from the video frame – to enhance the segmentation
performance. However, deep learning methods often require a large amount of
training data and do not generalize well to novel scenes.

In general, optical flow based methods perform well on scenes without strong
depth variations or motion parallax. However, if the scene contains these
elements (e.g. road scenes), these methods will fail to distinguish if a part
of the image is moving independently or is just at a different depth from its
surroundings, because the motion flow vectors projected to a 2D image from the
3D space are determined by both the depth and the screw motion of the object
[34]. Additionally, strong brightness changes in the video will also adversely
affect the performance of optical flow based methods since optical flow
calculation is based on the brightness constancy constraint, which will be
violated under strong brightness change.

###  2.2 Point Trajectory Based Methods

In contrast to the other two categories, point trajectory based methods
produce clusters of key points that represent various motion patterns, rather
than providing full dense segmentations. These techniques can be further
divided into two-frame and multi-frame methods. Two frame methods [12, 24, 2]
usually determine motion parameters by solving an iterative energy
minimization problem of finding a certain number of geometric models (e.g.,
fundamental matrices) on a set of matched feature points, to minimize an
energy function that evaluates the quality of the overall clustering of
correspondences. Multi-frame based methods, on the other hand, usually analyze
manually adjusted trajectory points from a dense optical flow tracker and
often employ spectral clustering on affinity matrices. These matrices are
generated through geometric model fitting [30, 55, 1, 20, 21], subspace
fitting [13, 44, 48, 50], or pairwise motion affinities derived from spatio-
temporal motion cues and appearance cues [7, 37].

The efficacy of point trajectory based methods is heavily influenced by the
chosen motion model and the precision of point correspondences. There is not a
single motion model that can capture motion similarities across all types of
motions. In search of a better motion model, [1] uses trifocal tensor to
analyze point trajectories. Trifocal tensor is more robust to noises and is
able to distinguish motions on the epipolar plane, but it is harder to
optimize and prone to failure when the three cameras are close to being
colinear [18], which can often happen on road scenes. [55, 26] proposed
geometric model fusion techniques to combine different geometric models, but
they still fail to produce coherent and consistent segmentations on complex
scenes. Moreover, most existing methods depend on manually refined point
correspondences and struggle to effectively manage outliers.

Figure 2: Our Motion Segmentation Pipeline. Our method can be summarized to
three main steps: 1) given a sequence of video frames, we produce an object
proposal by automatically detecting, segmenting and tracking common objects in
the video. 2) we compute object-specific point trajectories, optical flow and
monocular depth maps for every frame. 3) we compute pairwise object motion
similarity scores using two motion models (one based on point trajectories and
the other based on optical flow and depth map), and use them to construct two
motion affinity matrices. The two matrices are fused using multi-view spectral
clustering to cluster objects into different motion groups.

###  2.3 Fusion Based Methods

Recent research in motion segmentation have introduced several innovative
approaches that leverage a combination of motion cues for improved motion
segmentation accuracy. Notably, [36] integrates optical flow masks and
monocular depth maps through a fusion module in their neural network,
facilitating end-to-end training. By adopting a semi-supervised training
strategy, this approach has set new benchmarks in monocular dense motion
segmentation across various datasets. Another study [19] explored the impact
of utilizing different combinations of motion cues, such as optical flow,
depth map, and scene flow, on motion segmentation performance, achieving
state-of-the-art results on the KITTI and DAVIS datasets. However, this
approach is fully supervised, which requires an extensive amount of training
data and computational power. Furthermore, its ability to generalize across a
wider range of benchmarks remains unverified. In our earlier work [22], we
introduced an interpretable geometric model that merges optical flow with
monocular depth maps for zero-shot motion segmentation. Despite these efforts,
a noticeable performance gap persists between our method and the state-of-the-
art supervised or semi-supervised techniques, showing the insufficiency of
relying solely on a single geometric model to achieve optimal results in
motion segmentation.

Despite these recent research, no existing method has yet to combine the two
complementary and most commonly explored motion cues in motion segmentation:
point trajectory and optical flow. This paper seeks to fill this gap,
demonstrating how combining these motion cues with well-crafted geometric
motion models can lead to state-of-the-art zero-shot monocular motion
segmentation.

##  3 Methodology

We propose a zero-shot monocular motion segmentation approach that uses both
object appearance information and a combination of epipolar geometry and
optical flow based geometric motion models to perform in-the-wild motion
segmentation without any assumptions of the motion or the scene that may
appear in the video.

Our segmentation pipeline begins by identifying initial segmentation of the
background and common objects within the scene through foundational models,
followed by continuous tracking of these objects across the video sequence.
For every object in each frame, we gather a collection of object-specific
trajectory points, an optical flow mask, and a monocular depth map.
Subsequently, we construct two distinct geometric motion models for each scene
object: one via fundamental matrix fitting using point trajectories and the
other via fitting optical flow and a depth map to our proposed parametric
equations. By fitting each object’s motion models on every other object and
analysing the residuals of the model fitting, we are able to derive two
pairwise affinity scores between every pair of objects, from which we can
construct two motion affinity matrices for the two types of motion models
respectively. Lastly, we fuse the two affinity matrices using co-regularized
multi-view spectral clustering to obtain the final segmentation. Figure 2
shows a diagram of the motion segmentation pipeline.

###  3.1 Generating Object Proposals

In order to identify all motions in a video sequence at object level, we use
the same method as proposed in [22] to identify, segment and track each
prominent object across the video. This is accomplished by integrating
foundation models for object recognition (RAM) [58], detection (Grounding DINO
model) [31], segmentation (SAM-HQ) [27], and tracking (DeAOT) [57]. This video
preprocessing pipeline for automatic object proposal generation is inspired by
and improved upon Segment and Track Anything (SAMTrack) [9]. Comparing to
SAMTrack, our video preprocessing module combines these foundation models to
segment and track objects automatically, bypassing the need for manual text
prompts by initiating our pipeline with the Recognize Anything Model to
automatically detect common objects in the initial video frame. Our object
proposal generation pipeline involves: 1) Automatically identifying common
objects in the video’s first frame using the Recognize Anything Model; 2)
Generating object bounding boxes with the Grounding DINO model; 3) Producing
instance segmentation masks for the initial frame via the SAM-HQ model,
applying non-max suppression to refine the results; 4) Employing the DeAOT
tracker to track each object’s segmentation mask throughout the video. To
accommodate new objects appearing mid-sequence, we segment the video into
sections of $l$ frames, repeating the above process for each section. The
choice of $l$ varies depending on the video’s dynamics and the frequency of
new objects entering the scene. Videos with higher dynamics and frequent entry
of new objects mid-sequence are better suited to a reduced segment length $l$.

###  3.2 Object-Specific Motion Cues

Once we have an object proposal for every frame of the video, we will then
obtain object-specific motion cues for every object in the object proposal. We
propose to use point trajectories, optical flow and monocular depth map
automatically generated by off-the-shelf networks as motion cues, in order to
model objects’ motions in two complementary ways.

####  3.2.1 Object-Specific Point Trajectories

A set of sparse point trajectories is generated for every object using PIPs
[17]. PIPs is a state-of-the-art point tracker which tracks individual pixels
given their initial locations in a video frame. A mixture of Shi-Tomasi [25]
and K-Medoids [40] sampling method is used to obtain the initial pixels from
each object as it showed good experimental results from previous works in
similar tasks [42]. These tracked pixels can be used as object-specific
feature points to fit fundamental matrices for every object in frame pairs to
describe their motions. One limitation of PIPs is that does not handle
occlusion well if the tracked video is more than 8 frames. To overcome this
issue, we check for every point if it is inside its corresponding object’s
mask area every 8 frames. If not, we remove that point and sample a new point
inside the object’s mask. We also remove any point that is near the edge of
the frame since the tracking accuracy of PIPs drops significantly in this
case.

Figure 3: Qualitative results of different methods on DAVIS-Moving (row 1, 2),
YTVOS-Moving (row 3, 4) and the extended KT3DMoSeg (row 5, 6) datasets. MoSeg
often mistakenly label static objects as dynamic when there is degenerate
camera motion. RigidMask fails to detect or coherently segment objects with
non-rigid motions. Similarly, Raptor also has these problems, although to a
lesser extent overall. Our method, despite being zero-shot, performs well when
facing these challenges.

####  3.2.2 Object-Specific Optical Flow and Depth Map

We also generate a dense optical flow mask and a monocular depth map for every
frame, from which we can extract object-specific optical flow vectors and
depth maps. We use a state-of-the-art optical flow estimator [47] to obtain
optical flow, and a state-of-the-art monocular depth estimator, DINOv2 [38],
to extract the depth maps. We use monocular depth estimation to estimate the
scene depth from a single frame since our goal is to perform motion
segmentation from a moving monocular camera. DINOv2 outputs a relative depth
map, which is sufficient for our application. Our experiment shows improved
results when both optical flow and depth map are used to compute the motion
model, comparing to only optical flow. We show how a depth map can be used to
improve the motion model based solely on optical flow in the next section.

Exp. |  Method |  Training | DAVIS-Moving | YTVOS-Moving | KT3DInsMoSeg
---|---|---|---|---|---
|  |  |  Pu |  Ru |  Fu |  Pu |  Ru |  Fu |  Pu |  Ru |  Fu
a |  MoSeg [11] |  Supervised |  78.30 |  78.80 |  78.10 |  74.50 |  66.40 |  66.38 |  63.73 |  78.24 |  66.85
a |  Raptor [36] |  Supervised Features |  75.90 |  79.67 |  75.93 |  64.43 |  60.94 |  60.35 |  71.52 |  88.27 |  75.82
a |  RigidMask [56] |  |  59.03 |  49.89 |  50.01 |  29.88 |  17.88 |  18.70 |  65.14 |  83.34 |  70.91
a |  EM [33] |  Unsupervised |  58.42 |  83.48 |  64.24 |  44.52 |  40.33 |  37.12 |  42.85 |  58.71 |  44.03
a+b |  Ours (fused) |  Zero-Shot (no training) |  78.27 |  81.58 |  79.40 |  64.12 |  61.10 |  60.62 |  72.93 |  71.02 |  71.89
b |  Ours (OC+depth) |  |  71.53 |  75.66 |  73.18 |  63.54 |  58.94 |  56.06 |  48.04 |  61.54 |  49.26
b |  Ours (OC) |  |  58.25 |  59.22 |  57.08 |  61.79 |  54.64 |  53.74 |  36.44 |  39.97 |  34.78
b |  Ours (trajs) |  |  65.99 |  75.51 |  68.47 |  54.67 |  52.92 |  50.05 |  42.31 |  73.66 |  45.24
b |  Ours (base) |  |  43.17 |  86.24 |  52.12 |  48.49 |  73.01 |  50.82 |  38.97 |  70.97 |  43.37
Table 1: Performance of our method and state-of-the-art motion segmentation
methods (Exp. a) on the DAVIS-Moving, YTVOS-Moving validation datasets and the
KT3DInsMoSeg dataset, as well as ablation study results (Exp. b). The best
result for each metric is in bold and the second best result is in underscore.
Our method overall performs the best on DAVIS-Moving and second best on both
YTVOS and KT3DInsMoSeg, despite not being trained on any data. Our method also
significantly surpasses the state-of-the-art unsupervised motion segmentation
method [33].

###  3.3 Geometric Motion Model Fitting

After obtaining object-specific point trajectories, optical flow vectors and
depth maps, for each frame pair, we compute two geometric motion models of
each object based on epipolar geometry and optical flow respectively, to model
its motion throughout the video. To compute the epipolar geometry based motion
models using point trajectories, we compute a fundamental matrix of each
object between every f frames by solving ${p^{\prime}TFp=0}$ using the eight-
point algorithm with RANSAC [15], where $p$ and $p^{\prime}$ are the
normalized 2D homogeneous coordinates of the same tracked point in the two
frames. If a degenerate case is encountered for the fundamental matrix, we do
not use it.

For the optical flow and depth based motion model, we use the same motion
model proposed in our earlier work [22]. We refine the Longuet-Higgins and
Pruzdny model equation [32] to address rigid object motion, adapting it to
include depth information without needing exact pixel depth, a common
limitation in practice. Instead of relying on the original model, which is
impractical due to unknown absolute pixel depth, we propose a linearized
version incorporating relative depth from DINOv2, making it more applicable to
real-world scenarios with varying depths. This approach, while using both
optical flow and depth data, simplifies the motion model to the following
linear equations:

$\begin{split}u=a+b\frac{1}{z}-c\frac{x}{z}-dy+ex^{2}-fxy\\\\[4.30554pt]
v=g+h\frac{1}{z}-c\frac{y}{z}-dx+exy+fy^{2}\end{split}$ (1)

This motion model aims to cluster different motions rather than calculate
exact screw motions, sidestepping scale uncertainties and making it
theoretically sound without requiring specific camera intrinsics. For
consistency reasons, we still refer to this motion model as the ”optical flow
motion model”, although it uses both optical flow vectors and pixel depth
maps.

###  3.4 Constructing Motion Affinity Matrices

After all fundamental matrices and optical flow motion models are computed,
each object will have a fundamental matrix between every $p$ frames and an
optical flow motion model between every two frames. By fitting every object’s
trajectory points, optical flow vectors and depth maps to every other object’s
fundamental matrix and optical flow motion model on the same frame pair, we
can obtain the residuals of every object to all other objects’ motion models
respectively. We use Sampson distance [18] as the residual for the fundamental
matrix and mean squared error for the optical flow motion model. Assuming
there are k objects in the scene, for the i-th object at the m-th frame pair,
we obtain the following residual vectors under the fundamental matrix and
optical flow motion models:

$\begin{split}{\boldsymbol{r}_{o}}_{i}^{m}=[{r_{o}}_{i,1}^{m},{r_{o}}_{i,2}^{m},...,{r_{o}}_{i,k}^{m}],\\\
{\boldsymbol{r}_{f}}_{i}^{m}=[{r_{f}}_{i,1}^{m},{r_{f}}_{i,2}^{m},...,{r_{f}}_{i,k}^{m}]\end{split}$

where ${r_{o}}_{i,k}^{m}$ is the mean residual for fitting the parametric
motion model of object $i$ on the optical flow vectors of object $k$ between
frames $m$ and $m+1$, and ${r_{f}}_{i,k}^{m}$ is the mean Sampson error for
fitting the fundamental matrix of object $i$ on the trajectory points of
object $k$ between frames $m$ and $m+p$. We construct two affinity matrices
encapsulating the pairwise motion affinities between each pair of objects
using a modified version of ordered residual kernal (ORK) [10]. Specifically,
for each object, we sort its residual vectors in ascending order and define a
threshold to select the smallest t-th residual as inliers. We define
${\boldsymbol{c}_{i}}=\\{0,max(t-n_{i},0)\\}^{K}$ as an inlier score vector,
where $n_{i}$ is the rank of object $k$ in the residual vector of object $i$,
penalizing different inlier distributions between objects. The pairwise motion
affinity between objects $i$ and $j$ can thus be computed as
${\boldsymbol{a}_{ij}=\boldsymbol{c}_{i}^{\intercal}\boldsymbol{c}_{j}}$,
which denotes a weighted co-occurrence score between two objects as inliers of
all motion models. Our proposed weighted ORK is robust to outliers and makes
the affinity matrix more adaptive to different scenes by reducing the need to
set scene specific inlier thresholds.

###  3.5 Co-Regularized Multi-view Spectral Clustering

After constructing the affinity matrices, we normalize them using row
normalization [51] and adapt co-regularized multi-view spectral clustering
[29] to fuse the two affinity matrices together. With the number of motion
groups in the scene given as an input, we are able to obtain the final
clustering of moving objects. Co-regularized multi-view spectral clustering
uses an regularization term to encourage consensus between different views and
is shown to perform well on fusing multiple geometric models for a consistent
representation of motion information [55].

##  4 Experiments

Our method is tested on three benchmarks: DAVIS-Moving, YTVOS-Moving and the
extended KT3DMoSeg. We first briefly introduce these datasets, then show both
quantitative and qualitative comparisons between our method and other state-
of-the-art methods. Lastly, we present an ablation study to compare the
performance of each individual motion models and the fused motion model.

###  4.1 Datasets

DAVIS-Moving and YTVOS-Moving are both proposed by [11] as datasets for
generic instance motion detection and segmentation. DAVIS-Moving and YTVOS-
Moving are subsets of the DAVIS 17 dataset [41] and the YTVOS dataset [54],
where all moving instances in the video sequence are labeled and no static
objects are labeled. These two recently proposed datasets are very challenging
due to their diverse object classes, occlusions and non-rigid motions.

In addition to these two datasets, we also evaluate our method on an extended
version of the KT3DMoSeg dataset. The original KT3DMoSeg dataset [55] is
designed to test point trajectory based motion segmentation methods on complex
road scenes. It contains manually corrected point trajectories on selected
moving instances in road scenes and includes significant degenerate motions
and depth variation. In order to test the performance of our method in such
environments, we extend the KT3DMoSeg dataset by adding a pixel-level
segmentation mask to every moving instance in the scene. We refer to this
extended dataset as the KT3DInsMoSeg dataset in the following sections.

###  4.2 Results and Discussion

Our method’s performance is evaluated using precision (Pu), recall (Ru), and
F-measure (Fu) proposed in [11] which penalizes false positives. The F-measure
combines both precision and recall and indicates the method’s overall
performance. Table 1 shows quantitative results of our method and other state-
of-the-art methods on the three benchmarks. Despite no training, our approach
excels on the DAVIS-Moving dataset, outperforming fully-supervised methods,
ranks second on the YTVOS-Moving dataset, closely surpassing Raptor [36], and
secures a similar position on the KT3DInsMoSeg dataset, trailing only behind
Raptor. Our method also significantly surpasses EM [33], which is the state-
of-the-art unsupervised multi-label motion segmentation method.

We also qualitatively compare our method with these methods and show the
results in 3. Results indicate our method’s superiority in identifying static
and moving objects across various scenes, notably in complex scenarios where
other methods fail, such as in scenes with degenerate motions or complex
object contours. Our technique demonstrates robust performance across all
datasets, showing its effectiveness in accurately grouping motions and
outperforming existing methods in challenging conditions.

One primary limitation of the proposed method is its inference speed. Despite
being a zero-shot approach that requires no training, the method integrates
multiple computer vision foundation models, as well as the neural networks for
feature point tracking and optical flow estimation. Consequently, such
integration significantly slows the method’s processing speed, making it only
suitable to be applied on pre-recorded videos. Another limitation is the
requirement for a known ground truth number of motions in the scene to achieve
optimal results, inherent to the use of spectral clustering. Although this
issue can be mitigated by employing various model selection methods [21, 51],
such adjustments typically result in a slight degradation of performance.

Figure 4: Qualitative comparison of different motion models on different
scenes. Pure optical flow based motion model (OC) suffers on scenes with
objects at varying depths. Combining optical flow with depth information (OC +
Depth) only alleviates this problem to some extent. Pure point trajectory
based motion model (Trajs) suffers from motions near the epipolar plane and
inaccurate trajectory estimation. Motion model fusion solves these problem by
combining the advantages of both motion models and outperforms any single
model.

###  4.3 Ablation Study

We present both quantitative (Table 1, Exp. b) and qualitative (Figure. 4)
comparisons between different individual motions models and the fused motion
model for their performances on the three benchmarks.

We found that on both DAVIS-Moving and KT3DInsMoSeg datasets, our model fusion
technique (fused) is able to significantly boost the Fu score comparing to
using only a single model, while on YTVOS-Moving, the Fu score only had a
relatively small increase. Upon further inspection, we discovered this could
be attributed to some motion labels in the YTVOS-Moving dataset actually being
mostly static throughout the video sequence. Since our method clusters moving
objects purely using motion cues, it groups these objects together with the
background as expected. Additionally, the YTVOS-Moving dataset also contains
videos with significant camera zooming, which violates the geometric
assumptions of both our motion models. Our motion model fusion technique is
able to achieve better results than any single motion model on all three
datasets, showing its effectiveness.

We also show the motion segmentation performance of our pipeline under
conditions where only partial motion cues are used. Specifically, we present
results obtained from two different types motion affinity matrices, which are
computed using two different motion models: one solely based on the optical
flow motion model (OC), and another that combines optical flow with monocular
depth information (OC + depth). The optical flow based motion model is
obtained from [33], which is a state-of-the-art unsupervised method using only
optical flow as input. The motion model combining optical flow and depth is
proposed by [22], which is a direct improvement on [33]. Results show that the
motion model based on a combination of optical flow and depth (OC + depth)
outperforms OC by a large margin in all three metrics on both DAVIS-Moving and
KT3DInsMoSeg, while having similar results on YTVOS-Moving.

Both Point trajectory based (trajs) and optical flow based motion models
perform poorly on the KT3DInsMoSeg dataset, potentially due to significant
motion degeneracy (e.g., forward motion) and depth variations on road scenes.
Incorporating depth information in this case proves to be an effective way to
reduce motion ambiguity for the optical flow based motion model, boosting its
F-score from 34.78% to 49.26%. Fusing the combined (OC + depth) motion model
with the epipolar geometry based point trajectory motion model significantly
enhances the performance in this case.

##  5 Conclusion and Future Work

We propose the first zero-shot monocular motion segmentation approach that
achieves state-of-the-art performance. Our method combines the advantages of
both deep learning and multiple geometric approaches, resulting in a zero-shot
motion segmentation approach that performs geometric motion model fusion on
object proposals. We compare the performances of the fused motion model and
each individual motion model, and observe a significant performance
improvement for the fused motion model, showing the effectiveness of the
proposed geometric motion model fusion technique. Even though our method is
zero-shot, experiments show that our method is better than many state-of-the-
art methods and highly competitive with others.

Future research could pursue two promising directions: First, the integration
of additional motion models, such as the trifocal tensor [18], may further
improve the motion segmentation performance. Second, developing methods to
effectively incorporate both types of motion affinity measures into the loss
function could enable end-to-end, self-supervised training of a motion
segmentation network, potentially achieving substantial improvement in
inference speed.

## References

  * Arrigoni et al. [2020] Federica Arrigoni, Luca Magri, and Tomas Pajdla.  On the Usage of the Trifocal Tensor in Motion Segmentation.  In _Computer Vision – ECCV 2020_ , pages 514–530. Springer International Publishing, Cham, 2020.  Series Title: Lecture Notes in Computer Science.
  * Barath and Matas [2019] Daniel Barath and Jiri Matas.  Progressive-X: Efficient, Anytime, Multi-Model Fitting Algorithm.  In _2019 IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 3779–3787, Seoul, Korea (South), 2019. IEEE.
  * Bideau and Learned-Miller [2016] Pia Bideau and Erik Learned-Miller.  It’s Moving! A Probabilistic Model for Causal Motion Segmentation in Moving Camera Videos.  In _Computer Vision – ECCV 2016_ , pages 433–449. Springer International Publishing, Cham, 2016.  Series Title: Lecture Notes in Computer Science.
  * Bideau et al. [2018] Pia Bideau, Aruni RoyChowdhury, Rakesh R. Menon, and Erik Learned-Miller.  The Best of Both Worlds: Combining CNNs and Geometric Constraints for Hierarchical Motion Segmentation.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 508–517, Salt Lake City, UT, USA, 2018. IEEE.
  * Bideau et al. [2019] Pia Bideau, Rakesh R. Menon, and Erik Learned-Miller.  MoA-Net: Self-supervised Motion Segmentation.  In _Computer Vision – ECCV 2018 Workshops_ , pages 715–730. Springer International Publishing, Cham, 2019.  Series Title: Lecture Notes in Computer Science.
  * Bosch [2021] Markus Bosch.  Deep Learning for Robust Motion Segmentation with Non-Static Cameras, 2021.  arXiv:2102.10929 [cs].
  * Brox and Malik [2010] Thomas Brox and Jitendra Malik.  Object segmentation by long term analysis of point trajectories.  In _Proceedings of the 11th European conference on Computer vision: Part V_ , pages 282–295, Berlin, Heidelberg, 2010. Springer-Verlag.
  * Cao et al. [2019] Zhe Cao, Abhishek Kar, Christian Hane, and Jitendra Malik.  Learning Independent Object Motion From Unlabelled Stereoscopic Videos.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5587–5596, Long Beach, CA, USA, 2019. IEEE.
  * Cheng et al. [2023] Yangming Cheng, Liulei Li, Yuanyou Xu, Xiaodi Li, Zongxin Yang, Wenguan Wang, and Yi Yang.  Segment and Track Anything, 2023.  arXiv:2305.06558 [cs].
  * Chin et al. [2009] Tat-jun Chin, Hanzi Wang, and David Suter.  The Ordered Residual Kernel for Robust Motion Subspace Clustering.  In _Advances in Neural Information Processing Systems_. Curran Associates, Inc., 2009.
  * Dave et al. [2019] Achal Dave, Pavel Tokmakov, and Deva Ramanan.  Towards Segmenting Anything That Moves.  In _2019 IEEE/CVF International Conference on Computer Vision Workshop (ICCVW)_ , pages 1493–1502, Seoul, Korea (South), 2019. IEEE.
  * Delong et al. [2010] Andrew Delong, Anton Osokin, Hossam N. Isack, and Yuri Boykov.  Fast approximate energy minimization with label costs.  In _2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , pages 2173–2180, 2010.  ISSN: 1063-6919.
  * Elhamifar and Vidal [2013] E. Elhamifar and R. Vidal.  Sparse Subspace Clustering: Algorithm, Theory, and Applications.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 35(11):2765–2781, 2013.
  * Faisal et al. [2020] Muhammad Faisal, Ijaz Akhter, Mohsen Ali, and Richard Hartley.  EpO-Net: Exploiting Geometric Constraints on Dense Trajectories for Motion Saliency.  In _2020 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , pages 1873–1882, Snowmass Village, CO, USA, 2020. IEEE.
  * Fischler and Bolles [1981] Martin A. Fischler and Robert C. Bolles.  Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography.  _Communications of the ACM_ , 24(6):381–395, 1981.
  * Fragkiadaki et al. [2012] K. Fragkiadaki, Geng Zhang, and Jianbo Shi.  Video segmentation by tracing discontinuities in a trajectory embedding.  In _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1846–1853, Providence, RI, 2012. IEEE.
  * Harley et al. [2022] Adam W. Harley, Zhaoyuan Fang, and Katerina Fragkiadaki.  Particle Video Revisited: Tracking Through Occlusions Using Point Trajectories.  In _Computer Vision – ECCV 2022_ , pages 59–75. Springer Nature Switzerland, Cham, 2022.  Series Title: Lecture Notes in Computer Science.
  * Hartley and Zisserman [2004] R. I. Hartley and A. Zisserman.  _Multiple View Geometry in Computer Vision_.  Cambridge University Press, ISBN: 0521540518, second edition, 2004.
  * [19] Christian Homeyer and Christoph Schnorr.  On Moving Object Segmentation from Monocular Video with Transformers.
  * Huang and Zelek [2023a] Yuxiang Huang and John Zelek.  Motion Segmentation from a Moving Monocular Camera.  In _IROS 2023 Workshop on Robotic Perception and Mapping: Frontier Vision and Learning Techniques_. arXiv, 2023a.  arXiv:2309.13772 [cs].
  * Huang and Zelek [2023b] Yuxiang Huang and John Zelek.  A Unified Model Selection Technique for Spectral Clustering Based Motion Segmentation.  _Journal of Computational Vision and Imaging Systems_ , 9(1), 2023b.
  * Huang et al. [2024] Yuxiang Huang, Yuhao Chen, and John Zelek.  Dense Monocular Motion Segmentation Using Optical Flow and Pseudo Depth Map: A Zero-Shot Approach.  In _21st Conference on Robots and Vision (CRV)_ , Guelph, ON, Canada, 2024. IEEE.
  * Hutchison et al. [2010] David Hutchison, Takeo Kanade, Josef Kittler, Jon M. Kleinberg, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Madhu Sudan, Demetri Terzopoulos, Doug Tygar, Moshe Y. Vardi, Gerhard Weikum, Thomas Brox, and Jitendra Malik.  Object Segmentation by Long Term Analysis of Point Trajectories.  In _Computer Vision – ECCV 2010_ , pages 282–295. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010.  Series Title: Lecture Notes in Computer Science.
  * Isack and Boykov [2012] Hossam Isack and Yuri Boykov.  Energy-Based Geometric Multi-model Fitting.  _International Journal of Computer Vision_ , 97(2):123–147, 2012.
  * Jianbo Shi and Tomasi [1994] Jianbo Shi and Tomasi.  Good features to track.  In _Proceedings of IEEE Conference on Computer Vision and Pattern Recognition CVPR-94_ , pages 593–600, Seattle, WA, USA, 1994. IEEE Comput. Soc. Press.
  * Jiang et al. [2021] Yangbangyan Jiang, Qianqian Xu, Ke Ma, Zhiyong Yang, Xiaochun Cao, and Qingming Huang.  What to Select: Pursuing Consistent Motion Segmentation from Multiple Geometric Models.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(2):1708–1716, 2021.  Number: 2.
  * Ke et al. [2023] Lei Ke, Mingqiao Ye, Martin Danelljan, Yifan Liu, Yu-Wing Tai, Chi-Keung Tang, and Fisher Yu.  Segment Anything in High Quality, 2023.  arXiv:2306.01567 [cs].
  * Keuper et al. [2015] Margret Keuper, Bjoern Andres, and Thomas Brox.  Motion Trajectory Segmentation via Minimum Cost Multicuts.  In _2015 IEEE International Conference on Computer Vision (ICCV)_ , pages 3271–3279, 2015.  ISSN: 2380-7504.
  * Kumar et al. [2011] Abhishek Kumar, Piyush Rai, and Hal Daume.  Co-regularized Multi-view Spectral Clustering.  In _Advances in Neural Information Processing Systems_. Curran Associates, Inc., 2011.
  * Lai et al. [2017] Taotao Lai, Hanzi Wang, Yan Yan, Tat-Jun Chin, and Wan-Lei Zhao.  Motion Segmentation Via a Sparsity Constraint.  _IEEE Transactions on Intelligent Transportation Systems_ , 18(4):973–983, 2017.  Conference Name: IEEE Transactions on Intelligent Transportation Systems.
  * Liu et al. [2023] Shilong Liu, Zhaoyang Zeng, Tianhe Ren, Feng Li, Hao Zhang, Jie Yang, Chunyuan Li, Jianwei Yang, Hang Su, Jun Zhu, and Lei Zhang.  Grounding DINO: Marrying DINO with Grounded Pre-Training for Open-Set Object Detection, 2023.  arXiv:2303.05499 [cs].
  * Longuet-Higgins and Prazdny [1980] H. C. Longuet-Higgins and K. Prazdny.  The Interpretation of a Moving Retinal Image.  _Proceedings of the Royal Society of London. Series B, Biological Sciences_ , 208(1173):385–397, 1980.  Publisher: The Royal Society.
  * Meunier et al. [2023] Etienne Meunier, Anaïs Badoual, and Patrick Bouthemy.  EM-Driven Unsupervised Learning for Efficient Motion Segmentation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 45(4):4462–4473, 2023.  Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * Mitiche and Aggarwal [2014] Amar Mitiche and J.K. Aggarwal.  _Computer Vision Analysis of Image Motion by Variational Methods_.  Springer International Publishing, Cham, 2014.
  * Mohamed et al. [2021] Eslam Mohamed, Mahmoud Ewaisha, Mennatullah Siam, Hazem Rashed, Senthil Yogamani, Waleed Hamdy, Mohamed El-Dakdouky, and Ahmad El-Sallab.  Monocular Instance Motion Segmentation for Autonomous Driving: KITTI InstanceMotSeg Dataset and Multi-Task Baseline.  In _2021 IEEE Intelligent Vehicles Symposium (IV)_ , pages 114–121, Nagoya, Japan, 2021. IEEE Press.
  * [36] Michal Neoral.  Monocular Arbitrary Moving Object Discovery and Segmentation.
  * Ochs et al. [2014] Peter Ochs, Jitendra Malik, and Thomas Brox.  Segmentation of Moving Objects by Long Term Video Analysis.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 36(6):1187–1200, 2014.  Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * Oquab et al. [2023] Maxime Oquab, Timothée Darcet, Théo Moutakanni, Huy Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, Mahmoud Assran, Nicolas Ballas, Wojciech Galuba, Russell Howes, Po-Yao Huang, Shang-Wen Li, Ishan Misra, Michael Rabbat, Vasu Sharma, Gabriel Synnaeve, Hu Xu, Hervé Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski.  DINOv2: Learning Robust Visual Features without Supervision, 2023.
  * [39] Anestis Papazoglou and Vittorio Ferrari.  V.: Fast object segmentation in unconstrained video.  In _In: ICCV (2013_.
  * Park and Jun [2009] Hae-Sang Park and Chi-Hyuck Jun.  A simple and fast algorithm for K-medoids clustering.  _Expert Systems with Applications_ , 36(2):3336–3341, 2009.
  * Pont-Tuset et al. [2018] Jordi Pont-Tuset, Federico Perazzi, Sergi Caelles, Pablo Arbeláez, Alex Sorkine-Hornung, and Luc Van Gool.  The 2017 DAVIS Challenge on Video Object Segmentation, 2018.  arXiv:1704.00675 [cs].
  * Rajič et al. [2023] Frano Rajič, Lei Ke, Yu-Wing Tai, Chi-Keung Tang, Martin Danelljan, and Fisher Yu.  Segment Anything Meets Point Tracking, 2023.
  * Ramzy et al. [2019] Mohamed Ramzy, Hazem Rashed, Ahmad El Sallab, and Senthil Yogamani.  RST-MODNet: Real-time Spatio-temporal Moving Object Detection for Autonomous Driving, 2019.  arXiv:1912.00438 [cs, stat] version: 1.
  * Rao et al. [2010] Shankar Rao, Roberto Tron, Rene Vidal, and Yi Ma.  Motion Segmentation in the Presence of Outlying, Incomplete, or Corrupted Trajectories.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 32(10):1832–1845, 2010.  Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
  * Sekkati and Mitiche [2007] Hicham Sekkati and Amar Mitiche.  A variational method for the recovery of dense 3D structure from motion.  _Robotics and Autonomous Systems_ , 55(7):597–607, 2007.
  * Siam et al. [2018] Mennatullah Siam, Heba Mahgoub, Mohamed Zahran, Senthil Yogamani, Martin Jagersand, and Ahmad El-Sallab.  MODNet: Motion and Appearance based Moving Object Detection Network for Autonomous Driving.  In _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , pages 2859–2864, 2018.  ISSN: 2153-0017.
  * Sun et al. [2022] Deqing Sun, Charles Herrmann, Fitsum Reda, Michael Rubinstein, David J. Fleet, and William T. Freeman.  Disentangling Architecture and Training for Optical Flow.  In _Computer Vision – ECCV 2022_ , pages 165–182, Cham, 2022. Springer Nature Switzerland.
  * Tron and Vidal [2007] Roberto Tron and Rene Vidal.  A Benchmark for the Comparison of 3-D Motion Segmentation Algorithms.  In _2007 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 1–8, 2007.  ISSN: 1063-6919.
  * Vertens et al. [2017] Johan Vertens, Abhinav Valada, and Wolfram Burgard.  SMSnet: Semantic motion segmentation using deep convolutional neural networks.  In _2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 582–589, 2017.  ISSN: 2153-0866.
  * Vidal [2011] Rene Vidal.  Subspace Clustering.  _IEEE Signal Processing Magazine_ , 28(2):52–68, 2011.
  * Von Luxburg [2007] Ulrike Von Luxburg.  A tutorial on spectral clustering.  _Statistics and Computing_ , 17(4):395–416, 2007.
  * Wedel et al. [2009a] Andreas Wedel, Annemarie Meißner, Clemens Rabe, Uwe Franke, and Daniel Cremers.  Detection and Segmentation of Independently Moving Objects from Dense Scene Flow.  In _Energy Minimization Methods in Computer Vision and Pattern Recognition_ , pages 14–27. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009a.  Series Title: Lecture Notes in Computer Science.
  * Wedel et al. [2009b] Andreas Wedel, Annemarie Meißner, Clemens Rabe, Uwe Franke, and Daniel Cremers.  Detection and Segmentation of Independently Moving Objects from Dense Scene Flow.  pages 14–27, 2009b.
  * Xu et al. [2018a] Ning Xu, Linjie Yang, Yuchen Fan, Jianchao Yang, Dingcheng Yue, Yuchen Liang, Brian Price, Scott Cohen, and Thomas Huang.  YouTube-VOS: Sequence-to-Sequence Video Object Segmentation.  In _Computer Vision – ECCV 2018_ , pages 603–619. Springer International Publishing, Cham, 2018a.  Series Title: Lecture Notes in Computer Science.
  * Xu et al. [2018b] Xun Xu, Loong Fah Cheong, and Zhuwen Li.  Motion Segmentation by Exploiting Complementary Geometric Models.  In _2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 2859–2867, Salt Lake City, UT, USA, 2018b. IEEE.
  * Yang and Ramanan [2021] Gengshan Yang and Deva Ramanan.  Learning to Segment Rigid Motions from Two Frames.  In _2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1266–1275, Nashville, TN, USA, 2021. IEEE.
  * Yang and Yang [2022] Zongxin Yang and Yi Yang.  Decoupling Features in Hierarchical Propagation for Video Object Segmentation.  _Advances in Neural Information Processing Systems_ , 35:36324–36336, 2022.
  * Zhang et al. [2023] Youcai Zhang, Xinyu Huang, Jinyu Ma, Zhaoyang Li, Zhaochuan Luo, Yanchun Xie, Yuzhuo Qin, Tong Luo, Yaqian Li, Shilong Liu, Yandong Guo, and Lei Zhang.  Recognize Anything: A Strong Image Tagging Model, 2023.  arXiv:2306.03514 [cs].