Analysis of algorithms for sparse signal representation

master's thesis

• Author: Dorian Stipić
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Committee member: Pavle Pandžić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-07-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

The topic of this thesis is sparse representations of signals. The thesis follows mainly the book Sparse and redundant representations by Michael Elad and is divided into five parts. The first part, consisting of chapter one, introduces the problem (P0) and related and describes the reason why is well founded. The second part, consisting of chapter two, presents the conditions under which the solution to the problem (P0), for the special two-orthogonal and general case, exhibits uniqueness and optimality. In doing so two special measures of a matrix A are introduced: the spark and the mutual-coherence. The third part, consisting of chapters three and four, describes six diferent algorithms for solving (P0) which are divided into two main categories: greedy and convex relaxational. Chapter four deals with theoretical guarantees of those algorithms. The fourth part, consisting of chapter five, introduces the (P 0) problem which is a more robust version of (P0) and thus better for applications. For this new problem uniqueness (which cannot be claimed) is replaced by stability of the solution. The elegant result of the stability of (P 0) is proved using the subtle concept of Restricted Isometry Property of a matrix. The fifth part, consisting of chapter six, introduces the generative model named Sparseland and presents a powerful application of a version of (P 0) to image inpainting. The algorithm used is called K-SVD and it achieved State-of-the-art performance by the time of first publication in 2006. The experiments are presented in the last section showing excellent results and great potential for future work.

Abstract (croatian)

Naslov i tema ovog rada je analiza algoritama za rijetku reprezentaciju signala. Rad uglavnom prati knjigu Sparse and redundant representations od Michaela Elada i podijeljen je u pet dijelova. U prvom dijelu, koji se sastoji od prvog poglavlja, uvodi se problem (P0) i njemu slični problemi te opisuje zašto je dobro utemeljen. U drugom dijelu, koji se sastoji od drugog poglavlja, izlažu se i dokazuju dovoljni uvjeti za koje je rješenje problema (P0) za specijalni dvo-ortogonalni te općeniti slučaj, jedinstveno i optimalno. U tom postupku uvedena su dva pojma vezana za matricu A: Iskra i međusobna-uskladenost. U trećem dijelu, koji se sastoji od trećeg i četvrtog poglavlja, opisuje se šest različitih algoritama za rješavanje (P0) problema koji su podijeljeni u dvije glavne kategorije: pohlepni i konveksno relaksacijski. Četvrto poglavlje je posvečeno teorijskim aspektima tih algoritama. U četvrtom dijelu, koji se sastoji od petog poglavlja, uvodi se problem (P 0) koji je robusnija verzija od (P0) i zato prikladniji za primjene. Za novouvedeni problem jedinstvenost (koja više ne vrijedi) je zamijenjena sa pojmom stabilnosti. Elegantni rezultat stabilnosti od (P 0) je dokazan korištenjem pojma Ogranićenog Izometrijskog Svojstva matrice. U petom dijelu, koji se sastoji od šestog poglavlja, uvodi se generirajući model pod nazivom Sparseland i pokazuje se snažna primjena jedne verzije od (P 0) za rekonstrukciju oštećenih slika. Korišten je tzv. K-SVD algoritam čiji su rezultati bili na State-of-the-art razini na dan publikacije 2006. godine. Eksperimenti su detaljno opisani u zadnjoj sekciji te potvrduju odlične rezultate i pokazuju puno potencijala za daljni razvoj.

• Keywords: sparse signal representation
• Keywords (croatian): analiza algoritama za rijetku reprezentaciju signala
• Language: english
• URN:NBN: urn:nbn:hr:217:457053
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-02-05 12:25:12