M.Sc Thesis

M.Sc StudentRaboy Svetlana
SubjectOn The Recovery of Missing Samples Via Sparsity Conditions
DepartmentDepartment of Electrical and Computers Engineering
Supervisors PROFESSOR EMERITUS Arie Feuer
PROF. Michael Elad
Full Thesis textFull thesis text - English Version


Over-completeness and sparsity have been shown in recent years to be powerful tools in the analysis and representation of signals.  This approach considers signals as linear combinations of atom signals from an over-complete dictionary, promoting sparsity of the linear coefficients. Much of the activity in this field has been focused on characterizing the properties of sparse representations, analyzing pursuit algorithms, and exploring different applications. In this work we discuss one specific application - the recovery of missing samples using sparsity as a prior. We present a theoretical analysis of this problem - also known as the inpainting problem in the context of image processing - and discuss practical considerations for filling holes in images. In the theoretical study we address the question of representing and reconstructing a signal from a subset of its samples. We consider under which conditions this is possible and to what extent. We provide a worst-case bound which ensures perfect recovery of a signal from its partial samples, and show how the behavior of this bound depends on the number of missing samples. From the worst-case viewpoint we turn to practical recovery by considering the question of adapting a dictionary to the inpainting problem. We introduce a new inpainting-sensitive version of the K-SVD learning algorithm to achieve this goal. The proposed algorithm is an iterative process that interchanges sparse coding of corrupted training data and dictionary updates using an uncorrupted data. We study the influence of the locations of the missing samples on the recovery results and describe the most problematic settings. We demonstrate our algorithm on real image data with different missing pixels configurations.