• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

A Low-Rank Approach to Off-the-Grid Sparse Deconvolution

Thumbnail
View/Open
160198471340423.pdf (586.2Kb)
Date
2017
Alternative titles
Déconvolution parcimonieuse sans grille: une méthode de faible rang
Dewey
Traitement du signal
Sujet
Sparse deconvolution; Superresolution; SDP relaxations; Conditional gradient; Déconvolution; Parcimonie; Relaxations SDP; Frank Wolfe
Conference name
ORASIS 2017 - Journées francophones des jeunes chercheurs en vision par ordinateur, GREYC
Conference date
06-2017
Conference city
Colleville-sur-Mer
Conference country
France
URI
https://basepub.dauphine.fr/handle/123456789/21076
Collections
  • CEREMADE : Publications
Metadata
Show full item record
Author
Catala, Paul
66 Département de Mathématiques et Applications - ENS Paris [DMA]
Duval, Vincent
60 CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Peyré, Gabriel
66 Département de Mathématiques et Applications - ENS Paris [DMA]
Type
Communication / Conférence
Abstract (FR)
On s'intéresse à la résolution numérique du problème de déconvolution sans grille pour des mesures de Radon discrètes. Une approche courante consiste à introduire des relaxations semidéfinies positives (SDP) du problème variationnel associé, qui correspond ici à un problème de minimisation de variation totale. Cependant, pour des signaux de dimension supérieure à 1, les méthodes usuelles de points intérieurs sont peu efficaces pour résoudre le programme SDP correspondant, la taille de celui-ci étant de l'ordre de fc^{2d} où fc désigne la fréquence de coupure du filtre et d la dimension du signal. Nous introduisons en premier lieu une version pénalisée de la formulation SDP, dont les solutions sont de faible rang. Nous proposons ensuite un schéma numérique basé sur l'algorithme de Frank-Wolfe, capable d'exploiter efficacement d'une part cette propriété de faible rang, d'autre part l'aspect convolutif du problème; notre méthode atteint ainsi un coût de l'ordre de O(fc^d log fc) par itération. Nos simulations sont prometteuses, et montrent que l'algorithme converge en k étapes, k étant le nombre de Diracs dans la solution.
Abstract (EN)
We propose a new solver for the sparse spikes deconvolution problem over the space of Radon measures. A common approach to off-the-grid deconvolution considers semidefinite (SDP) relaxations of the total variation (i.e. the total mass of the measure) minimization problem. The direct resolution of this SDP is however intractable for large scale settings, since the problem size grows as f2dc where fc is the cutoff frequency of the filter. Our first contribution introduces a penalized formulation of this semidefinite lifting, which has low-rank solutions. Our second contribution is a conditional gradient (a.k.a. Frank-Wolfe) optimization scheme with non-convex updates. This algorithm leverages both the low-rank and the convolutive structure of the involvedvariable, resulting in an O(fdc log fc) complexity per iteration. Our numerical simulations are promising and show that this algorithm converges in exactly k steps, where k is the number of Diracs composing the solution.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.