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

2 MOKAPLAN - Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales
CEREMADE - CEntre de REcherches en MAthématiques de la DEcision, Inria de Paris
Abstract : 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 (the total mass of the absolute value of the measure) minimization problem. The direct resolution of this 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 introduces a penalized formulation of this semidefinite lifting, which has low-rank solutions. Our second contribution is a conditional gradient optimization scheme with non-convex updates. This algorithm leverages both the low-rank and the convolutive 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.
Document type :
Journal articles
Domain :

https://hal.inria.fr/hal-01672896
Contributor : Vincent Duval Connect in order to contact the contributor
Submitted on : Wednesday, December 27, 2017 - 4:12:09 PM
Last modification on : Friday, January 21, 2022 - 3:09:46 AM

Citation

Paul Catala, Vincent Duval, Gabriel Peyré. A Low-Rank Approach to Off-The-Grid Sparse Deconvolution. SIAM Journal on Imaging Sciences, Society for Industrial and Applied Mathematics, 2019, 12 (3), pp.37. ⟨10.1137/19M124071X⟩. ⟨hal-01672896⟩

Metrics

Les métriques sont temporairement indisponibles