Universal Sparse Representation

Universal Sparse Representation
August, 01, 2018
Room 1061 Electrical Eng. Building Technion City

Signal Processing and Systems

Graduate Seminar

Speaker: Rotem Mulayof
Affiliation: Electrical Eng., Technion

Sparse representation over redundant dictionaries constitutes a good model for many classes of signals (e.g. patches of natural images, segments of speech signals, etc.). However, despite its popularity, very little is known about the representation capacity of this model. In this work, we study how redundant a dictionary must be so as to allow any vector to admit a sparse approximation with a prescribed sparsity and a prescribed level of accuracy. We address this problem both in a worst-case setting and in a typical-case one. For each scenario, we derive lower and upper bounds on the minimal required overcompleteness. Our bounds have simple closed-form expressions that allow to easily deduce the asymptotic behavior in large dimensions. In particular, we find that the required overcompleteness grows exponentially with the sparsity level and polynomially with the allowed representation error. This implies that universal sparse representation is practical only at moderate sparsity levels, but can be achieved at relatively high accuracy. Additionally, we suggest an algorithm to construct universal sparse representation dictionaries, based on minimizing the dictionary’s coherence. We show that our approach has advantages over existing methods. BIO: Rotem Mulayoff received his B.Sc. degree in electrical engineering from the Technion in 2016, where he is currently working toward an M.Sc. degree. From 2014 to 2016, he worked in the field of signal processing and algorithms. Since 2016, he has been a Teaching Assistant with the Viterbi Faculty of Electrical Engineering, Technion. His main areas of interest includes statistical signal processing and sparse representations.

*M.Sc. student under the supervision of Prof. Tomer Michaeli