Analysis of algorithms for sparse signal representation

diplomski rad

• Autor: Dorian Stipić
• Mentor: Zlatko Drmač (mentor)
• Član povjerenstva: Zlatko Drmač (predsjednik povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Član povjerenstva: Matija Kazalicki (član povjerenstva)
• Član povjerenstva: Pavle Pandžić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-07-24, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (hrvatski)

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.

• Ključne riječi: sparse signal representation
• Ključne riječi (hrvatski): analiza algoritama za rijetku reprezentaciju signala
• Jezik: engleski
• URN:NBN: urn:nbn:hr:217:457053
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-02-05 12:25:12