
A Low-Rank Approach to Off-the-Grid Sparse Superresolution
Catala, Paul; Duval, Vincent; Peyré, Gabriel (2019), A Low-Rank Approach to Off-the-Grid Sparse Superresolution, SIAM Journal on Imaging Sciences, 12, 3, p. 1464-1500. 10.1137/19M124071X
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2019Nom de la revue
SIAM Journal on Imaging SciencesVolume
12Numéro
3Éditeur
SIAM - Society for Industrial and Applied Mathematics
Pages
1464-1500
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Catala, PaulDépartement de Mathématiques et Applications - ENS Paris [DMA]
Duval, Vincent

CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Peyré, Gabriel
Département de Mathématiques et Applications - ENS Paris [DMA]
Résumé (EN)
We 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.Mots-clés
superresolution; semidefinite hierarchies, moment matrix, Frank--WolfePublications associées
Affichage des éléments liés par titre et auteur.
-
Catala, Paul; Duval, Vincent; Peyré, Gabriel (2017) Article accepté pour publication ou publié
-
Catala, Paul; Duval, Vincent; Peyré, Gabriel (2017) Communication / Conférence
-
Duval, Vincent; Peyré, Gabriel (2017) Document de travail / Working paper
-
Duval, Vincent; Peyré, Gabriel (2017) Article accepté pour publication ou publié
-
De Castro, Yohann; Duval, Vincent; Petit, Romain (2022) Article accepté pour publication ou publié