Accelerated Variational PDEs for Efficient Solution of Regularized Inversion Problems

Minas Benyamin, Jeff Calder, Ganesh Sundaramoorthi, Anthony Yezzi

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

We further develop a new framework, called PDE acceleration, by applying it to calculus of variation problems defined for general functions on Rn, obtaining efficient numerical algorithms to solve the resulting class of optimization problems based on simple discretizations of their corresponding accelerated PDEs. While the resulting family of PDEs and numerical schemes are quite general, we give special attention to their application for regularized inversion problems, with particular illustrative examples on some popular image processing applications. The method is a generalization of momentum, or accelerated, gradient descent to the PDE setting. For elliptic problems, the descent equations are a nonlinear damped wave equation, instead of a diffusion equation, and the acceleration is realized as an improvement in the CFL condition from Δt∼ Δx2 (for diffusion) to Δt∼ Δx (for wave equations). We work out several explicit as well as a semi-implicit numerical scheme, together with their necessary stability constraints, and include recursive update formulations which allow minimal-effort adaptation of existing gradient descent PDE codes into the accelerated PDE framework. We explore these schemes more carefully for a broad class of regularized inversion applications, with special attention to quadratic, Beltrami, and total variation regularization, where the accelerated PDE takes the form of a nonlinear wave equation. Experimental examples demonstrate the application of these schemes for image denoising, deblurring, and inpainting, including comparisons against primal–dual, split Bregman, and ADMM algorithms.

Original languageEnglish (US)
Pages (from-to)10-36
Number of pages27
JournalJournal of Mathematical Imaging and Vision
Volume62
Issue number1
DOIs
StatePublished - Jan 1 2020

Fingerprint

pulse detonation engines
Efficient Solution
Inversion
Wave equations
inversions
Gradient Descent
Nonlinear Wave Equation
Numerical Scheme
descent
wave equations
Total Variation Regularization
Semi-implicit Scheme
Deblurring
Inpainting
Damped Wave Equation
Image denoising
Image Denoising
Calculus of variations
Descent
Diffusion equation

Keywords

  • Accelerated gradient descent
  • Beltrami regularization
  • Image deblurring
  • Image denoising
  • Image restoration
  • Nesterov acceleration
  • Nonlinear wave equations
  • PDE acceleration
  • Total variation

Cite this

Accelerated Variational PDEs for Efficient Solution of Regularized Inversion Problems. / Benyamin, Minas; Calder, Jeff; Sundaramoorthi, Ganesh; Yezzi, Anthony.

In: Journal of Mathematical Imaging and Vision, Vol. 62, No. 1, 01.01.2020, p. 10-36.

Research output: Contribution to journalArticle

Benyamin, Minas ; Calder, Jeff ; Sundaramoorthi, Ganesh ; Yezzi, Anthony. / Accelerated Variational PDEs for Efficient Solution of Regularized Inversion Problems. In: Journal of Mathematical Imaging and Vision. 2020 ; Vol. 62, No. 1. pp. 10-36.
@article{26e5277f504c4f3b809d379d275124dc,
title = "Accelerated Variational PDEs for Efficient Solution of Regularized Inversion Problems",
abstract = "We further develop a new framework, called PDE acceleration, by applying it to calculus of variation problems defined for general functions on Rn, obtaining efficient numerical algorithms to solve the resulting class of optimization problems based on simple discretizations of their corresponding accelerated PDEs. While the resulting family of PDEs and numerical schemes are quite general, we give special attention to their application for regularized inversion problems, with particular illustrative examples on some popular image processing applications. The method is a generalization of momentum, or accelerated, gradient descent to the PDE setting. For elliptic problems, the descent equations are a nonlinear damped wave equation, instead of a diffusion equation, and the acceleration is realized as an improvement in the CFL condition from Δt∼ Δx2 (for diffusion) to Δt∼ Δx (for wave equations). We work out several explicit as well as a semi-implicit numerical scheme, together with their necessary stability constraints, and include recursive update formulations which allow minimal-effort adaptation of existing gradient descent PDE codes into the accelerated PDE framework. We explore these schemes more carefully for a broad class of regularized inversion applications, with special attention to quadratic, Beltrami, and total variation regularization, where the accelerated PDE takes the form of a nonlinear wave equation. Experimental examples demonstrate the application of these schemes for image denoising, deblurring, and inpainting, including comparisons against primal–dual, split Bregman, and ADMM algorithms.",
keywords = "Accelerated gradient descent, Beltrami regularization, Image deblurring, Image denoising, Image restoration, Nesterov acceleration, Nonlinear wave equations, PDE acceleration, Total variation",
author = "Minas Benyamin and Jeff Calder and Ganesh Sundaramoorthi and Anthony Yezzi",
year = "2020",
month = "1",
day = "1",
doi = "10.1007/s10851-019-00910-2",
language = "English (US)",
volume = "62",
pages = "10--36",
journal = "Journal of Mathematical Imaging and Vision",
issn = "0924-9907",
publisher = "Springer Netherlands",
number = "1",

}

