# Layerwise Quantum Convolutional Neural Networks Provide a Unified Way for
Estimating Fundamental Properties of Quantum Information Theory

Myeongjin Shin<EMAIL_ADDRESS>School of Computing, KAIST, Daejeon
34141, Korea  Seungwoo Lee  School of Computing, KAIST, Daejeon 34141, Korea
Mingyu Lee  Department of Computer Science and Engineering, Seoul National
University, Seoul 08826, Korea  Donghwa Ji  College of Liberal Studies, Seoul
National University, Seoul 08826, Korea  Hyeonjun Yeo  Department of physics
and astronomy, Seoul National University, Seoul 08826, Korea  Harrison J. Lee
<EMAIL_ADDRESS>School of Electrical and Electronic Engineering,
Yonsei University, Seoul 03722, Korea  Quantum Computing R&D, Norma Inc.,
Seoul 04799, Korea  Kabgyun Jeong<EMAIL_ADDRESS>Research Institute of
Mathematics, Seoul National University, Seoul 08826, Korea  School of
Computational Sciences, Korea Institute for Advanced Study, Seoul 02455, Korea

###### Abstract

The estimation of fundamental properties in quantum information theory,
including von Neumann entropy, Rényi entropy, Tsallis entropy, quantum
relative entropy, trace distance, and fidelity, has received significant
attention. While various algorithms exist for individual property estimation,
a unified approach is lacking. This paper proposes a unified methodology using
Layerwise Quantum Convolutional Neural Networks (LQCNN). Recent studies
exploring parameterized quantum circuits for property estimation face
challenges such as barren plateaus and complexity issues in large qubit
states. In contrast, our work overcomes these challenges, avoiding barren
plateaus and providing a practical solution for large qubit states. Our first
contribution offers a mathematical proof that the LQCNN structure preserves
fundamental properties. Furthermore, our second contribution analyzes the
algorithm’s complexity, demonstrating its avoidance of barren plateaus through
a structured local cost function.

##  I Introduction

