ba.lyx

#LyX 2.1 created this file. For more info see http://www.lyx.org/
\lyxformat 474
\begin_document
\begin_header
\textclass scrartcl
\begin_preamble
\usepackage{fancyhdr}
\pagestyle{fancyplain}
\fancyhf{}
\end_preamble
\use_default_options true
\begin_modules
theorems-ams
eqs-within-sections
figs-within-sections
algorithm2e
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman charter
\font_sans default
\font_typewriter default
\font_math auto
\font_default_family rmdefault
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement h
\paperfontsize default
\spacing onehalf
\use_hyperref true
\pdf_title "PCCA+ and its application to spatial timeseries clustering"
\pdf_author "Alexander Sikorski"
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize a4paper
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 3cm
\topmargin 3cm
\rightmargin 3cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Bachelor Thesis
\shape up

\begin_inset Newline newline
\end_inset


\shape default

\begin_inset VSpace 1cm*
\end_inset


\shape up
PCCA+ and its Application 
\begin_inset Newline newline
\end_inset

to Spatial Time Series Clustering
\begin_inset VSpace 1cm*
\end_inset


\end_layout

\begin_layout Subtitle
\begin_inset Graphics
	filename siegel.png
	width 7cm

\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset VSpace 1cm*
\end_inset

Free University of Berlin
\begin_inset Newline newline
\end_inset

Department of Mathematics and Computer Science
\begin_inset VSpace 1cm*
\end_inset


\end_layout

\begin_layout Author
Alexander Sikorski
\begin_inset Newline newline
\end_inset

Supervisor: PD Dr.
 Marcus Weber
\end_layout

\begin_layout Date
March 18th, 2015
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Section*
Declaration
\end_layout

\begin_layout Standard
I hereby declare that this thesis is my own work and has not been submitted
 in any form for another degree or diploma at any university or other institute.
 Information derived from the published and unpublished work of others has
 been acknowledged in the text and a list of references is given.
 
\end_layout

\begin_layout Standard
\begin_inset VSpace 2cm
\end_inset


\end_layout

\begin_layout Standard
\begin_inset CommandInset line
LatexCommand rule
offset "0.5ex"
width "100col%"
height "1pt"

\end_inset


\end_layout

\begin_layout Standard
Alexander Sikorski
\end_layout

\begin_layout Standard
Berlin, March 18th, 2015
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\begin_inset CommandInset toc
LatexCommand tableofcontents

\end_inset


\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setcounter{page}{1}
\backslash
fancyhf[FRO,FLE]{
\backslash
thepage}
\end_layout

\begin_layout Plain Layout


\backslash
fancyhead[LO]{
\backslash
leftmark}
\end_layout

\begin_layout Plain Layout


\backslash
fancyhead[RE]{
\backslash
rightmark} 
\end_layout

\end_inset


\end_layout

\begin_layout Section

\shape up
Introduction
\end_layout

\begin_layout Standard
In this thesis, we develop an algorithm for clustering spatial time series
 into a prescribed number of clusters based on their spatial and dynamical
 properties.
\end_layout

\begin_layout Standard
After an introduction to the underlying theoretical background we will review
 known results about the 
\emph on
Robust Perron Cluster Cluster Analysis
\emph default
 (PCCA+), which forms the basis for our application.
 PCCA+ allows to identify metastable clusters in Markov chains which are
 configurations of the system which are likely to persist for a longer time.
 In the course, we will extend the known results by a stochastic interpretation
 for the propagator matrix which encodes the time evolution on the clusters.
\end_layout

\begin_layout Standard
We then explain a method to turn spatial time series into a Markov chain
 to obtain a spatial clustering by further application of PCCA+, respecting
 the dynamic information.
 Finally, we will apply that method to data obtained by tracking human eye
 fixations while these look at different paintings to detect the depicted
 objects.
 This can be seen as a form of object recognition which does not rely on
 the image data itself but detects the objects based on the human recognition
 reflected in their eye movement.
\end_layout

\begin_layout Standard
The presented program was developed in cooperation with the Zuse Institute
 Berlin and the University of Potsdam and I would like to thank Dr.
 Weber and Prof.
 Dr.
 Kliegl for their support.
\end_layout

\begin_layout Section

\shape up
Theoretical background
\end_layout

\begin_layout Subsection
Introduction to Markov chains
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $S$
\end_inset

 be any finite set, i.e.
 
\begin_inset Formula $S:=\left\{ s_{1},...,s_{N}\right\} $
\end_inset

.
 A 
\emph on
Markov chain
\emph default
 on 
\begin_inset Formula $S$
\end_inset

 is a stochastic process, consisting of a sequence of random variables 
\begin_inset Formula $X_{i}:\Omega\rightarrow S$
\end_inset

, 
\begin_inset Formula $i\in\mathbb{N}$
\end_inset

 satisfying the Markov property: 
\begin_inset Formula 
\[
P(X_{t+1}=x|X_{1}=x_{1},X_{2}=x_{2},...,X_{t}=x_{t})=P(X_{t+1}=x|X_{t}=x_{t})\,\forall t\in\mathbb{N}.
\]

\end_inset

It is common to interpret 
\begin_inset Formula $S$
\end_inset

 as the state space of possible outcomes of measurements at time step 
\begin_inset Formula $t$
\end_inset

 represented by 
\begin_inset Formula $X_{t}$
\end_inset

.
 The Markov property assures that the transition probabilities to the next
 time step 
\begin_inset Formula $x{}_{t+1}$
\end_inset

 only depend on the current state 
\begin_inset Formula $x_{t}$
\end_inset

.
 This means that the process at time 
\begin_inset Formula $t$
\end_inset

 has no memory of its previous history 
\begin_inset Formula $(x_{1},...,x_{t-1})$
\end_inset

, sometimes this is also called the memoryless property.
\end_layout

\begin_layout Standard
We will furthermore assume that the process is autonomous, i.e.
 not explicitly depending on the time:
\begin_inset Formula 
\[
P(X_{t+1}=x|X_{t}=y)=P(X_{t}=x|X_{t-1}=y)\forall t\in\mathbb{N}.
\]

\end_inset

This does not really impose a restriction since any non-autonomous process
 can be turned into an autonomous one: By adding all possible times to the
 state space 
\begin_inset Formula $S$
\end_inset

 using the Cartesian product 
\begin_inset Formula $S':=\mathbb{N}\times S$
\end_inset

, the explicit time-dependence of the process on 
\begin_inset Formula $S$
\end_inset

 can be implicitly subsumed by an autonomous process on 
\begin_inset Formula $S'$
\end_inset

.
\end_layout

\begin_layout Standard
Since 
\begin_inset Formula $S$
\end_inset

 is finite, we can, enumerating all states in 
\begin_inset Formula $S$
\end_inset

, encode the whole process in the right stochastic 
\emph on
transition matrix
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
P_{ij}:=P\left(X_{t+1}=j|X_{t}=i\right),
\]

\end_inset

in which case right stochastic means that each row has row sum one and propagati
on of states is realized by right application of 
\begin_inset Formula $P$
\end_inset

.
\end_layout

\begin_layout Standard
A 
\emph on
stationary distribution
\emph default
 is a row vector 
\begin_inset Formula $\pi$
\end_inset

, satisfying
\begin_inset Formula 
\[
\pi P=\pi,\,\sum_{i=1}^{N}\pi_{i}=1.
\]

\end_inset


\end_layout

\begin_layout Standard
Given a stationary distribution 
\begin_inset Formula $\pi$
\end_inset

, we denote by 
\begin_inset Formula $D_{\pi}$
\end_inset

 the diagonal matrix with 
\begin_inset Formula $\pi$
\end_inset

 on its diagonal.
\end_layout

\begin_layout Standard
Although we only consider a discrete state space in this thesis, the results
 are extendible to continuous state spaces as well.
 A natural way is using a set-based discretization dividing the state space
 into a finite mesh of subsets.
 For high dimensional state spaces, as for example met in molecular dynamics,
 this approach exhibits the curse of dimensionality, as the size of the
 mesh grows exponentially with the dimensions.
 Weber developed a meshless version of PCCA+ using a global Galerkin discretizat
ion
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

 as solution to this problem .
\end_layout

\begin_layout Subsection
Clustering of the state space
\end_layout

\begin_layout Standard
The goal of PCCA+ is to reduce the complexity of analysis of the Markov
 chain by a dimension reduction of the state space.
 To formalize this we will now introduce the concept of clustering, which
 is subsuming different states of the state space to a smaller set of 
\begin_inset Formula $n\in\mathbb{N}$
\end_inset

 clusters 
\begin_inset Formula $C:=\left\{ 1,...,n\right\} $
\end_inset

.
\end_layout

\begin_layout Standard
The simplest possibility is assigning each state 
\begin_inset Formula $k\in S$
\end_inset

 to a cluster 
\begin_inset Formula $i\in C$
\end_inset

 which can be encoded by means of the 
\emph on
characteristic vector
\emph default
 
\begin_inset Formula $\chi_{i}\in\left\{ 0,1\right\} ^{N}$
\end_inset

