Ê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 GraphSearch.
Concept
Poursuite de base
Résumé
La poursuite de base (de l'anglais basis pursuit), aussi appelée recouvrement par norme ou plus simplement recouvrement , est une technique d'optimisation mathématique utilisée initialement en traitement du signal qui revient à résoudre un problème d'optimisation de la forme
où l'inconnue est un vecteur formé de nombres réels, est la norme ,
est une matrice réelle et . Il s'agit donc de trouver le plus petit vecteur , au sens de la norme , qui vérifie l'équation affine Ce problème est convexe (l'objectif est convexe et l'ensemble admissible est affine, donc convexe), mais non lisse (la norme n'est pas partout différentiable).
Le contexte dans lequel intervient le recouvrement est décrit dans l'article Acquisition comprimée.
Comme nous le verrons, l'intérêt du problème est de sélectionner une solution du système linéaire , supposé sous-déterminé, ayant le moins d'éléments non nuls possible (ou presque). La non-différentiabilité de la norme joue un rôle-clé dans l'obtention de cette propriété.
L'appellation poursuite de base vient de l'algorithme du simplexe qui était proposé dans l'article original pour résoudre le problème ci-dessus, lequel détermine une base optimale. Dans la terminologie de cet algorithme, il s'agit d'une sélection de colonnes de , supposée surjective en l'occurrence, telle que la sous-matrice correspondante soit inversible et détermine la solution par .
Connaissances supposées : le vocabulaire de l'optimisation mathématique et de l'algèbre linéaire.
Voici comment on peut être amené à résoudre un problème d'optimisation de la forme ci-dessus.
Un problème classique en traitement du signal consiste à trouver une décomposition parcimonieuse (c'est-à-dire formée de peu d'éléments) d'un signal donné dans un dictionnaire surabondant de signaux, contenant par exemple des sinusoïdes (décomposition de Fourier), des ondelettes Dans l'écriture ci-dessus, le vecteur est le signal à décomposer, les colonnes de la matrice de type sont les éléments du dictionnaire de signaux et les composantes de sont les coefficients recherchés pour représenter le signal au moyen des signaux du dictionnaire.
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.