Dalla Sparse Representation al Dictionary Learning: algoritmi K-SVD e SGK

In this thesis we present the problem of Dictionary Learning, a problem of growing interest in recent years. Given a set of signal-atoms Y, we research the dictionary D that leads to the best sparse representation of these signals, according to Y=DX under-determined system. In order to do so, various algorithms have been developed and they are based on two phases: a Sparse Representation phase where we update the coefficients matrix, followed by a Dictionary Update phase. In this paper we present two algorithms designed to solve the Dictionary Learning problem: the K-SVD algorithm and the SGK algorithm. We will briefly follow their implementation and, after comparing their features and computational costs, we will come to the conclusion that the SGK algorithm is the more convenient to use in Dictionary Learning.

In questa tesi viene presentato un problema di crescente interesse negli ultimi anni, il Dictionary Learning. Dato un set di segnali-esempio Y, si ricerca un dizionario D che sia la miglior rappresentazione sparsa di questi segnali secondo il sistema sottodeterminato Y=DX. Per farlo sono stati sviluppati diversi algoritmi, che si basano su una prima fase di Sparse Representation, dove viene aggiornata la matrice dei coefficienti X, e una seconda fase di Dictionary Update, dove viene aggiornato, appunto, il dizionario. A questo scopo verranno presentati due algoritmi, la K-SVD e la SGK. Daremo breve illustrazione della loro implementazione e, confrontando le caratteristiche e i costi computazionali, concluderemo che il secondo metodo sarà quello più vantaggioso.