:
\begin_inset Formula 
\[
\chi_{i,k}=\begin{cases}
1, & \text{if state \ensuremath{k}}\text{ belongs to cluster }i\\
0, & \text{else }
\end{cases}.
\]

\end_inset

Due to its discrete nature, this 
\emph on
crisp clustering 
\emph default
approach, used by the 
\emph on
Perron Cluster Cluster Analysis
\emph default
 (PCCA) 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2000"

\end_inset

, has the disadvantage of not being robust against small perturbations since
 continuous changes in 
\begin_inset Formula $P$
\end_inset

 finally result in discontinuous changes in the clustering.
\end_layout

\begin_layout Standard
Deuflhard and Weber therefore developed a robust version, 
\emph on
Robust Perron Cluster Analysis
\emph default
 (PCCA+) 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005"

\end_inset

, by making use of a 
\emph on
fuzzy clustering
\emph default
 representing each cluster by an
\emph on
 almost characteristic vector 
\begin_inset Formula 
\begin{equation}
\chi_{i}\in\left[0,1\right]^{n}.\label{eq:pos}
\end{equation}

\end_inset


\emph default
A
\emph on
lmost characteristic vectors 
\begin_inset Formula $\left\{ \chi_{i}\right\} _{i=1}^{n}$
\end_inset


\emph default
 satisfying the partition of unity property
\begin_inset Formula 
\begin{equation}
\sum_{i=1}^{n}\chi_{i}=1\label{eq:pu}
\end{equation}

\end_inset

are called 
\emph on
membership vectors
\emph default
 as they describe the relative membership of each state to each cluster.
 We will refer to the matrix collection 
\begin_inset Formula $\chi:=\left(\chi_{i}\right)_{i=1}^{n}\in\mathbb{R}^{N\times n}$
\end_inset

 of the 
\emph on
membership vectors
\emph default
 as a 
\emph on
clustering
\emph default
, whereas in the field of computational chemistry it is also referred to
 as 
\emph on
conformations.
\end_layout

\begin_layout Subsection
Galerkin projection of the transition matrix
\end_layout

\begin_layout Subsubsection*
The coupling Matrix
\end_layout

\begin_layout Standard
To represent the dynamics on the reduced/clustered state space in the case
 of a 
\emph on
crisp clustering
\emph default
 
\begin_inset Formula $\chi$
\end_inset

, i.e.
 
\begin_inset Formula $\chi_{i}\in\left\{ 0,1\right\} $
\end_inset

, Deuflhard et al.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2000"

\end_inset

 introduced the 
\emph on
coupling matrix
\emph default
 
\emph on

\begin_inset Formula 
\[
W_{ij}:=\frac{\left\langle \chi_{j},P\chi_{i}\right\rangle _{\pi}}{\left\langle \chi_{i},1\right\rangle _{\pi}}=\frac{\chi_{j}^{T}D_{\pi}P\chi_{i}}{\pi^{T}\chi_{i}},
\]

\end_inset


\emph default
or in matrix notation
\begin_inset Formula 
\[
W:=\text{diag}\left(\chi^{T}\pi\right)^{-1}\chi^{T}D_{\pi}P\chi.
\]

\end_inset

The entries 
\begin_inset Formula $W_{ij}$
\end_inset

 can thus be interpreted as conditional transition probabilities from cluster
 
\begin_inset Formula $i$
\end_inset

 to cluster 
\begin_inset Formula $j$
\end_inset

, given the starting distribution 
\begin_inset Formula $\pi$
\end_inset


\emph on
.
\end_layout

\begin_layout Standard
In the 
\emph on
fuzzy clustering 
\emph default
setting, the problem arises that it is not clear anymore which state belongs
 to which cluster.
 It is therefore convenient to interpret the membership of state 
\begin_inset Formula $j$
\end_inset

 to cluster 
\begin_inset Formula $\chi_{i}$
\end_inset

, 
\begin_inset Formula $\chi_{ij}$
\end_inset

, as the probability of measuring state 
\begin_inset Formula $j$
\end_inset

 belonging to cluster 
\begin_inset Formula $\chi_{i}$
\end_inset

.
 Then, 
\begin_inset Formula $W_{ij}$
\end_inset

 denotes the expectation value for measuring cluster 
\begin_inset Formula $\chi_{j}$
\end_inset

 after propagating the density given by 
\begin_inset Formula $\chi_{i}$
\end_inset

.
\end_layout

\begin_layout Standard
Note, however, that even if no real transitions are actually happening in
 the state space, we still may count transitions between clusters since
 we measure the same state once belonging to one and then to another cluster,
 as demonstrated in example 3.
\end_layout

\begin_layout Standard
One of the main motivations for developing PCCA+ was the wish to identify
 so called 
\emph on
metastable
\emph default
 
\emph on
conformations
\emph default
 of molecular systems, e.g.
 to analyze the effectivity of active pharmaceutical ingredients in Computationa
l Molecular Design (for a overview over this approach see 
\begin_inset CommandInset citation
LatexCommand cite
key "Jan-HendrikPrinz2011"

\end_inset

).
 These 
\emph on
conformations
\emph default
 are 
\emph on
almost invariant
\emph default
 
\emph on
aggregates
\emph default
 of states, i.e.
 
\emph on
membership vectors
\emph default
 with high self-transition probabilities, guaranteeing that the system resides
 in these states on longer timescales.
\end_layout

\begin_layout Standard
This can be formalized, as proposed by Huisinga 
\begin_inset CommandInset citation
LatexCommand cite
key "Huising2001"

\end_inset

, by the definition of the 
\emph on
metastability 
\emph default
of 
\emph on
membership vectors 
\emph default
as the trace of the corresponding 
\emph on
coupling matrix
\emph default
: 
\begin_inset Formula $\text{tr}\left(W\right).$
\end_inset

 Note, this does not need to correspond with a high probability of the cluster.
\end_layout

\begin_layout Subsubsection*
The propagator matrix
\end_layout

\begin_layout Standard
Unfortunately, the projection via the 
\emph on
coupling matrix 
\emph default
does not commute with time propagation and therefore cannot be used for
 long term analyses of the underlying Markov chain.
\end_layout

\begin_layout Standard
As remedy, Kube and Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Kube2007"

\end_inset

 proposed the 
\emph on
coarse propagator matrix
\emph default
 
\emph on

\begin_inset Formula 
\begin{equation}
P_{C}:=\left(\chi^{T}D_{\pi}\chi\right)^{-1}\chi^{T}D_{\pi}P\chi\label{eq:pc}
\end{equation}

\end_inset


\emph default
which coincides with the 
\emph on
coupling matrix 
\begin_inset Formula $W$
\end_inset

 
\emph default
in the 
\emph on
crisp clustering
\emph default
 setting.
 Assuming that 
\begin_inset Formula $\chi$
\end_inset

 is a linear combination of vectors spanning a 
\begin_inset Formula $P$
\end_inset

-invariant subspace satisfying an invertibility condition, it has the advantage
 that discretization via 
\begin_inset Formula $\chi$
\end_inset

 and time propagation commute, i.e.
 
\begin_inset Formula 
\begin{equation}
P\chi=\chi P_{C}.\label{eq:com}
\end{equation}

\end_inset

This property ensures that the 
\emph on
coupling matrix 
\emph default
represents the right dynamics of the underlying Markov chain on the reduced
 state space, even for iterative application, i.e.
 
\begin_inset Formula $P^{n}\chi=\chi P_{C}^{n}$
\end_inset

.
\end_layout

\begin_layout Theorem
\begin_inset CommandInset label
LatexCommand label
name "thm:comm"

\end_inset

Let 
\begin_inset Formula $\chi=XA$
\end_inset

, 
\begin_inset Formula $X\in\mathbb{R}^{N\times n}$
\end_inset

, 
\begin_inset Formula $A\in\mathbb{R}^{n\times n}$
\end_inset

 satisfying the subspace condition
\begin_inset Formula 
\begin{equation}
PX=X\Lambda\label{eq:ss}
\end{equation}

\end_inset

for some 
\begin_inset Formula $\Lambda\in\mathbb{R}^{n\times n}$
\end_inset

 and 
\begin_inset Formula $C:=X^{T}D_{\pi}X$
\end_inset

 be invertible.
\end_layout

\begin_layout Theorem
Then the 
\begin_inset Formula $P_{C}$
\end_inset

 is conjugate to 
\begin_inset Formula $\Lambda$
\end_inset

 and 
\emph on
discretization-propagation commutativity
\emph default
 (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:com"

\end_inset

) holds
\emph on
.
\end_layout

\begin_layout Proof
We calculate
\begin_inset Formula 
\begin{eqnarray}
P_{C} & = & \left(\chi^{T}D_{\pi}\chi\right)^{-1}\chi^{T}D_{\pi}P\chi\nonumber \\
 & = & \left(A^{T}CA\right)^{-1}A^{T}C\Lambda A\nonumber \\
 & = & A^{-1}C^{-1}A^{-T}A^{T}C\Lambda A\nonumber \\
 & = & A^{-1}\Lambda A,\label{eq:conj}
\end{eqnarray}

\end_inset

which implies
\begin_inset Formula 
\[
P\chi=PXA=X\Lambda A=XAA^{-1}\Lambda A=\chi P_{C}.
\]

\end_inset


\end_layout

\begin_layout Standard
This form of the theorem constitutes a small generalization towards its
 so far published versions in which 
\begin_inset Formula $C=Id$
\end_inset

 was assumed instead of invertibility.
\end_layout

\begin_layout Subsubsection*
Stochastic interpretation
\end_layout

\begin_layout Standard
Due to the matrix inversion, the 
\emph on
propagator matrix
\emph default
 can have negative entries as shown in example 3 below, thus prohibiting
 a natural stochastic interpretation.
\end_layout

\begin_layout Standard
We will therefore shed some light into the connection between the 
\emph on
coupling- 
\emph default
and the 
\emph on
propagator matrix
\emph default
 making use of the notation of the 
\emph on
restriction
\emph default
- and 
\emph on
interpolation operators
\emph default
 introduced by Kube and Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Kube2007"

\end_inset

: 
\begin_inset Formula 
\begin{eqnarray*}
R:\mathbb{R}^{N} & \rightarrow & \mathbb{R}^{n},\, x\mapsto x\chi\\
I:\mathbb{R}^{n} & \rightarrow & \mathbb{R}^{N},\, x\mapsto xD_{\tilde{\pi}}^{-1}\chi^{T}D_{\pi}
\end{eqnarray*}

\end_inset

with 
\begin_inset Formula $\tilde{\pi}=\pi R$
\end_inset

 and 
\begin_inset Formula $\chi$
\end_inset

 as above, where we apply them from the right in line with the used notation
 of right-stochastic matrices.
\end_layout

\begin_layout Standard
These provide the transformations between the (fine-grained) configuration
 space and the (coarse-grained) cluster space.
 These are in the sense that 
\begin_inset Formula $IRw=w$
\end_inset

, i.e.
 
\begin_inset Formula $I$
\end_inset

 reconstructs the fine-grained density lost by the restriction 
\begin_inset Formula $R$
\end_inset

 using the fine-grained stationary density.
\end_layout

\begin_layout Standard
This allows to reformulate the 
\emph on
coupling- 
\emph default
and 
\emph on
propagator matrix as
\begin_inset Formula 
\begin{eqnarray*}
W & = & IPR\\
P_{C} & = & \left(IR\right)^{-1}IPR.
\end{eqnarray*}

\end_inset


\end_layout

\begin_layout Standard
Now, consider the situation when setting 
\begin_inset Formula $P=Id$
\end_inset

 with a fuzzy clustering.
 Then 
\begin_inset Formula $W=IR=\tilde{D_{\pi}}^{-1}\chi^{T}D_{\pi}\chi\ne Id$
\end_inset

 as different clusters overlap.
 The result corresponds to the transitions which are introduced to the coarser
 system due to the overlap.
\end_layout

\begin_layout Standard
As this overlap would be applied on every iteration of 
\begin_inset Formula $W$
\end_inset

, it would lead to increased mixing between the states resulting in wrong
 long-term results.
 
\begin_inset Formula $P_{C}$
\end_inset

 grants the desired commutativity (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:com"

\end_inset

) by factoring out these transitions.
\end_layout

\begin_layout Standard
This also shows how we can compute a corresponding stochastically interpretable
 
\emph on
coupling matrix 
\emph default
for larger times corresponding to 
\begin_inset Formula $n$
\end_inset

 iterations, 
\begin_inset Formula $W_{n}$
\end_inset

, from the smaller matrix 
\begin_inset Formula $P_{c}$
\end_inset

:
\begin_inset Formula 
\[
W_{n}:=IP^{n}R=IRP_{C}^{n}.
\]

\end_inset


\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Subsection
Example Processes
\end_layout

\begin_layout Standard
To demonstrate the connections between the different projections we now
 will show some example systems.
\end_layout

\begin_layout Subsubsection*
Example 1: The decoupled system
\end_layout

\begin_layout Standard
Consider 
\begin_inset Formula 
\[
P=\left(\begin{array}{ccc}
\frac{1}{2} & \frac{1}{2} & 0\\
\frac{1}{2} & \frac{1}{2} & 0\\
0 & 0 & 1
\end{array}\right).
\]

\end_inset

In this ideal decoupled system we have two invariant subspaces spanned by
 the so called 
\emph on
Perron eigenvectors 
\emph default
with eigenvalue 1, the vectors 
\begin_inset Formula 
\[
\left(\begin{array}{c}
1\\
1\\
0
\end{array}\right)\text{ and }\left(\begin{array}{c}
0\\
0\\
1
\end{array}\right).
\]

\end_inset


\shape up
 These can be interpreted as a 
\shape default
\emph on
crisp clustering
\emph default
 and, assuming an equidistributed starting distribution, we can compute
 the, in the 
\emph on
crisp 
\emph default
case coinciding, matrices 
\begin_inset Formula 
\[
W=P_{C}=\left(\begin{array}{cc}
1 & 0\\
0 & 1
\end{array}\right).
\]

\end_inset


\end_layout

\begin_layout Subsubsection*
Example 2: The 3-pot
\end_layout

\begin_layout Standard
Next, we will consider the stationary Markov chain on three states with
 a 
\emph on
fuzzy clustering
\emph default
: 
\begin_inset Formula 
\[
P:=\left(\begin{array}{ccc}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{array}\right),\,\chi=\left(\begin{array}{cc}
1 & 0\\
\frac{1}{2} & \frac{1}{2}\\
0 & 1
\end{array}\right),\,\pi=\frac{1}{3}\left(\begin{array}{c}
1\\
1\\
1
\end{array}\right).
\]

\end_inset

According to our definitions we now compute 
\begin_inset Formula 
\[
P_{C}:=\left(\begin{array}{cc}
1 & 0\\
0 & 1
\end{array}\right),\, W=\frac{1}{6}\left(\begin{array}{cc}
5 & 1\\
1 & 5
\end{array}\right).
\]

\end_inset

 We thus observe that 
\begin_inset Formula $P_{C}$
\end_inset

 contains the expected stationary dynamics on the reduced state space while
 
\begin_inset Formula $W$
\end_inset

 accounts for the possible transitions of observing the second state once
 in cluster 1 and once in cluster 2, due to the overlap in the 
\emph on
clustering
\emph default
.
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Subsubsection*
Example 3: Negative entries
\end_layout

\begin_layout Standard
Let us now consider
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
P=\left(\begin{array}{cc}
0 & 1\\
1 & 0
\end{array}\right),\,\chi=\left(\begin{array}{cc}
1 & 0\\
\frac{1}{2} & \frac{1}{2}
\end{array}\right),\,\pi=\frac{1}{2}\left(\begin{array}{cc}
1 & 1\end{array}\right).
\]

\end_inset

Computation of the propagator matrix now leads to negative entries: 
\begin_inset Formula 
\[
P_{C}=\frac{1}{2}\left(\begin{array}{cc}
1 & 1\\
3 & -1
\end{array}\right).
\]

\end_inset

Let us first compute the propagation of the normalized density corresponding
 to 
\begin_inset Formula $\chi_{2}$
\end_inset

:
\begin_inset Formula 
\[
\left(0,1\right)\cdot P=\left(1,0\right),
\]

\end_inset

i.e.
 
\begin_inset Formula $s_{2}$
\end_inset

 is propagated to 
\begin_inset Formula $s_{1}$
\end_inset

.
 The corresponding computation on the cluster space is
\begin_inset Formula 
\[
\left(0,1\right)\cdot P_{C}=\frac{1}{2}\left(3,-1\right).
\]

\end_inset

Here, the negative entry amounts for the overlap of the clusters and is
 necessary to encode state 
\begin_inset Formula $s_{1}$
\end_inset

: As both clusters hold an amount of 
\begin_inset Formula $s_{2}$
\end_inset

 we use a linear combination to eliminate this.
 We thus may interpret 
\begin_inset Formula $P_{C}$
\end_inset

 acting to the basis of clusters eliminating the overlap.
\end_layout

\begin_layout Standard
We can calculate the corresponding density on the state space by applying
 the interpolation operator
\begin_inset Formula 
\[
I=\left(\begin{array}{cc}
\frac{2}{3} & \frac{1}{3}\\
0 & 1
\end{array}\right),\,\frac{1}{2}\left(3,-1\right)\cdot I=\left(1,0\right).
\]

\end_inset


\end_layout

\begin_layout Section

\shape up
PCCA+
\end_layout

\begin_layout Standard
In this section, we will construct the 
\emph on
Robust Perron Cluster Cluster Analysis 
\emph default
algorithm, introduced in 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005"

\end_inset

.
 We first will construct the matrix 
\begin_inset Formula $X$
\end_inset

 spanning the required invariant subspace and examine the possible linear
 transformations 
\begin_inset Formula $A$
\end_inset

 mapping these to a set of membership vectors.
 Finally, we propose different objectives to an optimization problem to
 specify a 
