Solving Linear Inverse Problems using Higher-Order Annealed Langevin Diffusion

• URL: http://arxiv.org/abs/2305.05014v4
• Date: Wed, 6 Dec 2023 14:11:40 GMT
• Title: Solving Linear Inverse Problems using Higher-Order Annealed Langevin Diffusion
• Authors: Nicolas Zilberstein, Ashutosh Sabharwal, Santiago Segarra
• Abstract summary: We propose a solution for linear inverse problems based on Langevin diffusion. We prove that both pre-conditioned dynamics are well-defined and have the same unique invariant distributions as the non-conditioned cases.
• Score: 36.230439476675826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a solution for linear inverse problems based on higher-order Langevin diffusion. More precisely, we propose pre-conditioned second-order and third-order Langevin dynamics that provably sample from the posterior distribution of our unknown variables of interest while being computationally more efficient than their first-order counterpart and the non-conditioned versions of both dynamics. Moreover, we prove that both pre-conditioned dynamics are well-defined and have the same unique invariant distributions as the non-conditioned cases. We also incorporate an annealing procedure that has the double benefit of further accelerating the convergence of the algorithm and allowing us to accommodate the case where the unknown variables are discrete. Numerical experiments in two different tasks in communications (MIMO symbol detection and channel estimation) and in three tasks for images showcase the generality of our method and illustrate the high performance achieved relative to competing approaches (including learning-based ones) while having comparable or lower computational complexity.

Related papers

• Distributed Optimization via Energy Conservation Laws in Dilated Coordinates [5.35599092568615]
  This paper introduces an energy conservation approach for analyzing continuous-time dynamical systems in dilated coordinates. convergence rates can be explicitly expressed in terms of the inverse time-dilation factor. Its accelerated convergence behavior is benchmarked against various state-of-the-art distributed optimization algorithms on practical, large-scale problems.
  arXiv  Detail & Related papers  (2024-09-28T08:02:43Z)
• State-Free Inference of State-Space Models: The Transfer Function Approach [132.83348321603205]
  State-free inference does not incur any significant memory or computational cost with an increase in state size. We achieve this using properties of the proposed frequency domain transfer function parametrization. We report improved perplexity in language modeling over a long convolutional Hyena baseline.
  arXiv  Detail & Related papers  (2024-05-10T00:06:02Z)
• Proximal Algorithms for Accelerated Langevin Dynamics [57.08271964961975]
  We develop a novel class of MCMC algorithms based on a stochastized Nesterov scheme. We show superior performance of the proposed method over typical Langevin samplers for different models in statistics and image processing.
  arXiv  Detail & Related papers  (2023-11-24T19:56:01Z)
• Enhancing Low-Order Discontinuous Galerkin Methods with Neural Ordinary Differential Equations for Compressible Navier--Stokes Equations [0.1578515540930834]
  We introduce an end-to-end differentiable framework for solving the compressible Navier-Stokes equations. This integrated approach combines a differentiable discontinuous Galerkin solver with a neural network source term. We demonstrate the performance of the proposed framework through two examples.
  arXiv  Detail & Related papers  (2023-10-29T04:26:23Z)
• Comparison of Single- and Multi- Objective Optimization Quality for Evolutionary Equation Discovery [77.34726150561087]
  Evolutionary differential equation discovery proved to be a tool to obtain equations with less a priori assumptions. The proposed comparison approach is shown on classical model examples -- Burgers equation, wave equation, and Korteweg - de Vries equation.
  arXiv  Detail & Related papers  (2023-06-29T15:37:19Z)
• Reweighted Interacting Langevin Diffusions: an Accelerated Sampling Methodfor Optimization [28.25662317591378]
  We propose a new technique to accelerate sampling methods for solving difficult optimization problems. Our method investigates the connection between posterior distribution sampling and optimization with Langevin dynamics.
  arXiv  Detail & Related papers  (2023-01-30T03:48:20Z)
• Second Order Ensemble Langevin Method for Sampling and Inverse Problems [10.406582941856099]
  We propose a sampling method based on an ensemble approximation of Langevin dynamics. Numerical results demonstrate its potential as the basis for a numerical sampler in inverse problems.
  arXiv  Detail & Related papers  (2022-08-09T02:17:22Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Convex Analysis of the Mean Field Langevin Dynamics [49.66486092259375]
  convergence rate analysis of the mean field Langevin dynamics is presented. $p_q$ associated with the dynamics allows us to develop a convergence theory parallel to classical results in convex optimization.
  arXiv  Detail & Related papers  (2022-01-25T17:13:56Z)
• Sharp global convergence guarantees for iterative nonconvex optimization: A Gaussian process perspective [30.524043513721168]
  We develop a general recipe for analyzing the convergence of iterative algorithms for a class of regression models. deterministicly, we accurately capture both the convergence rate of the algorithm and the eventual error floor in the finite-sample regime. We show sharp convergence rates for both higher-order algorithms based on alternating updates and first-order algorithms based on subgradient subgradients.
  arXiv  Detail & Related papers  (2021-09-20T21:48:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.