Concept

Sparse approximation

Résumé
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. The core sparse representation problem is defined as the quest for the sparsest possible representation satisfying . Due to the underdetermined nature of , this linear system admits in general infinitely many possible solutions, and among these we seek the one with the fewest non-zeros. Put formally, we solve where is the pseudo-norm, which counts the number of non-zero components of . This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in combinatorial optimization. Sparsity of implies that only a few () components in it are non-zero. The underlying motivation for such a sparse decomposition is the desire to provide the simplest possible explanation of as a linear combination of as few as possible columns from , also referred to as atoms. As such, the signal can be viewed as a molecule composed of a few fundamental elements taken from . While the above posed problem is indeed NP-Hard, its solution can often be found using approximation algorithms. One such option is a convex relaxation of the problem, obtained by using the -norm instead of , where simply sums the absolute values of the entries in . This is known as the basis pursuit (BP) algorithm, which can be handled using any linear programming solver. An alternative approximation method is a greedy technique, such as the matching pursuit (MP), which finds the location of the non-zeros one at a time.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (8)

Chargement

Chargement

Chargement

Personnes associées (17)
Unités associées

Chargement

Concepts associés (3)
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.
Acquisition comprimée
L'acquisition comprimée (en anglais compressed sensing) est une technique permettant de trouver la solution la plus parcimonieuse d'un système linéaire sous-déterminé. Elle englobe non seulement les moyens pour trouver cette solution mais aussi les systèmes linéaires qui sont admissibles. En anglais, elle porte le nom de Compressive sensing, Compressed Sampling ou Sparse Sampling.
Cours associés (5)
EE-726: Sparse stochastic processes
We cover the theory and applications of sparse stochastic processes (SSP). SSP are solutions of differential equations driven by non-Gaussian innovations. They admit a parsimonious representation in a
EE-556: Mathematics of data: from theory to computation
This course provides an overview of key advances in continuous optimization and statistical analysis for machine learning. We review recent learning formulations and models as well as their guarantees
PHYS-467: Machine learning for physicists
Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practi
Séances de cours associées (41)
Descente progressive stochastique: Techniques d'optimisation
Explore la descente stochastique du gradient et les techniques d'optimisation non lisses pour la sparté et la détection de compression.
Modèles probabilistes pour la régression linéaire
Couvre le modèle probabiliste de régression linéaire et ses applications dans la résonance magnétique nucléaire et l'imagerie par rayons X.
Sparse Communication: Transformations et applications
Explore l'évolution de la modélisation clairsemée à la communication clairsemée dans les réseaux neuronaux pour les tâches de traitement du langage naturel.
MOOCs associés

Aucun résultat