• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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

View/Open
1712.08800.pdf (1.635Mb)
Type
Article accepté pour publication ou publié
Date
2019
Journal name
SIAM Journal on Imaging Sciences
Volume
12
Number
3
Publisher
SIAM - Society for Industrial and Applied Mathematics
Pages
1464-1500
Publication identifier
10.1137/19M124071X
Metadata
Show full item record
Author(s)
Catala, Paul
Département de Mathématiques et Applications - ENS Paris [DMA]
Duval, Vincent cc
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Peyré, Gabriel
Département de Mathématiques et Applications - ENS Paris [DMA]
Abstract (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.
Subjects / Keywords
superresolution; semidefinite hierarchies, moment matrix, Frank--Wolfe

Related items

Showing items related by title and author.

  • Thumbnail
    A Low-Rank Approach to Off-The-Grid Sparse Deconvolution 
    Catala, Paul; Duval, Vincent; Peyré, Gabriel (2017) Article accepté pour publication ou publié
  • Thumbnail
    A Low-Rank Approach to Off-the-Grid Sparse Deconvolution 
    Catala, Paul; Duval, Vincent; Peyré, Gabriel (2017) Communication / Conférence
  • Thumbnail
    Sparse Spikes Super-resolution on Thin Grids II: the Continuous Basis Pursuit 
    Duval, Vincent; Peyré, Gabriel (2017) Document de travail / Working paper
  • Thumbnail
    Sparse Regularization on Thin Grids I: the LASSO 
    Duval, Vincent; Peyré, Gabriel (2017) Article accepté pour publication ou publié
  • Thumbnail
    Towards Off-the-Grid Algorithms for Total Variation Regularized Inverse Problems 
    De Castro, Yohann; Duval, Vincent; Petit, Romain (2022) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo