Tech Briefs

Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. Sparse modeling calls for constructing a succinct representation of some data as a combination of a few typical patterns (atoms) learned from the data itself.

A critical component of sparse modeling is the actual sparsity of the representation, which is controlled by a regularization term (regularizer, for short) and its associated parameters. The choice of the functional form of the regularizer and its parameters is a challenging task. Several solutions to this problem have been proposed, ranging from the automatic tuning of the parameters to Bayesian models, where these parameters are themselves considered as random variables.

A paper addresses this challenge by proposing a family of regularizers that is robust under the choice of their parameters. These regularizers are derived using tools from information theory; more specifically, from universal coding theory. The main idea is to consider sparse modeling as a code length minimization problem, where the regularizers define, through a probability assignment model, the code length associated with the description of the sparse representation coefficients.

Also included is the introduction of tools from universal modeling into the sparse world, which brings a fundamental and well supported theoretical angle to this very important and popular area of research. The remainder of this paper covers the standard framework of sparse modeling, the derivation of the proposed universal modeling framework and its implementation, and experimental results showing the practical benefits of the proposed framework for image representation and classification.

This work was done by Ignacio Ramirez and Guillermo Sapiro of the University of Minnesota. UMINN-0001

This Brief includes a Technical Support Package (TSP).

Universal Sparse Modeling (reference UMINN-0001) is currently available for download from the TSP library.

Please Login at the top of the page to download.