Ph.D Thesis

Ph.D StudentAharon Michal
SubjectOvercomplete Dictionaries for Sparse Representation of
DepartmentDepartment of Computer Science
Supervisor PROF. Michael Elad
Full Thesis textFull thesis text - English Version


In recent years there has been a growing interest in the study of sparse representation of signals. Using an overcomplete dictionary that contains prototype signal-atoms, signals are described as linear combinations of a few of these atoms. Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and more.

Roughly speaking, the activity in this field concentrates around two main problems: (i) algorithms for performing sparse decomposition and their performance analysis, and (ii) dictionary composition methods. The `sparse decomposition' activity deals with the pursuit problem - given a signal and an overcomplete dictionary, the goal is to find the smallest set of atoms from the dictionary to represent it. The construction of appropriate dictionaries that lead to the existence of sparse representations for a family of signals in mind is the second challenge addressed in recent years in this field. Among the various contributions on this problem, dictionary learning from examples is especially appealing as it can tune the found dictionary to specific and narrow families of signals.

In this work we concentrate on this dictionary learning process. The problem setting for dictionary learning is the following - given a set of signals assumed to have a sparse representation over an unknown dictionary D, can we find D? At the heart of this work stands the novel dictionary learning algorithm named the K-SVD. We describe its development and analysis, and show some stylized applications to demonstrate its applicability and the advantages of trained dictionaries in general. Variations of the K-SVD algorithm for learning structural constrained dictionaries are also presented. Among those constraints are the non-negativity of the dictionary and shift invariance property. This work also includes a development of a state-of-the-art image denoising algorithm based on the K-SVD. This contribution is important as it strengthens the message that the general model of sparsity and redundancy, along with fitted dictionaries as considered here, could lead to the best known results in practical applications in image processing.

An underlying assumption throughout this thesis is that natural signals are represented well using a sparse linear composition of atoms from redundant dictionaries. We refer to this assumption as the "Sparseland" model, and provide an initial study of its geometrical behavior. More specifically, we provide bounds on the expected ratio of signals that can be represented by this dictionary with fixed sparsity constraints.