*Result*: Multilevel optimisation for computer vision

*The recent spark in machine learning and computer vision methods requiring increasingly larger datasets has motivated the introduction of optimisation algorithms specifically tailored to solve very large problems within practical time constraints. This demand in algorithms challenges the practicability of state of the art methods requiring new approaches that can take advantage of not only the problem’s mathematical structure, but also its data structure. Fortunately, such structure is present in many computer vision applications, where the problems can be modelled with varying degrees of fidelity. This structure suggests using multiscale models and thus multilevel algorithms. The objective of this thesis is to develop, implement and test provably convergent multilevel optimisation algorithms for convex composite optimisation problems in general and its applications in computer vision in particular. Our first multilevel algorithm solves convex composite optimisation problem and it is most efficient particularly for the robust facial recognition task. The method uses concepts from proximal gradient, mirror descent and multilevel optimisation algorithms, thus we call it multilevel accelerated gradient mirror descent algorithm (MAGMA). We first show that MAGMA has the same theoretical convergence rate as the state of the art first order methods and has much lower per iteration complexity. Then we demonstrate its practical advantage on many facial recognition problems. The second part of the thesis introduces new multilevel procedure most appropriate for the robust PCA problems requiring iterative SVD computations. We propose to exploit the multiscale structure present in these problems by constructing lower dimensional matrices and use its singular values for each iteration of the optimisation procedure. We implement this approach on three different optimisation algorithms - inexact ALM, Frank-Wolfe Thresholding and non-convex alternating projections. In this case as well we show that these multilevel algorithms converge (to an exact or approximate) solution with the same convergence rate as their standard counterparts and test all three methods on numerous synthetic and real life problems demonstrating that the multilevel algorithms are not only much faster, but also solve problems that often cannot be solved by their standard counterparts.*