Dictionary Learning for Biometric Data

Research in the last years has shown that many problems in high-dimensional data-processing, such as compression or denoising, can be efficiently solved if the signals at hand have a sparse representation in a known generating system, called dictionary. This leads to the fundamental question, how to find dictionaries providing sparse representations for a given data-class - a problem known as dictionary learning or sparse coding. The aim of this project is to study dictionary learning for biometric data. The main focus within the field of dictionary learning has so far been on the development of learning algorithms, which, however, all suffer from one of the following limitations. There is no characterisation of the outcome of the algorithm, therefore no indication whether it is appropriate for the data at hand. The algorithm is too complex to be applicable to very high-dimensional data. The algorithm is based on the assumption that all elements of the dictionary are used with the same probability and strength. When dealing with biometric data especially the last two limitations prevent the use of already existing algorithms, because biometric data, like full iris images, has usually a high dimension and is very structured. For instance, facial images exhibit strong similarities between each other on a coarse level, which suggests the preferred use of one dictionary element in all representations. This project plans to overcome the above mentioned limitations of dictionary learning algorithms using the following approach. First, suitable models of structured sparsity for three biometric data classes will be studied and, based on that, simple algorithms will be developed that can be proven to identify the underlying dictionaries from data-classes following these models. To keep the computational complexity of the algorithms low, dimensionality reduction schemes will be investigated. Finally the project will relate the learning of dictionaries that are suited to a task like classification to dictionary learning for structured sparsity.

Dictionary learning is a technique to automatically learn building blocks (the dictionary), which allow to efficiently represent all elements in a data class, such as face images or speech, from some elements of the data class. This representation consists simply of the sum of a small number of adaptively chosen and weighted building blocks. The fact that such an efficient representation exists, is very useful for many signal processing tasks, such as image denoising or reconstruction of incomplete data. A practical example is magnetic resonance imaging, where based on good building blocks, the number of measurements and thus the acquisition time (in the box) can be reduced.The problem with most learning algorithms is that they are computationally very costly and that there are no guarantees that they will work in practice. In this project we could shed light on the question when K-SVD, the Ferrari of dictionary algorithms, will perform well. Based on the shortcomings of K-SVD, that is, theoretically predicted complications in some regimes, we then developed two very simple dictionary learning algorithms called iterative thresholding and K signal/residual means (ITKsM/ITKrM). For both algorithms we could prove good local behaviour and in the case of ITKrM we could experimentally show also good global behaviour.The main advantage of ITKrM over K-SVD is that it is much cheaper and thus faster. Also the training signals can be processed sequentially, such that the work can be distributed to several computers, which further increases speed. This computational efficiency makes ITKrM the Fiat 500 of dictionary learning and allows dictionary learning to be applied to a much wider range of problem sizes. Coming back to the example of magnetic resonance imaging this can contribute to a further reduction of acquisition time.