\begin_inset Quotes eld
\end_inset

good
\begin_inset Quotes erd
\end_inset

 solution.
\end_layout

\begin_layout Standard
Unlike previous treatises, we will not restrict ourselves to reversible
 processes and provide a more general version of PCCA+ using the Schur decomposi
tion thus reflecting the newest developments in 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2015"

\end_inset

.
 
\end_layout

\begin_layout Standard
Note, that we impose a fixed cluster number 
\begin_inset Formula $n$
\end_inset

.
 An overview over methods for estimating the cluster number based on different
 criteria is given by Röblitz, Weber
\begin_inset CommandInset citation
LatexCommand cite
key "Roeblitz2013"

\end_inset

.
\end_layout

\begin_layout Standard
PCCA+ will construct the clusters described by the 
\emph on
membership vectors
\emph default
 as a linear combination of eigenvectors.
 This guarantees that 
\begin_inset Formula $\chi$
\end_inset

 spans an invariant subspace, thus leading to preservation of the slow time-scal
es.
 By choosing the 
\begin_inset Formula $n<N$
\end_inset

 eigenvectors with the largest eigenvalues, one hopes to preserve the principal
 dynamics of 
\begin_inset Formula $P$
\end_inset

.
 A good indicator towards this goal is that eigenvectors with large eigenvalues
 represent conformations with a high degree of self-mapping.
 Deuflhard et al.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2000"

\end_inset

 have furthermore shown that the desired metastability is bounded from above
 by the sum of the chosen eigenvalues and for 
\begin_inset Formula $\epsilon$
\end_inset

-perturbations of the coupling of uncoupled Markov chains also from below
 by 
\begin_inset Formula $\sum\lambda_{i}-O\left(\epsilon^{2}\right)$
\end_inset

, justifying the choice of large eigenvalues.
\end_layout

\begin_layout Subsection
Subspace construction
\begin_inset CommandInset label
LatexCommand label
name "sub:constrXL"

\end_inset


\end_layout

\begin_layout Standard
For the construction of the invariant subspace, we make use of the
\emph on
 real Schur decomposition
\emph default
 decomposing a matrix 
\begin_inset Formula $P=Q\Lambda Q^{-1}$
\end_inset

 into a orthonormal
\emph on
 
\emph default
matrix 
\begin_inset Formula $Q$
\end_inset

, whose columns are called the 
\emph on
Schur vectors,
\emph default
 and an upper quasi-triangular (1-by-1 and 2-by-2 blocks on its diagonal)
 matrix 
\begin_inset Formula $\Lambda$
\end_inset

, called the 
\emph on
Schur form
\emph default
.
 The columns of 
\begin_inset Formula $Q$
\end_inset

 are called the Schur vectors of 
\begin_inset Formula $P$
\end_inset

.
 The eigenvalues of 
\begin_inset Formula $P$
\end_inset

 appear on the diagonal of 
\begin_inset Formula $\Lambda$
\end_inset

, where complex conjugate eigenvalues correspond to the 2-by-2 blocks.
\end_layout

\begin_layout Standard
Compute the Schur decomposition of 
\begin_inset Formula $\tilde{P}=D_{\pi}^{\frac{1}{2}}PD_{\pi}^{-\frac{1}{2}}$
\end_inset

.
 Then reorder the 
\emph on
Schur form 
\emph default
so that the upper left 
\begin_inset Formula $n\times n$
\end_inset

 block contains the 
\begin_inset Formula $n$
\end_inset

 largest eigenvalues, recomputing the corresponding 
\emph on
Schur vectors
\emph default
 using a Schur reordering algorithm 
\begin_inset CommandInset citation
LatexCommand cite
key "Kressner2006"

\end_inset

.
 Note, that in the case of complex conjugate eigenvalues we have to select
 or discard the whole 2-by-2 blocks.
 Let us denote the resulting 
\emph on
Schur form 
\emph default
and 
\emph on
-vectors 
\emph default
by 
\begin_inset Formula $\Lambda$
\end_inset

, 
\begin_inset Formula $\tilde{X}$
\end_inset

.
 Then, defining 
\begin_inset Formula $X=D_{\pi}^{-\frac{1}{2}}\tilde{X}$
\end_inset

 and inserting into 
\begin_inset Formula $\tilde{P}\tilde{X}=\tilde{X}\Lambda$
\end_inset

 leads to 
\begin_inset Formula $PX=X\Lambda$
\end_inset

.
 Furthermore, due to orthonormality of 
\begin_inset Formula $\tilde{X}$
\end_inset

, we have 
\begin_inset Formula $X^{T}D_{\pi}X=Id$
\end_inset

.
 So 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $\Lambda$
\end_inset

 satisfy the conditions for Theorem 
\begin_inset CommandInset ref
LatexCommand ref
reference "thm:comm"

\end_inset

.
\end_layout

\begin_layout Subsection
The feasible transformation set
\end_layout

\begin_layout Standard
Given the invariant subspace 
\begin_inset Formula $X$
\end_inset

, we will now examine the set of feasible matrices 
\begin_inset Formula $F_{A}\subset\mathbb{R}^{n\times n}$
\end_inset

 for the transformation 
\begin_inset Formula $A$
\end_inset

, leading to actual 
\emph on
membership vectors
\emph default
 
\begin_inset Formula $\chi:=XA$
\end_inset

.
 As 
\begin_inset Formula $P$
\end_inset

 is stochastic, the vector 
\begin_inset Formula $e=\left(1,...,1\right)^{T}$
\end_inset

 is mapped to itself and thus forms an eigenvector to eigenvalue one which
 for stochastic matrices also is the largest eigenvalue.
 By the reordering of 
\begin_inset Formula $X$
\end_inset

 and due to 
\begin_inset Formula $X^{T}D_{\pi}X$
\end_inset

, we have 
\begin_inset Formula $X_{i,1}=1,\, i=1,...,N$
\end_inset

.
 Thus, one can reformulate the 
\emph on
positivity
\emph default
 (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pos"

\end_inset

) and 
\emph on
partition of unity
\emph default
 (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pu"

\end_inset

) conditions in terms of the matrices X and A, leading to the following
 constraints for 
\begin_inset Formula $A$
\end_inset

:
\begin_inset Formula 
\begin{eqnarray}
A_{1,j} & \ge & -\sum_{k=2}^{n}X_{ik}A_{kj},\, i=1,...,N,\, j=1,...,n\,\left(\text{positivity}\right),\label{eq:fa}\\
A_{i,1} & = & \delta_{i,1}-\sum_{j=2}^{n}A_{ij},\, i=1,...,n\,\left(\text{partition of unity}\right)
\end{eqnarray}

\end_inset

Since these constraints are linear in 
\begin_inset Formula $A$
\end_inset

, the set 
\begin_inset Formula $F_{A}$
\end_inset

 is a convex polytope.
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename simplex2.png
	lyxscale 30
	width 10cm

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:simplex"

\end_inset

Schematic illustration of the linear transformation mapping the row vectors
 of the eigenvectors 
\begin_inset Formula $X$
\end_inset

 (points on the 
\begin_inset Formula $z=1$
\end_inset

 hyperplane) onto the standard 2-simplex.
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
Geometrically, one might think of the 
\begin_inset Formula $N$
\end_inset

 rows of the matrix 
\begin_inset Formula $\chi$
\end_inset

 as points in the space 
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset

 (see Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:simplex"

\end_inset

).
 The 
\emph on
positivity
\emph default
 (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pos"

\end_inset

) and 
\emph on
partition of unity
\emph default
 (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pu"

\end_inset

) conditions force these points to lie on the standard 
\begin_inset Formula $\left(n-1\right)$
\end_inset

-simplex 
\begin_inset Formula $\Delta$
\end_inset

.
 Now, if 
\begin_inset Formula $\chi^{T}=A^{T}X^{T}$
\end_inset

 this means that the matrix 
\begin_inset Formula $A$
\end_inset

 maps the 
\begin_inset Formula $N$
\end_inset

 rows of the eigenvector matrix 
\begin_inset Formula $X$
\end_inset

 to that simplex.
 As we have seen the first component of each row is 1, thus, all rows lie
 on the hyperplane with first component 1.
 They furthermore are contained in a bounded region, and thus we can map
 them linearly onto 
\begin_inset Formula $\Delta$
\end_inset

 via a linear map 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\begin_layout Standard
Thus, we directly see that the set 
\begin_inset Formula $F_{A}$
\end_inset

 is not empty.
 It furthermore is infinite, as we can always shrink the image further and
 it will still fit into 
\begin_inset Formula $\Delta.$
\end_inset


\end_layout

\begin_layout Subsection
Optimization
\end_layout

\begin_layout Standard
As we have the choice between infinitely many possible solutions for 
\begin_inset Formula $A\subset F_{A}$
\end_inset

, we will now specify and motivate different optimization objectives to
 choose a specific solution by the optimization problem.
\end_layout

\begin_layout Subsubsection*
Maximal scaling condition
\end_layout

