Show simple item record

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

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.accessioned2019-09-24T12:30:36Z
dc.date.available2019-09-24T12:30:36Z
dc.date.issued2019
dc.identifier.issn1936-4954
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19906
dc.language.isoenen
dc.subjectsuperresolutionen
dc.subjectsemidefinite hierarchies, moment matrix, Frank--Wolfeen
dc.subject.ddc515en
dc.titleA Low-Rank Approach to Off-the-Grid Sparse Superresolutionen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe propose a new solver for the sparse spikes superresolution problem over the space of Radon measures. A common approach to off-the-grid deconvolution considers semidefinite relaxations of the total variation (the total mass of the absolute value of the measure) minimization problem. The direct resolution of this semidefinite program (SDP) is, however, intractable for large scale settings, since the problem size grows as $f_c^{2d}$, where $f_c$ is the cutoff frequency of the filter and $d$ the ambient dimension. Our first contribution is a Fourier approximation scheme of the forward operator, making the TV-minimization problem expressible as an SDP. Our second contribution introduces a penalized formulation of this semidefinite lifting, which we prove to have low-rank solutions. Our last contribution is the FFW algorithm, a Fourier-based Frank--Wolfe scheme with nonconvex updates. FFW leverages both the low-rank and the Fourier structure of the problem, resulting in an $O(f_c^d \log f_c)$ complexity per iteration. Numerical simulations are promising and show that the algorithm converges in exactly $r$ steps, $r$ being the number of Diracs composing the solution.en
dc.relation.isversionofjnlnameSIAM Journal on Imaging Sciences
dc.relation.isversionofjnlvol12en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2019-08
dc.relation.isversionofjnlpages1464-1500en
dc.relation.isversionofdoi10.1137/19M124071Xen
dc.relation.isversionofjnlpublisherSIAM - Society for Industrial and Applied Mathematicsen
dc.subject.ddclabelAnalyseen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-09-24T12:28:32Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
1712.08800.pdf
Size:
1.635Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record