Matrix and tensor methods for dictionary learning for sparse representations

master's thesis

• Title (croatian): Matrične i tenzorske metode za učenje rječnika za rijetke prikaze
• Author: Fran Špigel
• Mentor: Zlatko Drmač (mentor)
• Committee member: Zlatko Drmač (predsjednik povjerenstva)
• Committee member: Goran Muić (član povjerenstva)
• Committee member: Josip Tambača (član povjerenstva)
• Committee member: Pavle Pandžić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-04-29, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Iako ovo nije cjelokupan pregled, proučili smo nekolicinu efektivnih metoda za rijetku reprezentaciju podataka, tj. rješavanje \(min_a \left\|x-Ba\right\|\) sa uvjetom rijetkosti na \(a\) te povezane probleme. Počeli smo u poglavlju 1 objašnjavajući metode koje se najčešće koriste u modernom procesiranju signala, kao što su DCT i DFT, te smo upoznali neke općenite metode za rijetke reprezentacije - matching pursuit i basis pursuit. Spomenuli smo neke od problema koji su sadržani u ovom području, pogotovo činjenicu da je suštinski problem NP-težak, te kako se suočiti sa tim problemima. U poglavlju 2, upoznali smo se sa nekolicinom metoda za optimizaciju ne samo rijetke reprezentacije, nego i rječnika \(B\). Diskutirajući k-means i SVD, izgradili smo znanje potrebno za razumjevanje K-SVD algoritma, te smo ga testirali na sintetičkim podacima. Takoder smo ukratko pregledali još jedan pristup sa širokom primjenom - ’principal component analysis’, nužan za razumjevanje MPCA algoritma kojeg spominjemo kasnije. U zadnjem poglavlju, poglavlju 3, ulazimo u domenu tenzora. Ovo je prirodan korak budući da se puno stvarnih podataka, pogotovo vizualnih, može puno prirodnije prikazati u obliku tenzora višeg reda. Ponovili smo malo osnovne aritmetike tenzora, te upoznali dvije metode - jedna je metoda za učenje rječnika napravljena za analizu dinamičkih tekstura, a druga je multilinearna PCA, generalizacija PCA algoritma iz prethodnog poglavlja u prostor tenzora. Primjene rijetkih reprezentacija su široke, i nove metode se razvijaju vrlo brzo kako bi se suočili sa modernim problemom sve veće količine podataka koje prikupljamo i šaljemo preko telekomunikacijskih mreža, koje treba analizirati i komprimirati.

Abstract (english)

While this is by no means an exhaustive review, we have overviewed a number of efective methods for representing data sparsely, which is to say, solving \(min_a \left\|x-Ba\right\|\) with sparsity constraints on \(a\) and related problems. We started in chapter 1 by going over methods most widely used in modern signal processing, such as the DCT and DFT, and then introduced some general-purpose methods for sparse coding - namely matching pursuit and basis pursuit. We touched on some of the problems inherent in sparse coding (the fact that the base problem is NP-hard), and how to circumvent those issues. In chapter 2, we introduced a number of methods for not only optimizing the sparse representation, but the dictionary \(B\) as well, and sometimes simultaneously. By discussing k-means clustering and singular-value decompositions, we built the knowledge base necessary to understand the K-SVD algorithm, and we tested it on some synthetic data. We also briefly overviewed another approach with broad applications - the principal component analysis, necessary to understand MPCA discussed later on. In the last chapter, chapter 3, we enter the domain of tensors. This is a natural step, as much real-world data, especially visual data, is more naturally represented as tensors of higher orders instead of vectors or matrices. We went over some basic tensor arithmetic, and then reviewed two methods. One is a dictionary learning method built to analyze dynamic textures, and the other is multilinear principal component analysis - a generalization of PCA to tensor space. The applications of sparse coding and dictionary learning are vast, and new methods are being developed rapidly in order to deal with the modern problem of ever more data being accumulated, sent over communication channels and needing to be analyzed or compressed

• Keywords: moderno procesiranje signala; DCT; DFT; K-SVD algoritam
• Keywords (english): modern signal processing; DCT; DFT; K-SVD algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:148465
• Study programme: Title: Applied Mathematics; 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-05-20 13:31:03