In this paper, our objective is to estimate fundamental properties within
quantum information theory, encompassing von Neumann entropy
($S(\rho)=-\mathrm{Tr}(\rho\log\rho)$), Rényi entropy
($S_{\alpha}(\rho)=\frac{1}{1-\alpha}\log(\mathrm{Tr}(\rho^{\alpha}))$),
Tsallis entropy
($S_{q}(\rho)=\frac{1}{1-q}\left(\mathrm{Tr}(\rho^{q})-1\right)$), quantum
relative entropy ($S(\rho||\sigma)=\mathrm{Tr}(\rho\log\rho-\rho\log\sigma)$),
trace distance ($T(\rho,\sigma)=\frac{1}{2}\mathrm{Tr}|\rho-\sigma|$), and
fidelity
($F(\rho,\sigma)=\left(\mathrm{Tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^{2}$).
The estimation of these quantities has garnered significant interest,
resulting in numerous papers acharya2020estimating ; subramanian2021quantum ;
wang2022new ; wang2023quantum ; acharya2019measuring ; wang2023fast ;
chen2021variational ; shin2023estimating ; goldfeld2023quantum ;
lee2023estimating . However, a unified approach to estimate all these
quantities has not been proposed. As a consequence, different algorithm
implementations are necessary to estimate each quantity, leading to an
increase in the required copies of the quantum state with the growing number
of fundamental properties.

Regarding algorithm implementation details, quantum neural estimation of
entropies (QNEE) goldfeld2023quantum  stands out as a highly unified approach.
QNEE utilizes variational formulas, where the lower or upper bounds of each
formula correspond to fundamental properties. To optimize the variational
formula and determine the lower or upper bounds, parameterized quantum
circuits are employed. The advantage lies in the ease of implementing this
algorithm in software, as only the variational formula needs to be altered to
estimate other quantities. However, in terms of hardware cost and copy
complexity, QNEE falls short of providing a unified solution. The ansatz and
parameters in parameterized quantum circuits must be adjusted for each
property, preventing the reuse of optimized parameters. Consequently, the
number of training instances is proportional to the number of quantities to be
estimated, leading to an increase in copy complexity. Additionally, both QNEE
and other methods employing parameterized quantum circuits face a critical
issue known as barren plateaus mcclean2018barren ; marrero2021entanglement .

This paper introduces an algorithm that employs a parameterized quantum
circuit to estimate fundamental properties in a unified manner, addressing
both implementation and complexity concerns. The proposed quantum circuit is
trained layer-wise, with each layer utilizing a local cost function during
optimization. Each layer’s objective is to diminish the dimension of the
quantum state while preserving all fundamental properties with minimal error.
Once a layer is trained, its parameters are fixed, and training subsequent
layers does not impact the parameters of previous layers. We term this
architecture Layerwise Quantum Convolutional Neural Network (LQCNN).

##  II Background

###  II.1 Fundamental Properties of Quantum Information Theory

The von Neumann entropy $S(\rho)$ is defined for a density matrix $\rho$ as:

$S(\rho)=-\text{tr}(\rho\log(\rho)).$

This quantity represents the average amount of uncertainty or information in a
quantum state. In quantum statistical mechanics, it finds application in the
context of thermal states, where $S$ quantifies the system’s entropy.

The Rényi entropy $S_{\alpha}(\rho)$ is a family of entropies parameterized by
$\alpha$, defined as:

$S_{\alpha}(\rho)=\frac{1}{1-\alpha}\log(\text{tr}(\rho^{\alpha})).$

This generalization offers a spectrum of information measures. In quantum
phase transitions, $S_{\alpha}$ characterizes the order of the transition,
providing a richer understanding of critical phenomena.

The Tsallis entropy $S_{q}(\rho)$ is expressed as:

$S_{q}(\rho)=\frac{1}{1-q}\left(\text{tr}(\rho^{q})-1\right).$

Its application extends to the study of non-equilibrium quantum systems. In
quantum phase transitions, $S_{q}$ captures deviations from thermal
equilibrium, providing insights into the emergence of complexity in quantum
dynamics.

The trace distance $T(\rho,\sigma)$ quantifies the distinguishability between
quantum states $\rho$ and $\sigma$, defined as:

$T(\rho,\sigma)=\frac{1}{2}\text{tr}|\rho-\sigma|=\frac{1}{2}||\rho-\sigma||_{1}.$

In quantum communication, trace distance serves as a figure of merit. For
instance, in quantum key distribution, it gauges the distinguishability of
quantum states and influences the security of the protocol.

The fidelity $F(\rho,\sigma)$ measures the similarity between two quantum
states $\rho$ and $\sigma$, given by:

$F(\rho,\sigma)=\left(\text{tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^{2}.$

Beyond its role as a similarity metric, fidelity is integral to quantum error
correction. It ensures the accuracy of quantum gates by quantifying how well
an ideal quantum state is approximated by an imperfect operation.

The relative entropy $S(\rho||\sigma)$ also quantifies the distinguishability
between two quantum states like trace distance. It defined as:

$S(\rho||\sigma)=-\text{tr}\rho\log\sigma-S(\rho)=\text{tr}\rho(\log\rho-\log\sigma).$

It is asymmetric unlike trace distance because it measures the difference in
uncertainty between two states.

To understand these measures more deeply, one needs to explore advanced
mathematical concepts. Operator theory becomes crucial, particularly when
dealing with density matrices, and functional analysis is employed to study
the properties of quantum states in Hilbert spaces. Additionally, concepts
from quantum information theory, such as completely positive maps, play a
vital role in extending these measures to complex quantum scenarios.

In conclusion, the mathematical richness of these quantum information measures
not only contributes to their elegance but also underscores their versatility
and applicability across a spectrum of quantum phenomena, from foundational
principles to cutting-edge quantum technologies.

###  II.2 Continuity Bound of Fundamental Properties

The continuity bound of fundamental properties shows that if quantum states
are close enough, the fundamental properties are close too. Trace
norm(distance) $T=\frac{1}{2}||\rho-\sigma||_{1}$ is often used as the measure
to represent the distance of the quantum states in the continuity bound.

Audenaert audenaert2007sharp  proved the continuity bound of von Neumann
entropy with respect to trace norm:

$|S(\rho)-S(\sigma)|\leq T\log\left(d-1\right)-T\log
T-(1-T)\log\left(1-T\right).$

Audenaert audenaert2007sharp  and Chen chen2017sharp  proved the continuity
bound of Rényi entropy with respect to trace norm:

$\displaystyle|S_{\alpha}(\rho)-S_{\alpha}(\sigma)|\leq\begin{cases}\frac{1}{1-\alpha}\log((1-T)^{\alpha}+(d-1)^{1-\alpha}T^{\alpha})&(0<\alpha<1)\\\
\frac{1}{1-\alpha}(1-(1-T)^{\alpha}-(d-1)^{1-\alpha}T^{\alpha})&(\alpha>1).\\\
\end{cases}$

Audenaert audenaert2007sharp  and Raggio raggio1995properties  proved the
continuity bound of Tsallis entropy with respect to trace norm:

$\displaystyle|S_{q}(\rho)-S_{q}(\sigma)|\leq\begin{cases}\frac{1}{1-q}((1-T)^{q}-1+(d-1)^{1-q}T^{q})&(0<q<1)\\\
\frac{2q}{1-q}T&(q>1).\\\ \end{cases}$

Recently, general continuity bounds for quantum relative entropies have been
found bluhm2023general :

$|S(\rho_{1}||\sigma_{1})-S(\rho_{2}||\sigma_{2})|\leq(1-\frac{\log
m}{\sqrt{2}})||\rho_{1}-\rho_{2}||_{1}+\frac{5\log^{2}m}{\sqrt{2}(1-m)}||\sigma_{1}-\sigma_{2}||_{1},$

where $\textnormal{ker}\rho_{1}\subset\textnormal{ker}\sigma_{1}$,
$\textnormal{ker}\rho_{2}\subset\textnormal{ker}\sigma_{2}$ and $m$ satisfies
$m\rho_{1}\leq\sigma_{1}$, $m\rho_{2}\leq\sigma_{2}$.

The continuity bound of trace distance and fidelity can be derived from the
triangle inequality. The triangle inequality of trace distance is represented
as nielsen2001quantum :

$T(\rho,\sigma)+T(\sigma,\gamma)\geq T(\rho,\gamma).$

On the other hand, fidelity doesn’t satisfy the triangle inequality directly.
But it is known that it satisfies nielsen2001quantum :

$\arccos F(\rho,\sigma)+\arccos F(\sigma,\gamma)\geq\arccos F(\rho,\gamma).$

We derive the continuity bound of fidelity in the next section.

###  II.3 Estimation of Fundamental Properties

Estimation of fundamental properties has garnered significant interest in
quantum information theory throughout the years. Most intuitive way is to use
quantum state tomography to restore the density matrix and calculate the
fundamental properties by definition. This approach is undesirable, because
the time complexity is proportional to the dimension of the state, which is
the exponential of the number of qubits.

Numerous papers acharya2020estimating ; subramanian2021quantum ; wang2022new ;
wang2023quantum ; acharya2019measuring ; wang2023fast ; chen2021variational ;
shin2023estimating ; goldfeld2023quantum ; lee2023estimating  tried to address
this problem. Estimation under quantum query model effectively address the
problem. The query complexity of the algorithm polynomial to the rank of the
quantum states wang2022new . However, these quantum query model algorithms
have limitation because the quantum circuit which generates the quantum state
needs to be prepared, and the effectiveness of constructing a query model for
input state isn’t known wang2023quantum . So many algorithmswang2023quantum ;
wang2023fast ; subramanian2021quantum  tried to estimate the quantities by
only using the identical copies of the unknown quantum state. These algorithms
provide speedups in certain cases but in worst cases it still needs
exponential resources.

All of the current approach doesn’t provide a unified solution for estimating
fundamental properties. Many algorithms only provide estimation for certain
quantities. In contrast, Algorithms that use variational formula allows us to
estimate all the quantities in a similar way shin2023estimating ;
goldfeld2023quantum ; lee2023estimating ; chen2021variational . But the ansatz
and parameters in parameterized quantum circuits must be adjusted and can’t be
reused. This paper provied a unified solution for estimation.

Currently, algorithms using parameterized quantum circuits have produced
promising results shin2023estimating ; goldfeld2023quantum ; lee2023estimating
; chen2021variational . Those approaches builds upon the possibility of
parameterized quantum circuits can provide quantum speedup and is full
trainable by using classical optimizers goldfeld2023quantum . They use
variational formulas, where the lower or upper bounds of each formula
correspond to fundamental properties. Parameterized quantum circuits are
employed to optimize the variational formula and determine the lower or upper
bounds. But the variational formula can’t be fully optimized in deep circuits,
because those formulas are global cost functions and can’t be full trained
because of barren plateaus mcclean2018barren ; cerezo2021cost . This paper
also addressed the problem of barren plateaus.

##  III Fundamental Properties Preservation of Quantum Information Theory

We propose and demonstrate that fundamental properties of quantum information,
such as von Neumann entropy, Rényi entropy, Tsallis entropy, quantum relative
entropy, fidelity, and trace distance, can be preserved with minimal error
while simultaneously reducing the dimension of the quantum state. If an
appropriate unitary operation exists, we apply it and subsequently trace out
the first qubit of the quantum state.

######  Theorem 1 (Fundamental Properties Preservation).

Let $\rho$ and $\sigma$ be density matrices of dimension $d=2^{n}$ with ranks
$r_{1}$ and $r_{2}$, respectively. Suppose there exists a unitary operator $U$
such that:

$\mbox{$\textnormal{Tr}$}(U\rho U^{\dagger}|0\rangle\langle 0|\otimes
I_{n-1})\geq 1-\epsilon,\;\;\textnormal{and}$ (1)
$\mbox{$\textnormal{Tr}$}(U\sigma U^{\dagger}|0\rangle\langle 0|\otimes
I_{n-1})\geq 1-\epsilon^{\prime}.$ (2)

Then, define $\rho^{\prime}$ and $\sigma^{\prime}$ as:

$\rho^{\prime}=\mbox{$\textnormal{Tr}$}_{1}(U\rho U^{\dagger}|0\rangle\langle
0|\otimes I_{n-1}),\;\;\textnormal{and}$ (3)
$\sigma^{\prime}=\mbox{$\textnormal{Tr}$}_{1}(U\sigma
U^{\dagger}|0\rangle\langle 0|\otimes I_{n-1}).$ (4)

Then, we have:

$|f(\rho,\sigma)-f(\rho^{\prime},\sigma^{\prime})|\leq
O(\textnormal{function}(f_{params},n,d,\epsilon,\epsilon^{\prime})),$ (5)

where $f$ is the fundamental property function, $f_{params}$ are the
parameters of f, $\epsilon>0$ and $\epsilon^{\prime}>0$ are error terms.

###### Proof.

Suppose $\rho=\sum_{i=1}^{r_{1}}p_{i}|\psi_{i}\rangle\langle\psi_{i}|$ and
$\sigma=\sum_{i=1}^{r_{2}}q_{i}|\phi_{i}\rangle\langle\phi_{i}|$. Given that
it satisfies Eqs. (1) and (2), $U\rho U^{\dagger}$ and $U\sigma U^{\dagger}$
can be expressed as:

$U\rho
U^{\dagger}=\sum_{i=1}^{r_{1}}p_{i}\left(\sqrt{1-\epsilon_{i}}|0\rangle|\psi_{i0}\rangle+\sqrt{\epsilon_{i}}|1\rangle|\psi_{i1}\rangle\right)\left(\sqrt{1-\epsilon_{i}}\langle
0|\langle\psi_{i0}|+\sqrt{\epsilon_{i}}\langle
1|\langle\psi_{i1}|\right),\;\;\textnormal{and}$

$U\sigma
U^{\dagger}=\sum_{i=1}^{r_{2}}q_{i}\left(\sqrt{1-\epsilon_{i}^{\prime}}|0\rangle|\phi_{i0}\rangle+\sqrt{\epsilon_{i}^{\prime}}|1\rangle|\phi_{i1}\rangle\right)\left(\sqrt{1-\epsilon_{i}^{\prime}}\langle
0|\langle\phi_{i0}|+\sqrt{\epsilon_{i}^{\prime}}\langle
1|\langle\phi_{i1}|\right),$

where the conditions are such that:

$\sum_{i=1}^{r_{1}}\epsilon_{i}p_{i}=\epsilon,\;\;\textnormal{and}\quad\sum_{i=1}^{r_{2}}\epsilon_{i}^{\prime}q_{i}=\epsilon^{\prime}.$

Consequently, we obtain:

$\rho^{\prime}=\sum_{i=1}^{r_{1}}\frac{(1-\epsilon_{i})p_{i}}{1-\epsilon}|\psi_{i0}\rangle\langle\psi_{i0}|,\;\;\textnormal{and}\quad\sigma^{\prime}=\sum_{i=1}^{r_{2}}\frac{(1-\epsilon_{i}^{\prime})q_{i}}{1-\epsilon^{\prime}}|\phi_{i0}\rangle\langle\phi_{i0}|.$

The comprehensive proof for each fundamental property function is provided
below. ∎

Theorem 1 suggests that fundamental properties can be preserved with low error
while reducing the dimension of the quantum state if a feasible unitary
exists. Each fundamental property can be proved by using Theorem 2 and the
continuity bounds of fundamental properties.

######  Theorem 2 (Trace Distance of Input and Output).

Let $\rho$ be a density matrix of dimension $d=2^{n}$ with rank $r$. Suppose
there exists a unitary operator $U$ that satisfies Eq (1). Then, define
$\rho^{\prime}$ as given in Eq (3). Subsequently,

$T(U\rho U^{\dagger},|0\rangle\langle
0|\otimes\rho^{{}^{\prime}})=O\left(\sqrt{\epsilon}\right).$ (6)

###### Proof.

$\displaystyle\|U\rho U^{\dagger}-|0\rangle\langle
0|\otimes\rho^{{}^{\prime}}||_{1}$
$\displaystyle=||\sum(1-\epsilon_{i})p_{i}|0\rangle|\psi_{i0}\rangle\langle\psi_{i0}|\langle
0|+\epsilon_{i}p_{i}|1\rangle|\psi_{i1}\rangle\langle\psi_{i1}|\langle 1|$
$\displaystyle+\sqrt{1-\epsilon_{i}}\sqrt{\epsilon_{i}}p_{i}(|0\rangle|\psi_{i0}\rangle\langle\psi_{i1}|\langle
1|+|1\rangle|\psi_{i1}\rangle\langle\psi_{i0}|\langle
0|)-\sum\frac{(1-\epsilon_{i})p_{i}}{1-\epsilon}|0\rangle|\psi_{i0}\rangle\langle\psi_{i0}|\langle
0|||_{1}$
$\displaystyle=||-\sum\frac{(1-\epsilon_{i})p_{i}\epsilon}{1-\epsilon}|0\rangle|\psi_{i0}\rangle\langle\psi_{i0}|\langle
0|+\epsilon_{i}p_{i}|1\rangle|\psi_{i1}\rangle\langle\psi_{i1}|\langle 1|$
$\displaystyle\quad+\sqrt{1-\epsilon_{i}}\sqrt{\epsilon_{i}}p_{i}(|0\rangle|\psi_{i0}\rangle\langle\psi_{i1}|\langle
1|+|1\rangle|\psi_{i1}\rangle\langle\psi_{i0}|\langle 0|)||_{1}$
$\displaystyle\leq\sum\frac{(1-\epsilon_{i})p_{i}\epsilon}{1-\epsilon}\left\lVert|0\rangle|\psi_{i0}\rangle\langle\psi_{i0}|\langle
0|\right\rVert_{1}+\sum\epsilon_{i}p_{i}\left\lVert|1\rangle|\psi_{i1}\rangle\langle\psi_{i1}|\langle
1|\right\rVert_{1}$
$\displaystyle\quad+\sum\sqrt{1-\epsilon_{i}}\sqrt{\epsilon_{i}}p_{i}(|||0\rangle|\psi_{i0}\rangle\langle\psi_{i1}|\langle
1|||_{1}+\left\lVert|1\rangle|\psi_{i1}\rangle\langle\psi_{i0}|\langle
0|\right\rVert_{1})$
$\displaystyle=\sum\frac{(1-\epsilon_{i})p_{i}\epsilon}{1-\epsilon}+\epsilon_{i}p_{i}+2\sqrt{1-\epsilon_{i}}\sqrt{\epsilon_{i}}p_{i}=2\epsilon+2\sum\sqrt{1-\epsilon_{i}}\sqrt{\epsilon_{i}}p_{i}.$

Since $\sum\epsilon_{i}p_{i}=\epsilon$, by using cauchy-schwarz inequality the
following can be proved.

$\displaystyle\sum\sqrt{\epsilon_{i}}p_{i}\leq\sqrt{\epsilon}.$

So, we can conclude that:

$\displaystyle T(U\rho U^{\dagger},|0\rangle\langle
0|\otimes\rho^{{}^{\prime}})=\frac{1}{2}||U\rho U^{\dagger}-|0\rangle\langle
0|\otimes\rho^{{}^{\prime}}||_{1}<\epsilon+\sqrt{\epsilon}.$

∎

We define $T_{\rho}=T(U\rho U^{\dagger},|0\rangle\langle
0|\otimes\rho^{{}^{\prime}})=O(\sqrt{\epsilon})$ and $T_{\sigma}=T(U\sigma
U^{\dagger},|0\rangle\langle
0|\otimes\sigma^{{}^{\prime}})=O(\sqrt{\epsilon^{{}^{\prime}}})$.

###  III.1 von Neumann Entropy

######  Theorem 3 (von Neumann Entropy Preservation Theorem).

Let $\rho$ be an $d=2^{n}$ dimension, rank $r$ density matrix. Suppose that
there exists a unitary $U$ such that satisfies Eq (1). Then define
$\rho^{\prime}$ as Eq (3). Then,

$|S(\rho)-S(\rho^{\prime})|=O\left(\epsilon
n+\sqrt{\epsilon}\log\left(\frac{1}{\epsilon}\right)\right).$ (7)

###### Proof.

It is evident that $S(\rho)=S(U\rho U^{\dagger})$ and
$S(\rho^{{}^{\prime}})=S(|0\rangle\langle 0|\otimes\rho^{{}^{\prime}})$. By
using Theorem 2 and the continuity bound of von Neumann entropy, we can
conclude that:

$\displaystyle|S(\rho)-S(\rho^{\prime})|$ $\displaystyle=|S(U\rho
U^{\dagger})-S(|0\rangle\langle 0|\otimes\rho^{\prime})|$ $\displaystyle\leq
T_{\rho}\log(d-1)-T_{\rho}\log T_{\rho}-(1-T_{\rho})\log(1-T_{\rho})$
$\displaystyle=O(\sqrt{\epsilon}n-\sqrt{\epsilon}\log\sqrt{\epsilon}-(1-\sqrt{\epsilon})\log(1-\sqrt{\epsilon}))$
$\displaystyle=O\left(\epsilon
n+\sqrt{\epsilon}\log\left(\frac{1}{\epsilon}\right)\right).$

∎

The Rényi entropy and Tsallis entropy are preserved too. The proof can be done
in a similar manner. By using the Rényi and Tsallis entropy continuity bound
with Theorem 2.

###  III.2 Trace distance

######  Theorem 4 (Trace distance Preservation Theorem).

Let $\rho,\sigma$ be an $d=2^{n}$ dimension, rank $r_{1},r_{2}$ density
matrix. Suppose that there exists a unitary $U$ such that satisfies Eqs (1)
and (2). Then define $\rho^{\prime},\sigma^{\prime}$ as Eqs (3) and (4). Then,

$|T(\rho,\sigma)-T(\rho^{\prime},\sigma^{\prime})|=O(\sqrt{\epsilon}+\sqrt{\epsilon^{{}^{\prime}}}).$
(8)

###### Proof.

It is evident that $T(\rho,\sigma)=T(U\rho U^{\dagger},U\sigma U^{\dagger})$
and $T(\rho^{\prime},\sigma^{\prime})=T(|0\rangle\langle
0|\otimes\rho^{\prime},|0\rangle\langle 0|\otimes\sigma^{\prime})$. By using
the triangle inequality of trace distance we can conclude that:

$\displaystyle|T(\rho,\sigma)-T(\rho^{\prime},\sigma^{\prime})|$
$\displaystyle=|T(U\rho U^{\dagger},U\sigma U^{\dagger})-T(|0\rangle\langle
0|\otimes\rho^{\prime},|0\rangle\langle 0|\otimes\sigma^{\prime})|$
$\displaystyle\leq T(U\rho U^{\dagger},|0\rangle\langle
0|\otimes\rho^{\prime})+T(U\sigma U^{\dagger},|0\rangle\langle
0|\otimes\sigma^{\prime})$
$\displaystyle=T_{\rho}+T_{\sigma}=O(\sqrt{\epsilon}+\sqrt{\epsilon^{{}^{\prime}}}).$

∎

###  III.3 Fidelity

######  Theorem 5 (Fidelity Preservation Theorem).

Let $\rho,\sigma$ be an $d=2^{n}$ dimension, rank $r_{1},r_{2}$ density
matrix. Suppose that there exists a unitary $U$ such that satisfies Eqs (1)
and (2). Then define $\rho^{\prime},\sigma^{\prime}$ as Eqs (3) and (4). Then,

$|F(\rho,\sigma)-F(\rho^{\prime},\sigma^{\prime})|=O(\sqrt[4]{\epsilon}+\sqrt[4]{\epsilon^{{}^{\prime}}}).$
(9)

###### Proof.

It is evident that $F(\rho,\sigma)=F(U\rho U^{\dagger},U\sigma U^{\dagger})$
and $F(\rho^{\prime},\sigma^{\prime})=F(|0\rangle\langle
0|\otimes\rho^{\prime},|0\rangle\langle 0|\otimes\sigma^{\prime})$. Define
$A(\rho,\sigma)=\arccos{F(\rho,\sigma)}$. It is proven that triangle
inequality for $A$ works nielsen2001quantum :

$\displaystyle A(\rho,\sigma)+A(\sigma,\gamma)\geq A(\rho,\gamma).$

By using that triangle inequality and using the inequality
$F(\rho,\sigma)\geq(1-T(\rho,\sigma))^{2}$, we can conclude that:

$\displaystyle|A(\rho,\sigma)-A(\rho^{{}^{\prime}},\sigma^{{}^{\prime}})|$
$\displaystyle\leq A(U\rho U^{\dagger},|0\rangle\langle
0|\otimes\rho^{\prime})+A(U\sigma U^{\dagger},|0\rangle\langle
0|\otimes\sigma^{\prime})$ $\displaystyle=\arccos{F(U\rho
U^{\dagger},|0\rangle\langle 0|\otimes\rho^{\prime})}+\arccos{F(U\sigma
U^{\dagger},|0\rangle\langle 0|\otimes\sigma^{\prime})}$
$\displaystyle\leq\arccos{(1-T_{\rho})^{2}}+\arccos{(1-T_{\sigma})^{2}}$
$\displaystyle\leq\arccos{(1-\sqrt{\epsilon}-\epsilon)^{2}}+\arccos{(1-\sqrt{\epsilon^{{}^{\prime}}}-\epsilon^{{}^{\prime}})^{2}}$
$\displaystyle=O(\sqrt[4]{\epsilon}+\sqrt[4]{\epsilon^{{}^{\prime}}}).$

Now applying mean value theorem, we can conclude that:

$\displaystyle|F(\rho,\sigma)-F(\rho^{{}^{\prime}},\sigma^{{}^{\prime}})|$
$\displaystyle=|\arccos{F(\rho,\sigma)}-\arccos{F(\rho^{{}^{\prime}},\sigma^{{}^{\prime}})}|\sqrt{1-t^{2}}$
$\displaystyle<|A(\rho,\sigma)-A(\rho^{{}^{\prime}},\sigma^{{}^{\prime}})|=O(\sqrt[4]{\epsilon}+\sqrt[4]{\epsilon^{{}^{\prime}}}).$

∎

During the proof, we suggested a new continuity bound for fidelity in both
inputs.

###  III.4 Quantum Relative Entropy

######  Theorem 6 (Quantum Relative Entropy Preservation Theorem).

Let $\rho,\sigma$ be an $d=2^{n}$ dimension, rank $r_{1},r_{2}$ density
matrix. Suppose that there exists a unitary $U$ such that satisfies Eqs (1)
and (2). Then define $\rho^{\prime},\sigma^{\prime}$ as Eqs (3) and (4). Then,

$|S(\rho||\sigma)-S(\rho^{\prime}||\sigma^{\prime})|=O((1-\frac{\log
m}{\sqrt{2}})\sqrt[4]{\epsilon}+\frac{5\log^{2}m}{\sqrt{2}(1-m)}\sqrt[4]{\epsilon^{{}^{\prime}}}),$
(10)

where $\textnormal{ker}\rho\subset\textnormal{ker}\sigma$ and $m$ satisfies
$m\rho\leq\sigma$.

###### Proof.

It is evident that $S(\rho||\sigma)=S(U\rho U^{\dagger}||U\sigma U^{\dagger})$
and $S(\rho^{\prime}||\sigma^{\prime})=S(|0\rangle\langle
0|\otimes\rho^{\prime}|||0\rangle\langle 0|\otimes\sigma^{\prime})$. We can
also prove that
$\textnormal{ker}\rho^{{}^{\prime}}\subset\textnormal{ker}\sigma^{{}^{\prime}}$.
So we can use the continuity bound for quantum relative entropy
bluhm2023general . Applying Theorem 2 to the continuity bound, we can conclude
the proof. ∎

##  IV Layerwise Quantum Convolutional Neural Network

When training quantum neural networks (QNNs), researchers have initiated
studies to address the issue of Barren Plateaus, which can impede learning. A
notable proposal in this regard is the quantum convolutional neural network
(QCNN) structure introduced by Cong et al cong2019quantum . This QCNN
structure is known to mitigate the occurrence of Barren Plateaus during the
learning process by employing a local cost function and a pooling layer
pesah2021absence . Inspired by this architecture and using the fundamental
properties preservation theorem above, we propose a layerwise quantum
convolutional neural network (LQCNN) structure.

###  IV.1 Proposed Structure

The purpose of this structure is to reduce the number of qubits while
retaining the information of the initially given quantum state, and then
easily obtain the desired fundamental properties. To achieve this a process is
employed to reduce the number of qubits while preserving the fundamental
properties of the quantum state, incorporating ideas inspired by QCNN. This
structure is based on a sequential unitary operator and a trace-out process
conducted by post-processing. The $k$-th layer of LQCNN is represented by a
unitary operator $U_{k}(\theta_{k})$ designed to maximize the probability of
measuring $|0\rangle$ on the first qubit. Following the optimization of
$\theta_{k}$, we perform measurements on the first qubit. If the outcome is
$|0\rangle$, we discard the first qubit and pass the remaining qubits to the
subsequent layer. In the case of an outcome of $|1\rangle$, the entire state
is discarded, and the measurement is repeated until a $|0\rangle$ outcome is
obtained. Once each pooling layer $U_{k}(\theta_{k})$ is trained, the final
layer $U(\theta)$ serves as the processing layer responsible for calculating
fundamental properties. The processing layer can be implemented using quantum
state tomography, QNEE, or other methodologies.

Figure 1: Structure of LQCNN

Suppose that $\rho_{k},\sigma_{k}$ are the input states of the k-th layer
$U_{k}$. Theorem 1 suggest that if the probability of measuring $|0\rangle$ on
the first qubit of each
$U_{k}\rho_{k}U^{\dagger}_{k},U_{k}\sigma_{k}U^{\dagger}_{k}$ is small,
difference of the fundamental properties between $\rho_{k},\sigma_{k}$ and
between $\rho_{k+1},\sigma_{k+1}$ are small. This implies that if each layer
of LQCNN is trained well, the fundamental properties are passed with low error
to the next layer. So calculating fundamental properties of the final output
states of LQCNN, estimates the fundamental properties of the input states of
LQCNN.

###  IV.2 Analysis

By using LQCNN, the complexity of estimating the fundamental properties are
determined by two aspects. The complexity of calculating the fundamental
properties of the final layer states and the training complexity of each layer
in LQCNN.

The first complexity are determined by the dimension of the final states.
After each layer of LQCNN, the dimension is reduced to the half. The final
dimension is determined by the number of layers. Now we focus on how many
layer can be stacked. Theorem 1 suggests that fundamental properties can be
preserved with low error while reducing the dimension of the quantum state if
a feasible unitary exists. The feasible unitary is the unitary that maximizes
the probability of measuring 0 on the first qubit. Focusing on existence of
the feasible unitary, we can determine the number of layers. An important fact
is that the rank of quantum states monotonically decreases while passing the
layer of LQCNN. And if $2^{n-1}\geq r_{1}+r_{2}$, it is evident that a unitary
satisfying Eqs (1) and (2) exists. Thus, we can stack the layers while the
dimension of the quantum states is greater than the rank. Using the result of
previous papers shin2023estimating ; goldfeld2023quantum ; lee2023estimating ;
acharya2020estimating ; subramanian2021quantum ; wang2023quantum ;
acharya2019measuring ; wang2023fast ; chen2021variational  the complexity of
calculating fundamental properties will be proportional to the rank.

The second complexity are determined by the ansatz of each layer. As the
ansatz are complex the training becomes complex, but less error occurs. So
there is a trade-off between error and train complexity. An important aspect
of LQCNN is that it uses local cost function for training each layers. So it
avoids barren plateaus cerezo2021cost  and training is available for complex
ansatz. The training and ansatz complexity for construct each layer of LQCNN
for less error needs to be further investigated.

##  V Conclusions

We suggested fundamental properties preservation (FPP) theorem, a new
inequality for von Neumann entropy, Rényi entropy, Tsallis entropy, quantum
relative entropy, trace distance, and fidelity. FPP theorem can be proved by
using the continuity bounds and the triangle inequalities. In this paper LQCNN
is proposed and it can used to calculate the fundamental properties. By
applying FPP theorem, it can be proven that each layer of LQCNN preserves the
fundamental properties with low error. By using LQCNN, fundamental properties
can be calculated in a unified manner with low error and low complexity. And
since LQCNN uses local cost function, contrast to other parametric methods it
avoids barren plateaus. We also anticipate that LQCNN can play a key role in
other quantum machine learning sectors. We expect that fundamental properties
preservation characteristics of LQCNN can be applied to effectively extract
the information of a quantum state. Those applications and complexity of
training a unitary that satisfies Eqs (1) and (2) requires further research.

## Acknowledgments

This work was supported by the National Research Foundation of Korea (NRF)
through grants funded by the Ministry of Science and ICT
(NRF-2022M3H3A1098237) and the Ministry of Education
(NRF-2021R1I1A1A01042199). This work was partially supported by an Institute
for Information & Communications Technology Promotion (IITP) grant funded by
the Korean government (MSIP) (No. 2019-000003; Research and Development of
Core Technologies for Programming, Running, Implementing, and Validating of
Fault-Tolerant Quantum Computing Systems), and Korea Institute of Science and
Technology Information (KISTI).

## Notes

This preprint serves as a concise summary of the entire study, and a detailed
version including specific experimental results will be uploaded shortly.

## References

  * (1) J. Acharya, I. Issa, N. V. Shende, and A. B. Wagner, “Estimating quantum entropy,” IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 2, pp. 454–468, 2020.
  * (2) S. Subramanian and M.-H. Hsieh, “Quantum algorithm for estimating $\alpha$-renyi entropies of quantum states,” Physical review A, vol. 104, no. 2, p. 022428, 2021.
  * (3) Q. Wang, J. Guan, J. Liu, Z. Zhang, and M. Ying, “New quantum algorithms for computing quantum entropies and distances,” arXiv preprint arXiv:2203.13522, 2022.
  * (4) Y. Wang, B. Zhao, and X. Wang, “Quantum algorithms for estimating quantum entropies,” Physical Review Applied, vol. 19, no. 4, p. 044041, 2023.
  * (5) J. Acharya, I. Issa, N. V. Shende, and A. B. Wagner, “Measuring quantum entropy,” in 2019 IEEE International Symposium on Information Theory (ISIT), pp. 3012–3016, IEEE, 2019.
  * (6) Q. Wang and Z. Zhang, “Fast quantum algorithms for trace distance estimation,” arXiv preprint arXiv:2301.06783, 2023.
  * (7) R. Chen, Z. Song, X. Zhao, and X. Wang, “Variational quantum algorithms for trace distance and fidelity estimation,” Quantum Science and Technology, vol. 7, no. 1, p. 015019, 2021.
  * (8) M. Shin, J. Lee, and K. Jeong, “Estimating quantum mutual information through a quantum neural network,” arXiv preprint arXiv:2306.14566, 2023.
  * (9) Z. Goldfeld, D. Patel, S. Sreekumar, and M. M. Wilde, “Quantum neural estimation of entropies,” arXiv preprint arXiv:2307.01171, 2023.
  * (10) S. Lee, H. Kwon, and J. S. Lee, “Estimating entanglement entropy via variational quantum circuits with classical neural networks,” arXiv preprint arXiv:2307.13511, 2023.
  * (11) J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” Nature communications, vol. 9, no. 1, p. 4812, 2018.
  * (12) C. O. Marrero, M. Kieferová, and N. Wiebe, “Entanglement-induced barren plateaus,” PRX Quantum, vol. 2, no. 4, p. 040316, 2021.
  * (13) K. M. Audenaert, “A sharp continuity estimate for the von neumann entropy,” Journal of Physics A: Mathematical and Theoretical, vol. 40, no. 28, p. 8127, 2007.
  * (14) Z. Chen, Z. Ma, I. Nikoufar, and S. Fei, “Sharp continuity bounds for entropy and conditional entropy,” arXiv preprint arXiv:1701.02398, 2017.
  * (15) G. A. Raggio, “Properties of q-entropies,” Journal of Mathematical Physics, vol. 36, no. 9, pp. 4785–4791, 1995.
  * (16) A. Bluhm, Á. Capel, P. Gondolf, and A. Pérez-Hernández, “General continuity bounds for quantum relative entropies,” arXiv preprint arXiv:2305.10140, 2023.
  * (17) M. A. Nielsen and I. L. Chuang, “Quantum computation and quantum information,” Phys. Today, vol. 54, no. 2, p. 60, 2001.
  * (18) M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, “Cost function dependent barren plateaus in shallow parametrized quantum circuits,” Nature communications, vol. 12, no. 1, p. 1791, 2021.
  * (19) I. Cong, S. Choi, and M. D. Lukin, “Quantum convolutional neural networks,” Nature Physics, vol. 15, no. 12, pp. 1273–1278, 2019.
  * (20) A. Pesah, M. Cerezo, S. Wang, T. Volkoff, A. T. Sornborger, and P. J. Coles, “Absence of barren plateaus in quantum convolutional neural networks,” Physical Review X, vol. 11, no. 4, p. 041011, 2021.


# Motion Segmentation via Global and Local Sparse Subspace Optimization

Michael Ying Yang1, Hanno Ackermann2, Weiyao Lin3, Sitong Feng2 and Bodo
Rosenhahn2 1University of Twente<EMAIL_ADDRESS>University
Hannover2Shanghai Jiao Tong University

###### Abstract

In this paper, we propose a new framework for segmenting feature-based moving
objects under affine subspace model. Since the feature trajectories in
practice are high-dimensional and contain a lot of noise, we firstly apply the
sparse PCA to represent the original trajectories with a low-dimensional
global subspace, which consists of the orthogonal sparse principal vectors.
Subsequently, the local subspace separation will be achieved via automatically
searching the sparse representation of the nearest neighbors for each
projected data. In order to refine the local subspace estimation result and
deal with the missing data problem, we propose an error estimation to
encourage the projected data that span a same local subspace to be clustered
together. In the end, the segmentation of different motions is achieved
through the spectral clustering on an affinity matrix, which is constructed
with both the error estimation and sparse neighbors optimization. We test our
method extensively and compare it with state-of-the-art methods on the Hopkins
155 dataset and Freiburg-Berkeley Motion Segmentation dataset. The results
show that our method is comparable with the other motion segmentation methods,
and in many cases exceed them in terms of precision and computation time.

##  I Introduction

In the past years, dynamic scenes understanding has been receiving increasing
attention especially on the moving camera or multiple moving objects. Motion
segmentation as a part of the video segmentation is an essential part for
studying the dynamic scenes and many other computer vision applications [1].
Particularly, motion segmentation aims to decompose a video into different
regions according to different moving objects that tracked throughout the
video. In case of feature extraction for all the moving objects from the
video, segmentation of different motions is equivalent to segment the
extracted feature trajectories into different clusters. One example of
feature-based motion segmentation is presented in Figure 1.

Figure 1: Example results of the motion segmentation on the real traffic video
cars9.avi from the Hopkins 155 dataset [2].

Generally, the algorithms of motion segmentation are classified into 2
categories [3]: affinity-based methods and subspace-based methods. The
affinity-based methods focus on computing the correspondences of each pair of
the trajectories, whereas the subspace-based approaches use multiple subspaces
to model the multiple moving objects in the video and the segmentation of
different motions is accomplished through subspace clustering. Recently, some
affinity-based methods [3, 4] are proposed to cluster the trajectories with
unlimited number of missing data. However, the computation times of them are
so high that require an optimizing platform to be reduced. Whereas, the
subspace-based methods [5, 6] have been developed to reconstruct the missing
trajectories with their sparse representation. The drawback is that they are
sensitive to the real video which contains a large number of missing
trajectories. Most of the existing subspace-based methods still fall their
robustness for handling missing features. Thus, there is an intense demand to
explore a new subspace-base algorithm that can not only segment multiple kinds
of motions but also handle the missing and corrupted trajectories from the
real video.

###  I-A Contributions

We propose a new framework with subspace models for segmenting different types
of moving objects from a video under affine camera. We cast the motion
segmentation as a two stage subspace estimation: the global and local subspace
estimation. Sparse PCA [7] is adopted for optimizing the global subspace in
order to defend the noise and outliers. Meanwhile, we seek a sparse
representation for the nearest neighbors in the global subspace for each data
point that span a same local subspace. In order to solve the missing data
problem and refine the local subspace estimation, we propose an error
estimation and build the affinity graph for spectral clustering to obtain the
clusters. To the best of our knowledge, our framework is the first one to
simultaneously optimize the global and local subspace with sparse
representation.

The remaining sections are organized as follows. The related works are
discussed in Section II. The basic subspace models for motion segmentation are
introduced in Section III. The proposed approach will be described in detail
in Section IV. Furthermore, the experimental results are presented in Section
V. Finally, this paper is concluded in Section VI.

##  II Related Work

During the last decades, either the subspace-based techniques [5, 6] or the
affinity-based methods [3, 4] have been receiving an increasing interest on
segmentation of different types of motions from a real video.

Affinity-based methods. [4] uses the distances of each pair of feature
trajectories as the measurement to build the affinity matrix based on a
translational motion model. This method can segment motions with unlimited
number of missing or incomplete trajectories, which means they are robust to
the video with occlusions or moving camera problems. Another approach which is
based on the affinity is called Multi-scale Clustering for Motion Segmentation
(MSMC) [3]. Based on the conventional image classification technique split and
merge, they use the correspondences of each two features between two frames to
segment the different motions with many missing data. One of the general
problems of affinity-based method is highly time-consuming. They have to be
implemented with an optimized platform in order to save the computation times.

Subspace-based methods. The existing works based on subspace models can be
divided into 4 main categories: algebraic, iterative, sparse representation
and subspace estimation.

Algebraic approaches, such as Generalized Principal Component Analysis (GPCA)
[8], which uses the polynomials fitting and differentiation to obtain the
clusters. GPCA can segment the rigid and non-rigid motions effectively, but
once the number of moving objects in the video increases, its computation cost
increases and the precision decreases in the same time. The general procedure
of an iterative method contains two main aspects: find the initial solution
and refine the clustering results to fit each subspace model. RANdom SAmple
Consensus (RANSAC) [9] selects randomly the number of points from the original
dataset to fit the model. RANSAC is robust to the outliers and noise, but it
requires a good initial parameter selection. Specifically, it computes the
residual of each point to the model with setting a threshold, if the residual
is below the threshold, it will be considered as inliers and vice versa.
Sparse Subspace Clustering (SSC) [5] is one of the most popular method based
on the sparse representation. SSC exploits a fact that each point can be
linearly represented with a sparse combination of the rest of other data
points. SSC has one of the best accuracy compared with the other subspace-
based methods and can deal with the missing data. The limitation is that it
requires a lot of computation times. Another popular algorithm based on the
sparse representation is Agglomerate Lossy Compression (ALC) [6], which uses
compressive sensing on the subspace model to segment the video with missing or
corrupted trajectories. However, the implementation of ALC cannot ensure that
find the global maximum with the greedy algorithm. By the way ALC is highly
time-consuming in order to tune the parameter.

Our work combines the subspace estimation and sparse representation methods.
The subspace estimation algorithms, such as Local Subspace Affinity (LSA)
[10], firstly project original data set with a global subspace. Then the
projected global subspace is separated into multiple local subspaces through
K-nearest neighbors (KNN). After calculating the affinities of different
estimated local subspaces with principle angles, the final clusters are
obtained through spectral clustering. It comes to the issue that the KNN
policy may overestimate the local subspaces due to noise and improper
selection of the number K, which is determined by the rank of the local
subspace. LSA uses the model selection (MS) [11] to estimate the rank of
global and local subspaces, but the MS is quite sensitive to the noise level.

##  III Multi-body Motion Segmentation with Subspace models

In this section, we introduce the motion structure under affine camera model.
Subsequently, we show that under affine model segmentation of different
motions is equivalent to separate multiple low-dimensional affine subspaces
from a high-dimensional space.

###  III-A Affine Camera Model

Most of the popular algorithms assume an affine camera model, which is an
orthographic camera model and has a simple mathematical form. It gives us a
tractable representation of motion structure in the dynamic scenes. Under the
affine camera, the general procedure for motion segmentation is started from
translating the 3-D coordinates of each moving object to its 2-D locations in
each frame. Assume that $\\{x_{fp}\\}_{f=1,...,F}^{p=1,...,P}\in R^{2}$
represents one 2-D tracked feature point $p$ of one moving object at frame
$f$, its corresponding 3-D world coordinate is $\\{X_{p}\\}_{p=1,...,P}\in
R^{3}$. The pose of the moving object at frame $f$ can be represented with
$(R_{f},T_{f})\in SO(3)$, where $R_{f}$ and $T_{f}$ are related to the
rotation and translation respectively. Thus, each 2-D point $x_{fp}$ can be
described with Equation 1

$x_{fp}=\left[R_{f}\ T_{f}\right]X_{p}=A_{f}X_{p}$ (1)

where $A_{f}=\left[\begin{array}[]{ccc}1&0&0\\\ 0&1&0\\\
\end{array}\right]\left[R_{f}\ T_{f}\right]\in R^{2\times 4}$ is the affine
transformation matrix at frame $f$.

###  III-B Subspace models for Motion Segmentation under Affine View

The general input for the subspace-based motion segmentation under affine
camera can be formulated as a trajectory matrix containing the 2-D positions
of all the feature trajectories tracked throughout all the frames. Given 2-D
locations $\\{x_{fp}\\}_{f=1,...,F}^{p=1,...,P}\in R^{2}$ of the tracked
features on a rigid moving object, the corresponding trajectory matrix can be
formulated as Equation 2

$W_{2F\times P}=\left[\begin{array}[]{ccc}x_{11}&\cdots&x_{1P}\\\
\vdots&\vdots&\vdots\\\ x_{F1}&\cdots&x_{FP}\\\ \end{array}\right]$ (2)

under affine model, the trajectory matrix $W_{2F\times P}$ can be further
reformulated as Equation 3

$W_{2F\times P}=\left[\begin{array}[]{c}A_{1}\\\ \vdots\\\ A_{F}\\\
\end{array}\right]_{2F\times 4}\left[\begin{array}[]{ccc}X_{1}&\cdots&X_{P}\\\
1&\cdots&1\\\ \end{array}\right]_{4\times P}$ (3)

we can rewrite it as following,

$W_{2F\times P}=M_{2F\times 4}S_{P\times 4}^{T}$ (4)

where $M_{2F\times 4}$ is called motion matrix, whereas $S_{P\times 4}$ is
structure matrix. According to Equation 4, we can obtain that under affine
view the rank of trajectory matrix $W_{2F\times P}$ of a rigid motion is no
more than 4. Hence, as the trajectory matrix is obtained, the first step is
reducing its dimensionality with a low-dimension representation, which is
called the global subspace transformation. Subsequently, each projected
trajectory from the global subspace lives in a local subspace. Then the
obstacle of multi-body motion segmentation is to separate these underlying
local subspaces from the global subspace, which means the segmentation of
different motions is related with segmenting different subspaces.

##  IV Proposed Framework

Our proposed framework extends the LSA [10] with sparse optimization for both
the global and local parts. As shown in Figure 2, given a general trajectory
matrix, we firstly transform it into a global subspace with Sparse PCA [7],
which is robust to noise and outliers. Furthermore, instead of the KNN
estimation we use the sparse neighbors to automatically find the projected
data points span a same subspace. To correct the overestimation and encourage
the projected data from the same subspace to be collected, we propose an error
function to build the affinity matrix for spectral clustering.

Figure 2: Overview of the proposed framework.

###  IV-A Global Subspace Transformation

Due to the trajectory matrix of a rigid motion has a maximal rank 4, most
people choose the projected dimension to be $m=4n$ or $5$, where $n$ is the
number of the motions in the video. Assume that the trajectory matrix is
$W_{2F\times P}$, where $F$ is the number of frames and $P$ is the number of
extracted trajectories. The traditional way to project $W_{2F\times P}$ is
Principal Component Analysis (PCA) [12], which can be formed as following,

$z^{*}=\max_{z^{T}z\leq 1}z^{T}\Sigma z,$ (5)

where $\Sigma=W^{T}W$ is the covariance matrix of $W$, solutions $z^{*}$
represent the principal components. Usually, PCA can be obtained through
performing singular value decomposition (SVD) for $W$. The solutions $z^{*}$
are fully observed, which means they are constructed with all the input
variables. However, if the principal components $z^{*}$ are built with only a
few number of original variables but still can represent the original data
matrix well, it should be easier to separate the underlying local subspaces
from the transformed global subspace. The sparse PCA technique has been proved
that it is robust to the noise and outliers in terms of dimensionality
reduction and feature selection [13, 14], which aims to seek a low-dimensional
sparse representation for the original high-dimensional data matrix. In
contrast to PCA, sparse PCA produces the sparse principal components that
achieve the dimensional reduction with a small number of input variables but
can interpret the main structure and significant information of the original
data matrix.

In order to contain the orthogonality of projected vectors in the global
subspace, we apply the generalized power method for sparse PCA [15] to
transform the global subspace. Given the trajectory matrix $W_{2F\times
P}=\left[w_{1},...,w_{F}\right]^{T}$, where $w_{f}\in R^{2\times P},f=1,...,F$
contains all the tracked $P$ 2-D feature points in each frame $f$. We can
consider a direct single unit form as Equation 6 to extract one sparse
principal component $z^{*}\in R^{P}$ [7, 15].

$z^{*}(\gamma)=\max\limits_{y\in B^{P}}\max\limits_{z\in
B^{2F}}(y^{T}Wz)^{2}-\gamma\|z\|_{0}$ (6)

where $y$ denotes a initial fixed data point from the unit Euclidean sphere
$B^{P}=\\{y\in R^{P}|y^{T}y\leq 1\\}$, and $\gamma>0$ is the sparsity
controlling parameter. If project dimension is $m,1<m<2F$, which means there
are more than one sparse principal components needed to be extracted, in order
to enforce the orthogonality for the projected principal vectors, [15] extends
Equation 6 to block form with a trace function(Tr()), which can be defined as
Equation 7

$\displaystyle Z^{*}(\gamma)=$ $\displaystyle\max\limits_{Y\in
S_{m}^{P}}\max\limits_{Z\in[S^{2F}]^{m}}Tr(Diag(Y^{T}WZN)^{2})$ (7)
$\displaystyle-\sum_{j=1}^{m}\gamma_{j}\|z_{j}\|_{0}$

where $\gamma=\left[\gamma_{1},...,\gamma_{m}\right]^{T}$ is a positive
$m$-dimensional sparsity controlling parameter vector, and parameter matrix
$N=Diag(\mu_{1},\mu_{2},...,\mu_{m})$ with setting distinct positive diagonal
elements enforces the loading vectors $Z^{*}$ to be more orthogonal,
$S_{m}^{p}=\\{Y\in R^{P\times m}|Y^{T}Y=I_{m}\\}$ represents the Stiefel
manifold111Stiefel manifold: the Stiefel manifold $V^{k}(R^{n})$ is the set of
all orthonormal k-frames in $R^{n}$.. Subsequently, Equation 7 is completely
decoupled in the columns of $Z^{*}(\gamma)$ as following,

$Z^{*}(\gamma)=\max_{Y\in S_{m}^{P}}\sum_{j=1}^{m}\max_{z_{j}\in
S^{2F}}(\mu_{j}y_{j}^{T}Wz_{j})^{2}-\gamma_{j}||z_{j}||_{0}$ (8)

Obviously, the objective function in Equation 8 is not convex, but the
solution $Z^{*}{\gamma}$ can be obtained after solving a convex problem in
Equation 9

$Y^{*}(\gamma)=\max\limits_{Y\in
S_{m}^{P}}\sum_{j=1}^{m}\sum_{i=1}^{F}\left[(\mu_{j}w_{i}^{T}y_{j})^{2}-\gamma_{j}\right]_{+}$
(9)

which under the constraint that all
$\gamma_{j}>\mu_{j}^{2}\max_{i}||w_{i}||_{2}^{2}$. In [15], a gradient scheme
has been proposed to efficiently solve the convex problem in Equation 9.
Hence, the sparsity pattern $\mathbf{I}$ for the solution $Z^{*}$ is defined
by $Y^{*}$ after Equation 9 under the following criterion,

$\mathbf{I}=\left\\{\begin{array}[]{cc}active,&(\mu_{j}w_{i}^{T}y_{j}^{*})^{2}>\gamma_{j},\\\
0,&otherwise\\\ \end{array}\right.$ (10)

As a result, the seeking sparse loading vectors $Z^{*}\in S_{m}^{P}$ are
obtained after iteratively solving Equation 9. After normalization, the global
projected subspace $\widetilde{W}_{m\times P}=normalize(Z^{*})^{T}$ is
achieved, which is embedded with multiple orthogonal underlying local
subspaces.

###  IV-B Local Subspace Estimation

Figure 3: Illustration of 6-nearest neighbors and sparse nearest neighbors
policy. The circles and triangles represent the data points from two different
local subspaces respectively. The red points denote the estimated neighbors
for the observed data $\alpha_{i}$ from the same local subspace under the
determinate searching area.

In order to cluster the different subspaces according to different moving
bodies, the first step is finding out the multiple underlying local subspaces
from the global subspace. Generally, the estimation of different local
subspaces can be addressed as the extraction of different data sets, which
contain only the projected trajectories from the same subspace. One of the
most traditional way is the local sampling [10], which uses the KNN.
Specifically, the underlying local subspace spanned by each projected data is
found by collecting each projected data point and its corresponding K nearest
neighbors, which are calculated by the distances [10, 16]. However, the local
sampling can not ensure that all the extracted K-nearest neighbors truly span
one same subspace, which means an overestimation, especially for the video who
contains a lot of degenerated/depended motions or missing data. Moreover, [17]
has testified that the selection of number K is quite sensitive, which depends
on the rank estimation. In this paper, for the sake of avoiding the searching
for only nearest neighbors and solving the overestimation problem we adopt the
sparse nearest neighbors optimization to automatically find the set of the
projected data points that span a same local subspace.

The assumption of sparse nearest neighbors is derived from SMCE [18], which
can cluster the data point from a same manifold robustly. Given a random data
point $x_{i}$ that draw from a manifold $M_{l}$ with dimension $d_{l}$, under
the SMCE assumption, we can find a relative set of points
$\mathcal{N}_{i}={x_{j},j\neq i}$ from $M_{l}$ but contains only a small
number of non-zero elements that passes through $x_{i}$. This assumption can
be mathematically defined with Equation 11

$\|c_{i}[x_{1}-x_{i},...,x_{P}-x_{i}]\|_{2}\leq\epsilon,\ s.t\
\textbf{1}^{T}c_{i}=\textbf{1}$ (11)

where $c_{i}$ contains only a few non-zero entries that denote the indices of
the data point that are the sparse neighbors of $x_{i}$ from the same
manifold, $\textbf{1}^{T}c_{i}=\textbf{1}$ is the affine constraint and $P$
represent the number of all the points lie in the entire manifold.

We apply the sparse neighbors estimation to find the underlying local
subspaces in our transformed global subspace. As shown in Figure 3, with the
6-nearest neighbors estimation, there are four triangles have been selected to
span the same local subspace with observed data $\alpha_{i}$, because they are
near to $\alpha_{i}$ than the other circles. While, the sparse neighbors
estimation is looking for only a small number of data point that close to
$\alpha_{i}$, in this way most of the intersection area between the different
local subspaces can be eliminated. In particular, we constraint the searching
area of the sparse neighbors for each projected trajectory from the global
subspace with calculating the normalized subspace inclusion (NSI) distances
[19] between them. NSI can give us a robust measurement between the orthogonal
projected vectors based on their geometrically consistent, which is formulated
as

$NSI_{ij}=\frac{tr\\{\alpha_{i}^{T}\alpha_{j}\alpha_{j}^{T}\alpha_{i}\\}}{\min(\dim(\alpha_{i}),\dim(\alpha_{j}))}$
(12)

where the input is the projected trajectory matrix $\widetilde{W}_{m\times
P}=[\alpha_{1},...,\alpha_{P}]$, and $\alpha_{i}$ and $\alpha_{j},i,j=1,...,P$
represent two different projected data. The reason of using NSI distances to
constraint the sparse neighbors searching area is the geometric property of
the projected global subspace. Nevertheless the data vectors which are very
far away from $\alpha_{i}$ definitely can not span the same local subspace
with $\alpha_{i}$. Moreover, in addition to save computation times, the
selection for the searching area with NSI distances is more flexible, which
has a wide range of values, than tuning the fixed parameter K for nearest
neighbors.

Furthermore, all the NSI distances are stacked into a vector
$X_{i}=[NSI_{i1},...,NSI_{iP}]^{T}$, the assumption from SMCE in Equation 11
can be solved with a weighted sparse $\mathcal{L}_{1}$ optimization under
affine constraint, which is formulated as following

$\displaystyle\min\|Q_{i}c_{i}\|_{1}$ (13) $\displaystyle s.t\
\|X_{i}c_{i}\|_{2}\leq\epsilon,1^{T}c_{i}=1$

where $Q_{i}$ is a diagonal weight matrix and defined as
$Q_{i}=\frac{exp(X_{i}/\sigma)}{exp(\sum_{t}\neq
iX_{it})/\sigma}\in(0,1],\sigma>0$. The effect of the positive-definite matrix
$Q_{i}$ is encouraging the selection of the closest points for the projected
data $\alpha_{i}$ with a small weight, which means a lower penalty, but the
points that are far away to $\alpha_{i}$ will have a larger weight, which
favours the zero entries in solution $c_{i}$. We can use the same strategy as
SMCE to solve the optimization problem in Equation 13 with Alternating
direction method of multipliers (ADMM) [20].

As a result, we can obtain the sparse solutions $C_{P\times
P}=[c_{1},...,c_{P}]^{T}$ with a few number of non-zero elements that contain
the informations and connections between the projected data point and its
estimated sparse neighborhoods. As investigated in SMCE [18], in order to
build the affinity matrix with sparse solution $C_{P\times P}$ we can
formulate a sparse weight matrix $\Omega_{P\times P}$ with vector
$\omega_{i}$, which is built by
$\omega_{ii}=0,\omega_{ij}=\frac{c_{ij}/X_{ij}}{\sum_{t\neq
i}c_{it}/X_{ti}},j\neq i$. The achieved weight matrix $\Omega_{P\times P}$
contains only a few non-zero entries in column, which give the indices of all
the estimated sparse neighbors and the distances between them. Hence, we can
collect each data $\alpha_{i}$ and its estimated sparse neighbors
$\mathcal{N}_{i}$ into one local subspace $\widehat{S_{i}}$ according to the
non-zero elements of $\omega_{i}$.

###  IV-C Error Estimation

Although the sparse neighbors optimization can help us to avoid the
intersection between different local subspaces, it turned into quite sensitive
and can’t ensure to carry all the information about the underlying local
subspaces under the missing data situation. The local subspace estimation
after the sparse neighbors searching can be illustrated with Figure 4. In
Figure 4 the estimated local subspaces are not completely spanned by each
observed data and its corresponding sparse neighborhood. Obviously, there are
some neighbors have been estimated to span two different local subspaces,
which can be called the overlapping estimation. Moreover, the obtained local
subspaces with some overlapping problems cannot carry the enough dissimilarity
or similarity information between two local subspaces, which can be used to
build an affinity matrix that can separate the different subspaces with
spectral clustering.

Figure 4: The geometrical illustration of incorrect local subspace estimation
with sparse neighbors. $S_{1},S_{2},S_{3},S_{4}$ are four estimated local
subspaces spanned by the observed data
$\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}$ respectively.

For purpose of estimating these overlapping and making a strong connection
between the data points from the same local subspace, we propose the following
error function with Equation 14

$e_{it}=\|(I-\widehat{\beta_{i}}\widehat{\beta_{i}}^{+})\alpha_{t}\|_{2}^{2},t=1,...,P$
(14)

where $\widehat{\beta_{i}}\in R^{m\times m_{i}}$ is the basis of estimated
local subspace $\widehat{S_{i}},m_{i}=rank(\widehat{S_{i}})$, which can be
achieved through the SVD of $\widehat{S_{i}}$, and $\widehat{\beta_{i}}^{+}$
is the Moore-Penrose inverse of $\widehat{\beta_{i}}$, the $I\in R^{m\times
m}$ is an identity matrix. Actually the geometrical meaning of the error
function $e_{it}$ is the distance between the estimated local subspace and
projected data. More specifically, if the projected data $\alpha_{t}$ truly
comes from the local subspace $\widehat{S_{i}}$, the corresponding error
$e_{it}$ should have a very small value, which ideally is near to zero, and
vice versa. As a consequence, after computing for each estimated local
subspace $\widehat{S_{i}}$ its corresponding error vector
$e_{i}=[e_{i}1,...,e_{i}P]$, we can build an error matrix $\mathbf{e}_{P\times
P}=[e_{1},...,e_{P}]$, which contains the strong connection between the
projected data span a same local subspace.

In the end, we can construct our affinity graph $\mathcal{G}=(V,E)$ with
combining the estimated error matrix $\mathbf{e}_{P\times P}$ and the sparse
weight matrix $\Omega_{P\times P}$, whose the nodes $V$ represent all the
projected data points and edges $E$ denote the distances between them. In our
affinity graph, the connection between each two nodes $\alpha_{i}$ and
$\alpha_{j}$ is determined by both the $e_{ij}$ and $\omega_{ij}$. Therefore,
our constructed affinity graph contains only several connected elements, which
are related to the data points span the same subspace, whereas there is no
connection between the data points live in a different subspace. More
formally, the adjacent matrix of the affinity graph is formulated as follows

$\displaystyle A[i]=|\omega_{i}|+|{e}_{i}|$ (15)
$\displaystyle\mathcal{A}=\left[\begin{array}[]{cccc}A[1]&0&...&0\\\
0&A[2]&...&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&...&A[P]\end{array}\right]\Gamma$

where the $\Gamma\in R^{P\times P}$ is an arbitrary permutation matrix.
Subsequently, we can perform the normalized spectral clustering [21] on the
symmetric matrix $\mathcal{A}$ and obtain the final clusters with different
labels, and each cluster is related to one moving object.

##  V Experimental Results

Our proposed framework is evaluated on both the Hopkins 155 dataset [2] and
the Freiburg-Berkeley Motion Segmentation Dataset [4] with comparing with
state-of-the-art subspace clustering and affinity-based motion segmentation
algorithms.

Implementation Details Most popular subspace based motion segmentation methods
[5, 10, 6, 3, 4] have assumed that the number of motions has been already
known. For the Hopkins 155 dataset, we give the exactly number of clusters
according to the number of motions, while for the Berkeley dataset we set the
number of clusters with 7 for all the test sequences. In this work, the
constrained area for searching the sparse neighbors is firstly varied in a
range variables $[10,20,30,50,100]$, then it turns out that the tuned
constrained area performs equally well from 20 to 50, so we choose to set the
number with 20, which according to the alternative number of sparse numbers.
In our experiments, we have applied the PCA and sparse PCA for evaluating the
performance of our framework on estimating the multiple local subspaces from a
general global subspace with dimension $m=5$. The sparsity controlling
parameter for sparse PCA is setted to $\gamma=0.01$ and the distinct parameter
vector $[\mu_{1},...,\mu_{m}]$ is setted to $[1/1,1/2,...,1/m]$.

###  V-A The Hopkins 155 Dataset

The Hopkins 155 dataset [2] contains 3 different kinds sequences:
checkerboard, traffic and articulated. For each of them, the tracked feature
trajectories are already been provided in the ground truth and the missing
features are removed as well, which means the trajectories in the Hopkins 155
dataset are fully observed and there is no missing data. We have computed the
average and median misclassification error for comparison our method with
state-of-the-art methods: SSC [5], LSA [10], ALC [6]and MSMC [3], as shown in
Table I, Table II, Table III. Table IV refers to the run times of our method
comparing with two sparse optimization based methods: ALC and SSC.

Method | ALC | SSC | MSMC | LSA |  Ourpca |  Ourspca
---|---|---|---|---|---|---
Articulated, 11 sequences
mean | 10.70 | 0.62 | 2.38 | 4.10 | 2.67 | 0.55
median | 0.95 | 0.00 | 0.00 | 0.00 | 0.00 | 0.00
Traffic, 31 sequences
mean | 1.59 | 0.02 | 0.06 | 5.43 | 0.2 | 0.48
median | 1.17 | 0.00 | 0.00 | 1.48 | 0.00 | 0.00
Checkerboard, 78 sequences
mean | 1.55 | 1.12 | 3.62 | 2.57 | 1.69 | 0.56
median | 0.29 | 0.00 | 0.00 | 0.27 | 0.00 | 0.00
All 120 sequences
mean | 2.40 | 0.82 | 2.62 | 3.45 | 1.52 | 0.53
median | 0.43 | 0.00 | 0.00 | 0.59 | 0.00 | 0.00
TABLE I: Mean and median of the misclassification (%) on the Hopkins 155 dataset with 2 motions. Method | ALC | SSC | MSMC | LSA |  Ourpca |  Ourspca
---|---|---|---|---|---|---
Articulated, 2 sequences
mean | 21.08 | 1.91 | 1.42 | 7.25 | 3.72 | 3.19
median | 21.08 | 1.91 | 1.42 | 7.25 | 3.72 | 3.19
Traffic, 7 sequences
mean | 7.75 | 0.58 | 0.16 | 25.07 | 0.19 | 0.72
median | 0.49 | 0.00 | 0.00 | 5.47 | 0.00 | 0.19
Checkerboard, 26 sequences
mean | 5.20 | 2.97 | 8.30 | 5.80 | 5.01 | 1.22
median | 0.67 | 0.27 | 0.93 | 1.77 | 0.78 | 0.55
All 35 sequences
mean | 6.69 | 2.45 | 3.29 | 9.73 | 2.97 | 1.94
median | 0.67 | 0.20 | 0.78 | 2.33 | 1.50 | 1.30
TABLE II: Mean and median of the misclassification (%) on the Hopkins 155 dataset with 3 motions. Method | ALC | SSC | MSMC | LSA |  Ourpca |  Ourspca
---|---|---|---|---|---|---
all 155 sequences
Mean | 3.56 | 1.24 | 2.96 | 4.94 | 1.98 | 0.70
Median | 0.50 | 0.00 |  | 0.90 | 0.75 | 0.00
TABLE III: Mean and median of the misclassification (%) on all the Hopkins 155 dataset. Method | ALC | SSC |  OurPCA |  OurSPCA
---|---|---|---|---
Run-time [s] | 88831 | 14500 | 1066 | 1394
TABLE IV: Computation-Time (s) on all the Hopkins 155 dataset.

Obviously, as Table I and Table II show, the overall error rate of ours with
sparse PCA projection is the lowest for both 2 and 3 motions. Generally, the
PCA projection has a lower accuracy than sparse PCA projection for the
articulated and checkerboard sequences. However, the traffic video with PCA
projection reaches a better result than the sparse PCA projection, which gives
us a conclusion that PCA is more robust to represent the rigid motion
trajectory matrix, but the sparse PCA projection can better represent the
trajectory matrix of independent or non-rigid motions. We also notice that
MSMC performs the best for the traffic sequence with 3 motions, but our work
with PCA projection is just slightly worse to MSMC and inferior to SSC, which
is one of the most accurate subspace-based algorithm. But due to the property
of MSMC, which is based on computing the affinities between each pair
trajectories, it is highly time-consuming. The checkerboard data is the most
significant component for the entire Hopkins dataset, which in particular
contains a lot of features points and many intersection problems between
different motions. To be specific, the most accurate results for the
checkerboard sequences belong to our proposed framework with sparse PCA
projection, either for two or three motions. It means that our method has the
most accuracy for clustering different intersected motions. Table III shows
our method achieves the least misclassification error for all the sequences
from the Hopkins dataset in comparison with all the other algorithms. Although
our method with sparse PCA or PCA projection is a bit loss of precision for
the traffic sequences, we save a lot of computation times comparing with SSC
and ALC as shown in Table IV. We evaluate our method with sparse PCA
projection in comparison with LSA [10], SSC [5], MSMC [3], GPCA [8], RANSAC
[9] and MSMC [3] in Figure 5 and Figure 6 on the Hopkins 155 dataset. Note
that MSMC has not been evaluated on the checkboard sequence.

Figure 5: Comparison of Our approach with ground truth and the other
approaches on the 1RT2RC video: 5: GroudTruth; 5: GPCA, error: $44.98\%$; 5:
LSA, error:$1.94\%$; 5: RANSAC, error: $33.66\%$; 5: SSC, $0\%$; 5: Our, $0\%$
on the 1RT2TC sequence from the Hopkins 155 dataset.

Figure 6: Comparison of Our approach with ground truth and the other
approaches on the 1RT2RC video: 6: GroudTruth; 6: GPCA, error: $19.34\%$; 6:
LSA, error:$46.23\%$; 6 MSMC, error: $46.23\%$; 6 SSC, $0\%$; 6: Our, $0\%$.

###  V-B Freiburg-Berkeley Motion Segmentation Dataset

In this subsection, our method has been evaluated on the Freiburg-Berkeley
Motion Segmentation dataset [4] to test the performance on the real video
sequences with occlusion and moving camera problems. This dataset contains 59
sequences and all the feature trajectories are tracked densely. All the
missing trajectories have not been removed and there is no pre-processing for
correcting the error tracked trajectory. The parameters for evaluation are
precision (%) and recall (%). Our method has been compared with Ochs [4],
which is based on the affinity of the trajectories between each two frames,
SSC [5] and ALC [6]. The results on all the training set and test set of the
Berkeley dataset are shown in Table V.

| Ochs | ALC | SSC |  Ourpca |  Ourspca
---|---|---|---|---|---
Precision | 82.36 | 55.78 | 64.55 | 72.12 | 70.77
Recall | 61.66 | 37.43 | 33.45 | 66.52 | 65.42
TABLE V: Results on the entire Freiburg-Berkeley Motion Segmentation Dataset
[4].

Figure 7: Our segmentation results on Freiburg-Berkeley Motion Segmentation
Dataset in comparison with the groundtruth segmentations from [4]. 7:bear01,
7: marple4, 7: cars8. Figure 8: Additional segmentation results of Freiburg-
Berkeley Motion Segmentation Dataset [4].

In general, as shown in Table V, the PCA projection has a better performance
on this dataset than the sparse PCA, which can not deal with the data matrix
contains a lot of zero entries. More specifically, our method with PCA
projection obtains the most Recall value comparing with the others, which
indicates our assigned clusters can cover the most parts of the different
ground-truth regions. However, compared with Ochs [4], which is based on the
affinity, our method lacks the precision. It means that our method can detect
the boundaries of different regions but can not complete segment the moving
objects from the background. Figure 7 show us the examples of our results with
PCA projection. Among all of these examples, our method has high quality
segmentations of the primary foreground moving objects, which according to to
the high recall value. However, there are some incorrect segmentations as
well, such as the features on the object cannot be distinguished exactly
especially at the last few frames. These incomplete segmentation results
indicate the small precision value in Table V. Among all of the subspace-based
motion segmentation algorithms SSC and ALC, which need to firstly apply the
sparse reconstruction for the incomplete trajectories, our method only depends
on the error estimation and sparse neighbors technique but has a superior
performance on the precision and recall.

Figure 8 show us some additional segmentation results. The typical failure
segmentations are shown in the bottom row marple1.avi, which contains 300
frames. Our method can not exactly extract the moving objects from the
background for the video that has the really long observed frames. Moreover
our method can not segment the video accurately when the camera is also
moving, due to the moving foreground usually has the short feature
trajectories that are very difficult to handle.

##  VI Conclusions

In this paper, we have proposed a subspace-based framework for segmenting
multiple moving objects from a video sequence with integrating global and
local sparse subspace optimization methods. The sparse PCA performs a data
projection from a high-dimensional subspace to a global subspace with sparse
orthogonal principal vectors. To avoid improperly choosing K-nearest neighbors
and defend intersection between different local subspaces, we seek a sparse
representation for the nearest neighbors in the global subspace for each data
point that span a same local subspace. Moreover, we propose an error
estimation to refine the local subspace estimation for the missing data. The
advantage of the proposed method is that we can apply two sparse optimizations
and a simple error estimation to handle the incorrect local subspace
estimation under the missing trajectories. The limitation of our work is the
number of motions should be known firstly and only a constrained number of
missing data can be handled accurately. The experiments on the Hopkins and
Berkeley dataset show our method are comparable with state-of-the-art methods
in terms of accuracy, and sometimes exceeds them on both precision and
computation time.

## Acknowledgements

The work is funded by DFG (German Research Foundation) YA 351/2-1 and the ERC-
Starting Grant (DYNAMIC MINVIP). The authors gratefully acknowledge the
support.

## References

  * [1] M. Y. Yang and B. Rosenhahn, “Video segmentation with joint object and trajectory labeling,” in _IEEE Winter Conference on Applications of Computer Vision_ , 2014, pp. 831–838.
  * [2] R. Tron and R. Vidal, “A benchmark for the comparison of 3-d motion segmentation algorithms,” in _CVPR_ , 2007, pp. 1–8.
  * [3] R. Dragon, B. Rosenhahn, and J. Ostermann, “Multi-scale clustering of frame-to-frame correspondences for motion segmentation,” in _ECCV_ , 2012, pp. 445–458.
  * [4] P. Ochs, J. Malik, and T. Brox, “Segmentation of moving objects by long term video analysis,” _PAMI_ , vol. 36, no. 6, pp. 1187–1200, 2014.
  * [5] E. Elhamifar and R. Vidal, “Sparse subspace clustering,” in _CVPR_ , 2009, pp. 2790–2797.
  * [6] Y. Ma, H. Derksen, W. Hong, and J. Wright, “Segmentation of multivariate mixed data via lossy data coding and compression,” _PAMI_ , vol. 29, no. 9, pp. 1546–1562, 2007.
  * [7] H. Zou, T. Hastie, and R. Tibshirani, “Sparse principal component analysis,” _Journal of computational and graphical statistics_ , vol. 15, no. 2, pp. 265–286, 2006.
  * [8] R. Vidal, Y. Ma, and S. Sastry, “Generalized principal component analysis (gpca),” _PAMI_ , vol. 27, no. 12, pp. 1945–1959, 2005.
  * [9] M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography,” _Communications of the ACM_ , vol. 24, no. 6, pp. 381–395, 1981.
  * [10] J. Yan and M. Pollefeys, “A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate,” in _ECCV_ , 2006, pp. 94–106.
  * [11] K. Kanatani, “Motion segmentation by subspace separation and model selection,” in _ICCV_ , 2001, pp. 586–591.
  * [12] H. Abdi and L. J. Williams, “Principal component analysis,” _Wiley Interdisciplinary Reviews: Computational Statistics_ , vol. 2, no. 4, pp. 433–459, 2010.
  * [13] T. Zhou, D. Tao, and X. Wu, “Manifold elastic net: a unified framework for sparse dimension reduction,” _Data Mining and Knowledge Discovery_ , vol. 22, no. 3, pp. 340–371, 2011.
  * [14] N. Naikal, A. Y. Yang, and S. S. Sastry, “Informative feature selection for object recognition via sparse pca,” in _ICCV_ , 2011, pp. 818–825.
  * [15] M. Journée, Y. Nesterov, P. Richtárik, and R. Sepulchre, “Generalized power method for sparse principal component analysis,” _The Journal of Machine Learning Research_ , vol. 11, pp. 517–553, 2010.
  * [16] A. Goh and R. Vidal, “Segmenting motions of different types by unsupervised manifold clustering,” in _CVPR_ , 2007, pp. 1–6.
  * [17] L. Zappella, X. Lladó, E. Provenzi, and J. Salvi, “Enhanced local subspace affinity for feature-based motion segmentation,” _Pattern Recognition_ , vol. 44, no. 2, pp. 454–470, 2011.
  * [18] E. Elhamifar and R. Vidal, “Sparse manifold clustering and embedding,” in _NIPS_ , 2011, pp. 55–63.
  * [19] N. P. da Silva and J. P. Costeira, “The normalized subspace inclusion: Robust clustering of motion subspaces,” in _ICCV_ , 2009, pp. 1444–1450.
  * [20] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” _Foundations and Trends in Machine Learning_ , vol. 3, no. 1, pp. 1–122, 2011.
  * [21] U. Von Luxburg, “A tutorial on spectral clustering,” _Statistics and computing_ , vol. 17, no. 4, pp. 395–416, 2007.