Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
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.
Source officielle
À 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.
Cours associés (7)
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
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
ME-371: Discretization methods in fluids
Ce cours présente une introduction aux méthodes d'approximation utilisées pour la simulation numérique en mécanique des fluides.
Les concepts fondamentaux sont présentés dans le cadre de la méthode d
Séances de cours associées (32)
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.
Descente progressive prévue: Convergence et optimisation
Explore Projected Gradient Descent pour les systèmes d'optimisation et de contrôle.
Personnes associées (65)
Unités associées (7)
Concepts associés (2)
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.