Optimisation Principles, Models & Algorithms for Dictionary Learning

Be it the 300 million photos uploaded to Facebook per day, the 800GB the large Hadron collider records per second or the 320.000GB per second it cannot record, it is clear that we have reached the age of big data. Indeed, last year the amount of data existing worldwide is estimated to have reached 2.8 ZB = 2.800 billion GB and while 23% of these data are expected to be useful if analysed only 1% actually are. So how do we deal with this big data challenge? On the side of data processing some of the most promising strategies are based on the key concept of sparsity, i.e., the low complexity of even high-dimensional data when represented in a suitable frame/dictionary. This project addresses the fundamental question how to automatically learn a dictionary, providing sparse representations for a given data class, known as dictionary learning or sparse coding. It aims to provide a deeper theoretical understanding of dictionary learning and based on that to develop stable and efficient learning algorithms for high-dimensional data. To reach this goal in particular the following topics will be addressed. Optimisation Principles: The most promising strategies for dictionary learning so far have been based on optimisation principles. We will investigate the local and global dictionary identification properties of several classical and new principles, assuming suitable sparse generating models for the signals. Models: We will go beyond the currently used isotropic sparse coefficient models and develop realistic sparse generating models, that allow us to model also structured sparse data sets. Further, we will design and analyse learning principles that allow identification of the dictionary together with (independent of) the underlying sparse structures. (Randomised) Algorithms: A fundamental challenge in dictionary learning is the high- dimensionality of the learning problem itself. Hence, we will explore how to reduce the computational complexity of the learning task via Johnson-Lindenstrauss embeddings and divide& conquer schemes. Analysis Dictionary Learning: Analysis (co)-sparsity has been recently introduced as promising alternative to synthesis sparsity. We are going to study the analysis dictionary learning problem through an approach parallel to synthesis dictionary learning, i.e., the formulation of optimisation principles, investigation of identifiability given random co-sparse signal models and development of efficient (randomised) algorithms. Applications: In close cooperation with our (inter)national scientific partners we will apply the developed schemes to high dimensional problems which cannot be tackled by currently available dictionary learning schemes, e.g. microscopy imaging, sound tracing, audio inpainting, magnetic resonance imaging or acoustic perception.

Given a class of signals, the aim of dictionary learning is to automatically find a representation system called dictionary, that allows to compactly represent all signals in the class. One of the main goals of the project was the design of dictionary learning algorithms, which provide sensible results on real and synthetic data and for which a theoretical analysis of their convergence behaviour can be conducted. Among the most beautiful outcomes of the project is a dictionary learning algorithm, that - without having the size of the dictionary or the compactness of the representation as input - learns the true underlying dictionary from synthetic data and plausible dictionaries on image data. Further, the project led to the first resp. improved characterisations of the convergent areas for the well-established dictionary algorithms MOD resp. ODL also known as approximative K-SVD. At the same time these results constitute the first theoretical results in dictionary learning, which are based on a natural signal model, where each dictionary element is used in the signal representations with a different probability. Finally we count among the outcomes of the project: simple insights into the design of measurement matrices in compressed sensing, applications of dictionary learning to image reconstruction in MRI and the probably first and definitely cutest semi definite order bound for matrices of inclusion probabilities in rejective sampling.