TY - JOUR

T1 - Accelerated Variational PDEs for Efficient Solution of Regularized Inversion Problems

AU - Benyamin, Minas

AU - Calder, Jeff

AU - Sundaramoorthi, Ganesh

AU - Yezzi, Anthony

PY - 2020/1/1

Y1 - 2020/1/1

N2 - We further develop a new framework, called PDE acceleration, by applying it to calculus of variation problems defined for general functions on Rn, obtaining efficient numerical algorithms to solve the resulting class of optimization problems based on simple discretizations of their corresponding accelerated PDEs. While the resulting family of PDEs and numerical schemes are quite general, we give special attention to their application for regularized inversion problems, with particular illustrative examples on some popular image processing applications. The method is a generalization of momentum, or accelerated, gradient descent to the PDE setting. For elliptic problems, the descent equations are a nonlinear damped wave equation, instead of a diffusion equation, and the acceleration is realized as an improvement in the CFL condition from Δt∼ Δx2 (for diffusion) to Δt∼ Δx (for wave equations). We work out several explicit as well as a semi-implicit numerical scheme, together with their necessary stability constraints, and include recursive update formulations which allow minimal-effort adaptation of existing gradient descent PDE codes into the accelerated PDE framework. We explore these schemes more carefully for a broad class of regularized inversion applications, with special attention to quadratic, Beltrami, and total variation regularization, where the accelerated PDE takes the form of a nonlinear wave equation. Experimental examples demonstrate the application of these schemes for image denoising, deblurring, and inpainting, including comparisons against primal–dual, split Bregman, and ADMM algorithms.

AB - We further develop a new framework, called PDE acceleration, by applying it to calculus of variation problems defined for general functions on Rn, obtaining efficient numerical algorithms to solve the resulting class of optimization problems based on simple discretizations of their corresponding accelerated PDEs. While the resulting family of PDEs and numerical schemes are quite general, we give special attention to their application for regularized inversion problems, with particular illustrative examples on some popular image processing applications. The method is a generalization of momentum, or accelerated, gradient descent to the PDE setting. For elliptic problems, the descent equations are a nonlinear damped wave equation, instead of a diffusion equation, and the acceleration is realized as an improvement in the CFL condition from Δt∼ Δx2 (for diffusion) to Δt∼ Δx (for wave equations). We work out several explicit as well as a semi-implicit numerical scheme, together with their necessary stability constraints, and include recursive update formulations which allow minimal-effort adaptation of existing gradient descent PDE codes into the accelerated PDE framework. We explore these schemes more carefully for a broad class of regularized inversion applications, with special attention to quadratic, Beltrami, and total variation regularization, where the accelerated PDE takes the form of a nonlinear wave equation. Experimental examples demonstrate the application of these schemes for image denoising, deblurring, and inpainting, including comparisons against primal–dual, split Bregman, and ADMM algorithms.

KW - Accelerated gradient descent

KW - Beltrami regularization

KW - Image deblurring

KW - Image denoising

KW - Image restoration

KW - Nesterov acceleration

KW - Nonlinear wave equations

KW - PDE acceleration

KW - Total variation

UR - http://www.scopus.com/inward/record.url?scp=85074065035&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074065035&partnerID=8YFLogxK

U2 - 10.1007/s10851-019-00910-2

DO - 10.1007/s10851-019-00910-2

M3 - Article

AN - SCOPUS:85074065035

VL - 62

SP - 10

EP - 36

JO - Journal of Mathematical Imaging and Vision

JF - Journal of Mathematical Imaging and Vision

SN - 0924-9907

IS - 1

ER -