Sparsity & Dictionaries - Algorithms & Design

Abstract With the flood of information available today the question how to deal with high dimensional da-ta/signals, which are cumbersome to handle, to calculate with and to store, is highly important.One approach to reducing this flood is to find sparse signal representations, as a signal that is thelinear combination of a few elements from a pool of building blocks, can be reduced to the few coeffi-cients of this representation. If these building blocks form a basis, finding the sparse representationposes no problem but unfortunately not many signal classes are sparse in a basis. Taking morebuilding blocks, i.e. a redundant dictionary, increases the chances of having sparse representations,but actually finding them becomes very hard. This led to the development of numerous strategiesand algorithms for finding sparse representations, with varying complexity and success rate.The first part of the thesis deals with two of those algorithms, Thresholding and Matching Pur-suit, from a more theoretical point of view. It is shown that both those greedy algorithms can beimproved with a little trick, that does not increase their complexity, and that when consideringtheir averageinstead of their worst case performance they perform quite well in comparison to morecomplex methods.The second part of thesis treats questions concerning the whole dictionary and its properties. Firstit gives more evidence that sparsity is useful by extending the concept of compressed sensing tosignals that are sparse not in a basis but in a redundant dictionary. Thus to record a sparse signal itis not necessary to make as many measurements as the dimension of the signal but only a multipleof the number of dictionary elements used to represent it.Next we show that dictionaries cannot only provide sparse representations but that their geometricproperties can also be exploited to model data structures. Here we explain how to model differentsubclasses of a class of signals by incoherent subspaces, present an algorithm to learn a dictionarymade out of these subspaces and then use it for classification of faces.Finally we turn back to the sparse representation problem and study the fundamental question howto find a dictionary providing sparse representations. We pick up the idea to learn a dictionary viaminimisation of a continuous cost function and provide conditions, guaranteeing that the decom-position of a collection of training signals into a dictionary and a coefficient matrix constitutes alocalminimum. Wealsoanalysestatisticallywhentheseconditionsarefulfilledwithhighprobability.Keywords: sparse representation, redundant dictionary, greedy algorithms, preconditioning,average case analysis, multichannel, compressed sensing, classification, dictionary learningvii