Show simple item record

hal.structure.identifierDépartement de Mathématiques et Applications - ENS Paris [DMA]
dc.contributor.authorCatala, Paul
hal.structure.identifierCEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
dc.contributor.authorDuval, Vincent
HAL ID: 7243
ORCID: 0000-0002-7709-256X
hal.structure.identifierDépartement de Mathématiques et Applications - ENS Paris [DMA]
dc.contributor.authorPeyré, Gabriel
HAL ID: 1211
dc.date.accessioned2020-10-06T12:01:10Z
dc.date.available2020-10-06T12:01:10Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/21076
dc.description.abstractfrOn 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.en
dc.language.isofren
dc.subjectSparse deconvolutionen
dc.subjectSuperresolutionen
dc.subjectSDP relaxationsen
dc.subjectConditional gradienten
dc.subjectDéconvolutionen
dc.subjectParcimonieen
dc.subjectRelaxations SDPen
dc.subjectFrank Wolfeen
dc.subject.ddc621.3en
dc.titleA Low-Rank Approach to Off-the-Grid Sparse Deconvolutionen
dc.title.alternativeDéconvolution parcimonieuse sans grille: une méthode de faible rangen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.subject.ddclabelTraitement du signalen
dc.relation.conftitleORASIS 2017 - Journées francophones des jeunes chercheurs en vision par ordinateur, GREYCen
dc.relation.confdate2017-06
dc.relation.confcityColleville-sur-Meren
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-10-06T11:56:31Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record