Publication

Sparse Approximation by Linear Programming: Measuring the Error with the $ell_1$ Norm

Pierre Vandergheynst
2005
Reports

Résumé

In this report we study the problem of sparse signal approximation over redundant dictionaries. We focus our attention on the minimization of a cost function where the error is measured using a l1 norm. We show a constructive equivalence between this minimization and Linear Programming. A recovery condition is then proved and finally we provide an example of the use of such a technique for denoising.

Source officielle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Pierre Vandergheynst
2005
Reports

Résumé

Source officielle

Concepts associés (32)

Sparse dictionary learning

Sparse dictionary learning (also known as sparse coding or SDL) is a representation learning method which aims at finding a sparse representation of the input data in the form of a linear combination of basic elements as well as those basic elements themselves. These elements are called atoms and they compose a dictionary. Atoms in the dictionary are not required to be orthogonal, and they may be an over-complete spanning set. This problem setup also allows the dimensionality of the signals being represented to be higher than the one of the signals being observed.

Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in , signal processing, machine learning, medical imaging, and more. Consider a linear system of equations , where is an underdetermined matrix and . The matrix (typically assumed to be full-rank) is referred to as the dictionary, and is a signal of interest.

Matching pursuit

Matching pursuit (MP) is a sparse approximation algorithm which finds the "best matching" projections of multidimensional data onto the span of an over-complete (i.e., redundant) dictionary . The basic idea is to approximately represent a signal from Hilbert space as a weighted sum of finitely many functions (called atoms) taken from . An approximation with atoms has the form where is the th column of the matrix and is the scalar weighting factor (amplitude) for the atom . Normally, not every atom in will be used in this sum.

Afficher plus

Publications associées (16)

Afficher plus

Sparse Approximation by Linear Programming: Measuring the Error with the $ell_1$ Norm

Chattez avec Graph Search

Scalable Choice-Based Optimization with Decomposition and Breakpoint-Based Methods

Systematic Analysis of Energy Transition Pathways for Emission Reduction in the Flat Glass Industry Using MILP Formulation

Optical Implementation of Denoising Diffusion Models for Efficient Image Generation