\begin_layout Standard
Assuming (
\emph on
maximality assumption), 
\emph default
that the convex hull 
\begin_inset Formula $\text{co}\left(X\right)$
\end_inset

 of the rows of 
\begin_inset Formula $X$
\end_inset

 already has the form of an 
\begin_inset Formula $\left(n-1\right)$
\end_inset

-simplex, we can now choose 
\begin_inset Formula $A$
\end_inset

 uniquely (up to permutation) to map this exactly onto 
\begin_inset Formula $\Delta$
\end_inset

, which among all the ways of mapping 
\begin_inset Formula $X$
\end_inset

 into 
\begin_inset Formula $\Delta$
\end_inset

 gives us the highest distinctiveness between the resulting clusters.
 This assumption is equivalent to the situation that for each corner there
 exists a row getting mapped into that corner, i.e.
\begin_inset Formula 
\[
\max_{i=1..N}\chi_{ij}=1,\, j=1,...,n,
\]

\end_inset

justifying its name.
\end_layout

\begin_layout Standard
As in general the 
\emph on
maximality assumption
\emph default
 is not met, it seems natural to turn it into an optimization problem.
 This has been done in 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005,Weber2006"

\end_inset

 by imposing maximization of the 
\emph on
maximal scaling condition 
\begin_inset Formula 
\[
I_{1}\left(A\right):=\sum_{j=1}^{n}\max_{i=1..N}\chi_{ij}\le n_{C}.
\]

\end_inset


\end_layout

\begin_layout Standard
Assuming that the 
\emph on
maximality assumption
\emph default
 is almost met, i.e.
 
\begin_inset Formula $\max_{i=1..N}\chi_{ij}\approx1,\, j=1,...,n$
\end_inset

, Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

 proposes to determine the maximizing indices by the 
\emph on
index mapping algorithm
\emph default
 (Algorithm 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:ima"

\end_inset

), turning this convex optimization problem into a linear one:
\begin_inset Formula 
\[
I_{1}\left(A\right)=\sum_{i,j=1}^{n}X_{ind\left(X\right)_{j},i}A_{ij}
\]

\end_inset


\end_layout

\begin_layout Standard
In 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

, Weber furthermore shows that 
\begin_inset Formula $W_{jj}\le\max_{i=1..N}\chi_{ij}$
\end_inset

, which implies that 
\begin_inset Formula $I_{1}$
\end_inset

 is an upper bound for the metastability, which thus should be large.
\end_layout

\begin_layout Standard
Note, that this objective, ignoring the data points not being the maxima,
 cannot distinguish between differences in the interior of the convex hull,
 leading to possibly non-optimal transformation matrices 
\begin_inset Formula $A$
\end_inset

 as illustrated in Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:hexagon"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\align center
\begin_inset Graphics
	filename hexagon.png
	lyxscale 20
	width 10cm

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Mapping of 7 rows of the eigenvectors (affine hexagon with an interior point)
 to a 2-simplex.
 While 
\begin_inset Formula $I_{1}$
\end_inset

 cannot differentiate between the two mappings, 
\begin_inset Formula $I_{3}$
\end_inset

 will choose the first as it provides a crisper assignment of the interior
 point.
\begin_inset CommandInset label
LatexCommand label
name "fig:hexagon"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
Maximal metastability condition
\end_layout

\begin_layout Standard
Another choice might be optimizing directly towards a maximal metastability
 as done by Deuflhard and Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005,Weber2006"

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
I_{2}\left(A\right):=\text{trace}\left(W\right)=\sum_{i=1}^{n}\lambda_{i}\sum_{j=1}^{n}\frac{A_{ij}^{2}}{A_{1,j}}
\]

\end_inset

where they establish the latter equation making use of 
\begin_inset Formula $\pi_{i}=A_{1,i}$
\end_inset

 (
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

, Lemma 3.6).
\end_layout

\begin_layout Subsubsection*
Crispness objective
\end_layout

\begin_layout Standard
Röblitz 
\begin_inset CommandInset citation
LatexCommand cite
key "Roeblitz2013"

\end_inset

 argues that the stochastic interpretation of 
\begin_inset Formula $W$
\end_inset

 is not valid in the fuzzy setting, due to the overlap.
 Optimization of the trace of 
\begin_inset Formula $P_{C}$
\end_inset

 makes no sense as it is similar to 
\begin_inset Formula $\Lambda$
\end_inset

, see (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:conj"

\end_inset

), and therefore independent of 
\begin_inset Formula $A$
\end_inset

.
 She therefore suggests maximization of 
\begin_inset Formula 
\[
I_{3}:=\text{trace}\left(IR\right)=\sum_{i=1}^{n}\sum_{j=1}^{n}\frac{A_{ij}^{2}}{A_{1,j}}
\]

\end_inset

which is similar to the 
\emph on
maximal metastability condition
\emph default
 with the corresponding 
\begin_inset Formula $P$
\end_inset

 replaced by the identity.
\end_layout

\begin_layout Standard
Maximizing the trace minimizes the off-diagonal entries of 
\begin_inset Formula $IR$
\end_inset

 leading to the least amount of clustering-induced transitions and therefore
 to a as crisp as possible clustering.
\end_layout

\begin_layout Subsubsection*
Unconstrained Optimization
\end_layout

\begin_layout Standard
Due to the high number of inequality constraints (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:fa"

\end_inset

), solving these linear or convex problems may still be very time consuming.
 Following Deuflhard and Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005,Weber2006"

\end_inset

, we will now show how to turn this constrained into an unconstrained optimizati
on problem by enforcing the constraints after each iteration.
\end_layout

\begin_layout Standard
Define the set 
\begin_inset Formula $F_{A}^{'}$
\end_inset

 by the equality constraints 
\begin_inset Formula 
\begin{eqnarray}
A_{i,1} & = & \delta_{i,1}-\sum_{j=2}^{n}A_{ij},\, i=1,...,n\nonumber \\
A_{1,j} & = & -\min_{l=1,...,N}\sum_{i=2}^{n}X_{li}A_{ij},\, j=1,....,n.\label{eq:fap}
\end{eqnarray}

\end_inset

Comparing these equalities to (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:fa"

\end_inset

), one easily checks that 
\begin_inset Formula $F_{A}^{'}\subset F_{A}$
\end_inset

.
\end_layout

\begin_layout Standard
Now consider the following 
\emph on
feasibilization
\emph default
 
\emph on
algorithm
\emph default
 
\begin_inset Formula $F:\mathbb{R}^{\left(n-1\right)\times\left(n-1\right)}\twoheadrightarrow F_{A}^{'}$
\end_inset

, mapping any arbitrary matrix 
\begin_inset Formula $\left(\tilde{A}_{ij}\right)_{i,j=2,...,n}$
\end_inset

 to a feasible transformation matrix 
\begin_inset Formula $A$
\end_inset

 and thus enforcing the desired constraints:
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
RestyleAlgo{algoruled}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Above

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "alg:feas"

\end_inset

Feasibilization algorithm
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
For 
\begin_inset Formula $i=2,....,n$
\end_inset

 define 
\begin_inset Formula $\tilde{A}_{i,1}:=-\sum_{j=2}^{n}\tilde{A}_{ij}$
\end_inset


\end_layout

\begin_layout Enumerate
For 
\begin_inset Formula $j=1,...,n$
\end_inset

 define 
\begin_inset Formula $\tilde{A}_{1,j}:=-\min_{l=1,...,N}\sum_{i=2}^{n}X_{li}\tilde{A}_{ij}$
\end_inset


\end_layout

\begin_layout Enumerate
For 
\begin_inset Formula $i,j=1,...,n$
\end_inset

 define 
\begin_inset Formula $A_{ij}:=\frac{\tilde{A}_{ij}}{\sum_{j=1}^{k}\tilde{A}_{1,j}}$
\end_inset


\end_layout

\begin_layout Enumerate
Return A
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Steps 1 and 2 guarantee feasibility of 
\begin_inset Formula $\tilde{A}$
\end_inset

 with respect to (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:fap"

\end_inset

) for 
\begin_inset Formula $i=2,...,n$
\end_inset

 respectively 
\begin_inset Formula $j=1,...,n$
\end_inset

.
 As these equalities are linear in 
\begin_inset Formula $A$
\end_inset

, they are invariant under scalar multiplication and step 3 now furthermore
 assures the equality (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:fap"

\end_inset

) for 
\begin_inset Formula $i=1$
\end_inset

.
 Thus, 
\begin_inset Formula $F$
\end_inset

 indeed maps to 
\begin_inset Formula $F_{A}^{'}$
\end_inset

.
 Furthermore, taking any matrix 
\begin_inset Formula $A\in F_{A}^{'}$
\end_inset

, dropping the first row and column to get 
\begin_inset Formula $\tilde{A}$
\end_inset

 and computing 
\begin_inset Formula $F\left(\tilde{A}\right)=A$
\end_inset

, we see that 
\begin_inset Formula $F$
\end_inset

 is surjective.
\end_layout

\begin_layout Standard
As any objective function 
\begin_inset Formula $I_{i},\, i=1,2,3$
\end_inset

 is convex over 
\begin_inset Formula $F_{A}$
\end_inset

 it attains its maximum at one of the vertices 
\begin_inset Formula $v\left(F_{A}\right)$
\end_inset

, which are contained in 
\begin_inset Formula $F'_{A}$
\end_inset

 (for a proof see 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

, Lemma 3.5).
 Thus, we can also optimize the function 
\begin_inset Formula $F\circ I_{i}$
\end_inset

 over 
\begin_inset Formula $\mathbb{R}^{\left(n-1\right)\times\left(n-1\right)}$
\end_inset

 and have thereby transformed the constrained optimization problem in 
\begin_inset Formula $n^{2}$
\end_inset

 unknowns to an unconstrained in 
\begin_inset Formula $\left(n-1\right)^{2}$
\end_inset

 unknowns.
\end_layout

\begin_layout Standard
As the 
\emph on
feasibilization algorithm 
\emph default
is not differentiable, Deuflhard and Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Deuflhard2005"

\end_inset

 propose the use of the nonlinear simplex method of Nelder and Mead 
\begin_inset CommandInset citation
LatexCommand cite
key "Nelder1965"

\end_inset

 as local optimization routine.
\end_layout

\begin_layout Subsubsection*
Initial guess
\end_layout

\begin_layout Standard
Based on Weber and Galliat 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2002"

\end_inset

, we outline the
\emph on
 inner simplex algorithm
\emph default
 determining an initial guess for the matrix 
\begin_inset Formula $A$
\end_inset

 by constructing a simplex surrounding all row-points and then computing
 the transformation to the standard simplex, thus, turning the global into
 a local optimization problem.
\end_layout

\begin_layout Standard
The first step
\emph on
, 
\emph default
the 
\emph on
index mapping algorithm, 
\emph default
searches for the indices 
\begin_inset Formula $i_{j}$
\end_inset

 of the successively farthest linear independent rows.
 It starts by choosing the largest row vector as starting point and then
 iteratively adds the points with the largest distance to the hyperplane
 spanned by the chosen points so far:
\begin_inset VSpace bigskip
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Index mapping algorithm
\begin_inset CommandInset label
LatexCommand label
name "alg:ima"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
Find starting point: 
\begin_inset Formula $i_{1}:=\text{argmax}_{j\in C}\left\Vert X_{\cdot,j}\right\Vert _{^{2}}$
\end_inset


\end_layout

\begin_layout Enumerate
Translate to origin: For 
\begin_inset Formula $i\in S$
\end_inset

 set 
\begin_inset Formula $X_{i,\cdot}\mapsfrom X_{i,\cdot}-X_{i_{1},\cdot}$
\end_inset


\end_layout

\begin_layout Enumerate
For 
\begin_inset Formula $j=2,...,n$
\end_inset


\end_layout

\begin_deeper
\begin_layout Enumerate
Find index of the farthest point: 
\begin_inset Formula $i_{j}:=\text{argmax}_{j\in C}\left\Vert X_{\cdot,j}\right\Vert _{^{2}}$
\end_inset


\end_layout

\begin_layout Enumerate
Projection to hyperplane by Gram-Schmidt process: 
\begin_inset Formula $X\mapsfrom X-\frac{\text{XX_{i_{j},\cdot}^{T}\otimes X_{i_{j},\cdot}}}{\left\Vert X_{i_{j},\cdot}\right\Vert _{2}}$
\end_inset

 
\end_layout

\end_deeper
\begin_layout Enumerate
Return the indices 
\begin_inset Formula $i_{j}$
\end_inset


\end_layout

\end_inset


\begin_inset VSpace bigskip
\end_inset


\end_layout

\begin_layout Standard
The 
\emph on
inner simplex algorithm
\emph default
 uses these indices to construct of the 
\begin_inset Formula $n$
\end_inset

 extremal points to construct the matrix 
\begin_inset Formula $A$
\end_inset

 mapping these to the vertices of 
\begin_inset Formula $\Delta$
\end_inset

:
\begin_inset VSpace bigskip
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float algorithm
placement H
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Inner simplex algorithm
\begin_inset CommandInset label
LatexCommand label
name "alg:isa"

\end_inset


\end_layout

\end_inset

Return 
\begin_inset Formula $A\left(X\right):=\left(X_{ij}\right)_{i=i_{1},...,i_{n},\, j=1,...,n}^{-1}$
\end_inset

 with 
\begin_inset Formula $i_{1},...,i_{n}$
\end_inset

 computed by the 
\emph on
index mapping algorithm
\end_layout

\end_inset


\begin_inset VSpace bigskip
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\end_layout

\begin_layout Standard
In the case of the 
\emph on
maximality assumption
\emph default
, 
\begin_inset Formula $X$
\end_inset

 spans a 
\begin_inset Formula $\left(n-1\right)$
\end_inset

-simplex, and the 
\emph on
index mapping algorithm 
\emph default
determines its vertices, thus 
\begin_inset Formula $\text{co}\left(AX\right)=\Delta$
\end_inset

 and 
\begin_inset Formula $A\in v\left(F_{A}\right)$
\end_inset

 maximizes 
\begin_inset Formula $I_{1}$
\end_inset

.
 For the general case though, Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

 (Lemma 3.13, Theorem 3.14) has shown that the following statements are equivalent
:
\end_layout

\begin_layout Enumerate
The convex hull 
\begin_inset Formula $\text{co}\left(X\right)$
\end_inset

 of 
\begin_inset Formula $X$
\end_inset

 is a simplex.
\end_layout

\begin_layout Enumerate
The result of the 
\emph on
inner simplex algorithm
\emph default
 is feasible, i.e.
 
\begin_inset Formula $A\in F_{A}$
\end_inset

.
\end_layout

\begin_layout Enumerate
\begin_inset Formula $A\in v\left(F_{A}\right)$
\end_inset

 and therefore maximizes 
\begin_inset Formula $I_{1}$
\end_inset

.
\end_layout

\begin_layout Standard
Therefore, the result is not feasible in the generic case.
 If, however, the 
\emph on
maximality assumption 
\emph default
almost holds, i.e.
 the convex hull of X is a small perturbation of a simplex, which according
 to Weber 
\begin_inset CommandInset citation
LatexCommand cite
key "Weber2006"

\end_inset

 (3.4.4) is satisfied in many applications, the algorithm still gives a solution
 near the unperturbed solution.
 Thus, 
\begin_inset Formula $A$
\end_inset

 is near a vertex of the set 
\begin_inset Formula $F_{A}$
\end_inset

 and thus a good initial guess for a local optimization of the unconstrained
 optimization.
\end_layout

\begin_layout Subsection
The PCCA+ algorithm
\end_layout

\begin_layout Standard
Once we have decided on an objective function we can now put together all
 steps:
\end_layout

\begin_layout Standard
\begin_inset Float algorithm
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
PCCA+
\end_layout

\end_inset


\end_layout

\begin_layout Enumerate
Given P and 
\begin_inset Formula $\pi$
\end_inset

, compute 
\begin_inset Formula $X,\,\Lambda$
\end_inset

 using the weighted Schur decomposition as in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:constrXL"

\end_inset


\end_layout

\begin_layout Enumerate
Determine the, in general infeasible, initial guess 
\begin_inset Formula $A_{0}:=A\left(X\right)$
\end_inset

 by the 
\emph on
inner simplex algorithm
\emph default
.
\end_layout

\begin_layout Enumerate
Perform an iterative local optimization 
\begin_inset Formula $A_{0},\, A_{1},...$
\end_inset

 of the objective function 
\begin_inset Formula $I_{1}$
\end_inset

, 
\begin_inset Formula $I_{2}$
\end_inset

 or 
\begin_inset Formula $I_{3}$
\end_inset

.
 In each step 
\begin_inset Formula $A_{k}\rightarrow A_{k+1}$
\end_inset

 only update the elements 
\begin_inset Formula $A_{k,ij},\, i,j\not=1$
\end_inset

 without constraints, then use Algorithm
\emph on
 
\begin_inset CommandInset ref
LatexCommand ref
reference "alg:feas"

\end_inset

 
\emph default
to get a feasible matrix 
\begin_inset Formula $A_{k}$
\end_inset

 before evaluating the corresponding objective function.
\end_layout

\begin_layout Enumerate
Return 
\begin_inset Formula $X$
\end_inset

 and 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
Extension to time-continuous Markov chains
\end_layout

\begin_layout Standard
PCCA+ is also applicable to the clustering of time-continuous Markov chains
 (c.f.
 
\begin_inset CommandInset citation
LatexCommand cite
key "Kube2007"

\end_inset

).
 In that case, the 
\emph on
transition matrix
\emph default
 
\begin_inset Formula $P$
\end_inset

 gets replaced by a 
\emph on
transition rate matrix 
\begin_inset Formula $Q$
\end_inset


\emph default
 having row-sum zero and non-negative off-diagonal entries.
 The transitions after a fixed time can then be computed by
\begin_inset Formula 
\[
P(t)=e^{tQ}.
\]

\end_inset


\end_layout

\begin_layout Standard
In that case, the eigenvectors of 
\begin_inset Formula $P$
\end_inset

 and 
\begin_inset Formula $Q$
\end_inset

 are the same and the eigenvalues of 
\begin_inset Formula $P$
\end_inset

 are the exponential of the corresponding eigenvalues of 
\begin_inset Formula $Q$
\end_inset

.
 As the exponential is monotone, the eigenvectors with highest absolute
 eigenvalue, near 1, of 
\begin_inset Formula $P$
\end_inset

 correspond to the eigenvectors with smallest absolute value, near zero,
 of 
\begin_inset Formula $Q$
\end_inset

.
\end_layout

\begin_layout Standard
So by selecting the eigenvectors with smallest eigenvalue of 
\begin_inset Formula $Q$
\end_inset

 we can compute the corresponding clustering for time-continuous Markov
 chains.
\end_layout

\begin_layout Section

\shape up
Application to eye tracking data
\end_layout

\begin_layout Standard
This algorithm was applied to experimental eye tracking data obtained by
 the Department of Psychology of the University of Potsdam with the goal
 to detect objects as metastable clusters using just the dynamics of the
 human eye, i.e.
 without any data of the image itself, and thus provides a way of interpreting
 the humans object recognition expressed through the eye movements.
\end_layout

\begin_layout Subsection
The experiment and model
\end_layout

\begin_layout Standard
A group of test persons was presented different pictures for about 10 seconds,
 during which an eye tracker measured their fixations 
\begin_inset Formula $f_{i}\in\mathbb{R}^{2}$
\end_inset

 and their respective durations 
\begin_inset Formula $t_{i}\in\mathbb{R}$
\end_inset

.
 For subsequent analysis it is necessary to group different areas of the
 image into 
\emph on
areas of interest (AOE) 
\emph default
which correspond to subjectively identified objects in the corresponding
 picture.
\end_layout

\begin_layout Standard
To apply PCCA+, we need to turn this spatial time series into a Markov chain.
\end_layout

\begin_layout Standard
We model each fixation as a 
\emph on
random choice
\emph default
 on a spatial grid, weighted by a Gaussian of the distance to the grid points,
 and then construct a 
\emph on
Markov chain
\emph default
 by counting the induced transitions on the grid points.
 Assuming, that humans, when looking at the pictures, do not jump randomly
 between all recognized objects but remain for some fixations inside one
 
\emph on
AOE
\emph default
, this behaviour should recur as high metastability of a clustering, correspondi
ng to the 
\emph on
AOEs.
\end_layout

\begin_layout Subsection
Implementation
\begin_inset CommandInset label
LatexCommand label
name "sub:Implementation"

\end_inset


\end_layout

\begin_layout Standard
As state space we choose a spatial grid 
\begin_inset Formula $S:=\left\{ s_{i}\right\} $
\end_inset

, where the natural choice is using all fixation coordinates as grid (
\begin_inset Formula $s_{i}=f_{i}$
\end_inset

 ) or alternatively use some spatial clustering algorithm (e.g.
 k-means) to reduce the computational effort of the following PCCA+ routine.
\end_layout

\begin_layout Standard
Introducing a parameter 
\begin_inset Formula $\sigma$
\end_inset

, we assign a membership of each fixation to each grid point weighted by
 a Gaussian of the distance between them, i.e.
 for each fixation 
\begin_inset Formula $f_{i}$
\end_inset

 and each state 
\begin_inset Formula $s_{j}$
\end_inset

:
\end_layout

\begin_layout Standard
\begin_inset Formula 
\begin{equation}
M_{ij}:=\frac{e^{\frac{\left|f_{i}-s_{j}\right|^{2}}{2\sigma^{2}}}}{\sum_{j}e^{\frac{\left|f_{i}-s_{j}\right|^{2}}{2\sigma^{2}}}}\label{eq:mass}
\end{equation}

\end_inset

This 
\emph on
mass matrix 
\emph default
assures that nearby fixations 
\begin_inset Quotes eld
\end_inset

overlap
\begin_inset Quotes erd
\end_inset

, adopting the metric information contained in the fixation data to the
 Markov process.
 Thus, the parameter 
\begin_inset Formula $\sigma$
\end_inset

, scaling the distance between points, can be interpreted as a spatial coupling
 constant.
\end_layout

\begin_layout Standard
We then choose a fixed time step 
\begin_inset Formula $\Delta\tau$
\end_inset

 as grid size for the time discretization, along which we count the transitions
 between the states weighted with the corresponding fixation transitions,
 and row-normalize it to generate a 
\emph on
transition matrix
\emph default
.
 In detail, for the transitions from state 
\begin_inset Formula $i$
\end_inset

 to 
\begin_inset Formula $j$
\end_inset

 we have
\begin_inset Formula 
\begin{eqnarray*}
\\
P_{ij} & = & \frac{\sum_{s=0}M_{f{}_{s},i}M_{f_{s+1},j}}{\sum_{s=0}M_{f_{s},i}},
\end{eqnarray*}

\end_inset

where 
\begin_inset Formula $f_{s}$
\end_inset

 denotes the current fixation at time 
\begin_inset Formula $s\Delta\tau$
\end_inset

.
\end_layout

\begin_layout Standard
Once we have constructed 
\begin_inset Formula $P$
\end_inset

 this way, we now compute the stationary distribution, being the left eigenvecto
r to eigenvalue one, and pass them to PCCA+, which in return gives us X
 and A to compute the clustering 
\begin_inset Formula $\chi=XA$
\end_inset

.
\end_layout

\begin_layout Standard
As a final step, we discretize this fuzzy clustering by assigning to each
 state 
\begin_inset Formula $s_{i}$
\end_inset

 the cluster 
\begin_inset Formula $c_{i}$
\end_inset

 with the maximal share:
\begin_inset Formula 
\begin{equation}
c_{i}=\text{argmax}_{j}\chi_{ij}.\label{eq:clmax}
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
Note, that choosing this discretization of the fuzzy clustering, some clusters
 may never be assigned, when being dominated by other clusters on every
 grid point.
\end_layout

\begin_layout Standard
In case of preclustering via k-means, the cluster assignment of the grid
 is passed to the corresponding fixations according to the k-means assignments.
\end_layout

\begin_layout Standard
The program was implemented in Julia and its source will be published on
 
\begin_inset Newline newline
\end_inset

https://github.com/kliegl/Hokusai.
\end_layout

\begin_layout Subsection
Choice of the parameters
\end_layout

\begin_layout Standard
The desired number of clusters, 
\begin_inset Formula $n$
\end_inset

, was chosen near the number of objects recognized by the experimenter.
 This, of course, is a subjective choice, but the number of clusters in
 general depends on the desired resolution of the clustering and thus on
 the further application.
 For example, imagine a picture of a bookshelf with books, here one might
 recognize either the whole shelf, the books, or their titles as objects.
\end_layout

\begin_layout Standard
The time step size 
\begin_inset Formula $\Delta\tau$
\end_inset

 should be chosen as large as possible without skipping too many transitions.
 If it is chosen too large some fixations will be skipped resulting in loss
 of information and thus leading to a worse clustering.
 If, on the other hand, chosen too small we count one fixation as multiple
 self-transitions, thus weakening the effect of the real transitions, favouring
 the spatial over the dynamic information.
 
\end_layout

\begin_layout Standard
The parameter 
\begin_inset Formula $\sigma$
\end_inset

 introduces the spatial information and can thus be considered as a weight
 between dynamic and spatial clustering and is therefore inherently necessary.
 While small 
\begin_inset Formula $\sigma$
\end_inset

 values favour the dynamic information, this can lead to scattered clusters
 neglecting the spatial component.
 Large 
\begin_inset Formula $\sigma$
\end_inset

 values will lead to a more regular and convex clustering by enforcing a
 stronger spatial coupling between nearby fixations.
\end_layout

\begin_layout Standard
For a general routine 
\begin_inset Formula $\Delta\tau$
\end_inset

 should be chosen small enough for most fixations to be counted and then
 increase 
\begin_inset Formula $\sigma$
\end_inset

 starting from small values to reach the desired spatial regularity.
 
\end_layout

\begin_layout Standard
The 
\emph on
maximal scaling condition 
\emph default
was used for the following clusterings, as it provided the best results.
\end_layout

\begin_layout Subsection
Results
\end_layout

\begin_layout Standard
Each of the following clusterings was computed based on about 2000 fixations.
 Each fixation is marked as a dot, with the color representing the corresponding
 cluster.
\end_layout

\begin_layout Subsubsection*
The Sistine Madonna
\end_layout

\begin_layout Standard
Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:raphael"

\end_inset

(a) depicts Raphael's 
\begin_inset Quotes eld
\end_inset

Sistine Madonna
\begin_inset Quotes erd
\end_inset

 oil painting, one of the last of his many Madonnas, commissioned by Pope
 Julius II for the Monastery of San Sisto in Piacenza, Italy.
 In the middle, we see the Madonna, holding Jesus, her child.
 She is flanked by Saint Sixtus and Saint Barbara.
 To their feet, we can see the two cherubim who became quite popular on
 their own in the last centuries as motives for postcards, advertisements,
 gifts and home décor.
 In the bottom left, we can see the Pope's crown, the Papal tiara.
\end_layout

\begin_layout Standard
In (b) we chose a small 
\begin_inset Formula $\sigma$
\end_inset

 value to emphasize the dynamic share of the clustering.
 As a consequence Saint Sixtus and Saint Barbara are clustered into one
 cluster, indicating back and forth movements of the observer, although
 they are separated by the Madonna.
 This non-convex clustering is a feature specific to the analysis of the
 dynamics which can not be reached by purely spatial clustering, e.g.
 k-means.
 Furthermore, the Madonna with her child and the Papal tiara are separated.
 The noisy red cluster is typical for small 
\begin_inset Formula $\sigma$
\end_inset

 values, as small cycles get uncoupled from the rest of the fixations due
 to the missing spatial coupling.
\end_layout

\begin_layout Standard
The more natural 
\begin_inset Formula $\sigma$
\end_inset

 choice and a higher cluster number in (c) allow a separation between the
 left and right saints, and instead of the red noise-cluster we now get
 a further cluster for the right curtain.
 
\end_layout

\begin_layout Standard
Further refinement (d) leads to additional separation of the left curtain,
 the background behind Saint Sixtus, his and Madonnas feet as well as her
 skirt.
 Unfortunately, we were not able to separate the Madonna from her child.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename 1.jpg
	lyxscale 15
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Original
\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img1 n5 tau20 sigma35 methodscaling precl0.png
	lyxscale 30
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=5,\,\tau=20,\,\sigma=35$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img1 n6 tau50 sigma60 methodscaling precl0.png
	lyxscale 30
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=6,\,\tau=50,\,\sigma=60$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img1 n10 tau60 sigma50 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=10,\,\tau=60,\,\sigma=50$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:raphael"

\end_inset

The Sistine Madonna (1512) by Raphael 
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename 5.jpg
	lyxscale 20
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Original
\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img5 n6 tau100 sigma250 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=6,\,\tau=100,\,\sigma=250$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img5 n7 tau80 sigma120 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=7,\,\tau=80,\,\sigma=120$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img5 n9 tau80 sigma120 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=9,\,\tau=80,\,\sigma=120$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:rembrandt"

\end_inset

The Three Trees (1643) by Rembrandt
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
Three Trees
\end_layout

\begin_layout Standard
In Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:rembrandt"

\end_inset

(a), we see Rembrandt's 
\begin_inset Quotes eld
\end_inset

Three Trees
\begin_inset Quotes erd
\end_inset

, widely regarded as his greatest and most elaborate landscape etching.
 It features a combination of many details: Of course there are the three
 trees as most prominent feature in the foreground, complemented by a fisherman
 accompanied by his wife in the lower left, a painter on the hill to the
 right of the trees and a cloud formation resembling and upcoming storm
 to their left.
\end_layout

\begin_layout Standard
Already the coarse clustering (b) shows a good separation of the trees,
 also assigning clusters to the fisherman and the stormy clouds, additionally
 the three corners of the image.
 
\end_layout

\begin_layout Standard
The refinement (c) now also separates the fisherman and his wife from the
 background, and further refinement (d) even separates the treetops from
 their trunks, also assigning an own cluster to the painter.
\end_layout

\begin_layout Standard
\begin_inset Float figure
placement H
wide false
sideways false
status collapsed

\begin_layout Plain Layout
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename 7.jpg
	lyxscale 20
	width 50line%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Original
\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img7 n6 tau80 sigma80 methodscaling precl0.png
	lyxscale 40
	width 50col%
	clip

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=6,\,\tau=80,\,\sigma=80$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Newline newline
\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img7 n8 tau80 sigma80 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=8,\,\tau=80,\,\sigma=80$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset Graphics
	filename img7 n10 tau80 sigma100 methodscaling precl0.png
	lyxscale 40
	width 50col%

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset Formula $n=10,\,\tau=80,\,\sigma=100$
\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
\begin_inset CommandInset label
LatexCommand label
name "fig:hokusai"

\end_inset

In the Totomi Mountains (1830) by Hokusai 
\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsubsection*
In the Totomi Mountains
\end_layout

\begin_layout Standard
Figure 
\begin_inset CommandInset ref
LatexCommand ref
reference "fig:hokusai"

\end_inset

(a) shows Katsushika Hokusai's 
\begin_inset Quotes eld
\end_inset

In the Totomi Mountains
\begin_inset Quotes erd
\end_inset

, one out 36 color woodblock prints of his series 
\begin_inset Quotes eld
\end_inset

Thirty-six Views of Mount Fuji
\begin_inset Quotes erd
\end_inset

, featuring the prominent volcano Mount Fuji, the highest mountain in Japan.
 This picture was chosen for it has a large number of distinct features:
 Two men sawing a large tree block on stands, a woman with a baby on her
 back watching a third man sawing a tree trunk on the ground and another
 man in the back making a fire, the Mount Fuji in the back entwined by a
 curling cloud.
\end_layout

\begin_layout Standard
The clustering into six clusters (b) focuses on a rough separation of the
 people (three clusters on five people), the legend in the top left, the
 smoke of the fire and the strawmat at the foot of the tree block.
 One might object that none of these clusters separate any of the objects
 properly, but as we impose just six clusters one can't expect a clear separatio
n as the objects in between have to become assigned as well.
 
\end_layout

\begin_layout Standard
Increasing the cluster number to eight (c), we gain an splitting of the
 former upper left cluster, now properly isolating the legend, the smoke
 around the Mount Fuji with its peak and the top of the wood block.
 
\end_layout

\begin_layout Standard
Further refinement to ten clusters (d) splits the two lower clusters into
 three, now distinguishing between the man sawing on the ground, the woman
 with her baby and the standing woodcutter with the man making the fire
 in the background.
 Additionally, the upper right cluster gets split into two, now correctly
 differentiating between the smoke and the hill.
\end_layout

\begin_layout Section
Discussion
\end_layout

\begin_layout Standard
Given a good choice of parameters, the algorithm showed to be able to cluster
 the points to the subjectively identified objects in the picture, backing
 up the hypothesis that human sight exhibits the metastable behaviour on
 recognized objects.
\end_layout

\begin_layout Standard
This conclusion already implies the current problem of the approach, the
 parameters.
 Although most of the resulting clusters proved to be stable in many situations,
 high cluster numbers or small 
\begin_inset Formula $\sigma$
\end_inset

 values lead to unstable results.
 
\end_layout

\begin_layout Standard
The time step parameter 
\begin_inset Formula $\Delta\tau$
\end_inset

 could be completely eliminated by using a time-continuous Markov chain
 as underlying transition model, leading to a transition rate matrix.
 Unfortunately the ad hoc approach using 
\begin_inset Formula 
\[
W_{ij}=\left(\frac{\sum_{a\rightarrow b}M_{ai}M_{bj}\tau_{a\rightarrow b}}{\sum_{a\rightarrow b}M_{ai}}\right)^{-1},
\]

\end_inset

denoting by 
\begin_inset Formula $\sum_{a\rightarrow b}$
\end_inset

 the sum over all fixation transitions, from 
\begin_inset Formula $a$
\end_inset

 to 
\begin_inset Formula $b$
\end_inset

, and 
\begin_inset Formula $\tau_{a\rightarrow b}$
\end_inset

 the corresponding transition time, leads to worse results.
 It is not yet clear to the author how to construct the most likelihood
 estimator for the corresponding process.
\end_layout

\begin_layout Standard
A, compared to the here chosen maximum method (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:clmax"

\end_inset

), more sophisticated method to discretize the fuzzy clustering could also
 proof crucial in improving the results.
 One possibility might be weighting the clusters with their size, thus,
 emphasizing their relative shape and/or discarding points with no clear
 assignment to an extra cluster.
 This would also solve the problem of non-assignment of some clusters mentioned
 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Implementation"

\end_inset

.
\end_layout

\begin_layout Standard
The choice of other 
\emph on
mass matrices 
\emph default

\begin_inset Formula $M$
\end_inset


\emph on
 
\emph default
in (
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:mass"

\end_inset

) and a different weighting of the states than by the stationary distribution
 
\begin_inset Formula $\pi$
\end_inset

 in section 
\begin_inset CommandInset ref
LatexCommand ref
reference "sub:constrXL"

\end_inset

 might allow for further adjustment of the results.
\end_layout

\begin_layout Standard
Overall, the presented method, turning the time series into a Markov chain
 and applying PCCA+ for the clustering, proved to be successful and a viable
 approach to spatial time series clustering with open opportunities for
 further improvement.
\end_layout

\begin_layout Standard
\begin_inset Newpage newpage
\end_inset


\shape up

\begin_inset CommandInset bibtex
LatexCommand bibtex
bibfiles "ba"
options "bibtotoc,plain"

\end_inset


\end_layout

\end_body
\end_document