Dynamical Programming for off-the-grid dynamic Inverse Problems
Résumé
In this work we consider algorithms for reconstructing time-varying data into a finite sum of discrete trajectories, alternatively, an off-the-grid sparse-spikes decomposition which is continuous in time. Recent work showed that this decomposition was possible by minimising a convex variational model which combined a quadratic data fidelity with dynamical Optimal Transport. We generalise this framework and propose new numerical methods which leverage efficient classical algorithms for computing shortest paths on directed acyclic graphs. Our theoretical analysis confirms that these methods converge to globally optimal reconstructions which represent a finite number of discrete trajectories. Numerically, we show new examples for unbalanced Optimal Transport penalties, and for balanced examples we are 100 times faster in comparison to the previously known method.
Dans cet article, nous considérons des algorithmes de reconstruction sans grille pour des mesures parcimonieuses à partir de données dynamiques. En particulier, le signal reconstruit est une somme finie de mesures de Dirac dont les positions et les amplitudes varient continûment. Des travaux récents ont montré qu'une telle décomposition était possible dans un cadre variationnel convexe qui combine une attache aux données quadratique avec la formulation dynamique du transport optimal. Nous généralisons ce cadre et proposons une nouvelle méthode numérique qui exploite des algorithmes efficaces classiques de plus court chemin sur des graphes acycliques orientés. Notre analyse théorique confirme que ces méthodes convergent vers des minimiseurs globaux. Nous illustrons ces méthodes sur des exemples nouveaux impliquant le transport optimal non-équilibré, et, pour le transport classique, notre méthode est près de 100 fois plus rapide que l'état de l'art.
Origine : Fichiers produits par l'(les) auteur(s)