faberno / integrating_linear_assignment_flows Goto Github PK

The objective of this thesis is to evaluate the error and time complexity of both the Explicit Euler Method and the Krylov Subspace Method, depending on their respective parameters step size and subspace dimension, so we can assess their performance in a direct comparison.
This repository contains brief explanations and findings as well as all necessary code. For more information, be sure to take a look at the full document.

This section will cover the background of the thesis very briefly.

Implementation
The Linear Assignment Flow (Zeilmann et al., 2020) is represented by an ODE on the tangent space

at the barycenter of the assignment Manifold

meaning that every row of $W\in \mathcal{W}$ represents a pixel and every column a label. The resulting entries then represent the probability of pixel $i$ being mapped to label $j$, so that every row sums up to 1. It is represented by an ODE of the form

where

• $V(t) \in \mathcal{T}_0$ is our tangent vector

• $A \in \mathbb{R}^{IJ\times IJ}$ represents the weights in pixel neighborhood
• $b \in \mathbb{R}^{IJ}$ carries the image data

For a standard sized image of $500\times500$ pixels and 5 prototypes, the system will result in the dimension

so sparse matrix representations have to be used.

For a matrix $A \in \mathbb{R}^{n\times n}$ we define the matrix exponential to be the $n\times n$ matrix

The φ-Functions represent special cases of the Mittag-Leffler Function and have the form

or as Taylor-Series

The solution of an inhomogeneous ODE is given by

respectively

if $x_0=0$.

Implementation
The Explicit Euler Method (also called ”forward Euler“) is the most basic method to solve an ODE. It is calculated iteratively by

where $h$ is a step size.

Implementation
The Krylov Subspace Method (Niesen and Wright, 2012, pp. 4-6) is a more advanced method than the Explicit Euler Method. It tries to approximate $\varphi_p(A)x$ which lives in $\mathbb{R}^n$ by using the Krylov Subspace

By orthonormalizing it, we get

These basis vectors combined, form the matrix $V_m \in \mathbb{R}^{n\times m}$ such that

respectively

where $e_m$ is a vector in the standard basis and $H_m$ is a small Hessenberg matrix $\in \mathbb{R}^{m\times m}.$ Approximating $A$ in this way is very useful to calculate the the $\varphi$-Funtions, because

so the matrix exponential does not have to be calculated on a very big matrix anymore, but instead one of size $m\times m$.

The global error of the Explicit Euler Integration has an upper bound

so it shrinks linearly with $h$, at least for small $h$.

The Krylov Subspace Methods a priori error has an upper bound

and in the Linear Assignment Flow $\lVert A \rVert = 1$, so it further simplifies to

So its a priori error shrinks factorially with $m$.
More info on the possible error correction and the estimation of an a posteriori error are the full document.

Parameters:

• $I$: Number of pixels, $J$: Number of labels
• $m$: Krylov Subspace Dimension
• $h$: step size
• $t$: total integrated distance
• $q$: degree of the Padé approximation (small)
• $s$: number that is needed to bring the spectral radius of $A$ below 0.5 by $A/2^s$ (small)

The Complexity of the Explicit Euler Method lies in

so it shrinks inversely proportional with the step size.
The Complexity of the Krylov Subspace Method lies in

when the Lanczos Iteration can be used for orthonormalization. Because the usually high number of pixels the left term dominates the right one and the methods complexity grows linearly proportional with $m$.

As can be seen in the following, the experiments support the theoretical findings.

For small $h$ the error of the Explicit Euler Method grows linearly.

(Euler) Error for varying step size h. left: linear, right: log

The error of the Krylov Subspace Method shrinks factorially fast with $m$ and also for a larger $t$ we can choose a $m$ that is several order smaller than $IJ$.

(Krylov) A priori bounds and the actual error for t = 1 (left) and t = 5 (right)

For a growing step size, the run time of the Explicit Euler Method shrinks inversely proportional.

(Euler) Run times for varying h and a fixed IJ

The run time of the Krylov Subspace Method grows linearly with $m$ if $m \ll IJ$. When they are similar, the run time grows exponentially.

(Krylov) Run times for varying m, if m ≪ IJ (left) and m = IJ (right)

• Zeilmann, A., Savarino, F., Petra, S., and Schnörr, C. (2020). Geometric numerical integration of the assignment flow. Inverse Problems
  
• Niesen, J. and Wright, W. M. (2012). Algorithm 919. ACM Transactions on Mathematical Software

Distributed under the MIT License. See LICENSE for more information.

(back to top)