Implementation of an optimal first-order method for strongly convex total variation regularization

DOI10.1007/S10543-011-0359-8zbMATH Open1256.65063arXiv1105.3723OpenAlexW2097726319MaRDI QIDQ438730FDOQ438730

Authors: T. L. Jensen, Per Christian Hansen, S. H. Jensen, J. H. Jørgensen 

Publication date: 31 July 2012

Published in: BIT (Search for Journal in Brave)

Abstract: We present a practical implementation of an optimal first-order method, due to Nesterov, for large-scale total variation regularization in tomographic reconstruction, image deblurring, etc. The algorithm applies to $mu$-strongly convex objective functions with $L$-Lipschitz continuous gradient. In the framework of Nesterov both $mu$ and $L$ are assumed known -- an assumption that is seldom satisfied in practice. We propose to incorporate mechanisms to estimate locally sufficient $mu$ and $L$ during the iterations. The mechanisms also allow for the application to non-strongly convex functions. We discuss the iteration complexity of several first-order methods, including the proposed algorithm, and we use a 3D tomography problem to compare the performance of these methods. The results show that for ill-conditioned problems solved to high accuracy, the proposed method significantly outperforms state-of-the-art first-order methods, as also suggested by theoretical results.

Full work available at URL: https://arxiv.org/abs/1105.3723

Recommendations

• Efficient schemes for total variation minimization under constraints in image processing
• Algorithms and software for total variation image reconstruction via first-order methods
• Some first-order algorithms for total variation based image restoration
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Scaled, inexact, and adaptive generalized FISTA for strongly convex optimization

zbMATH Keywords

numerical examplestomographytotal variation regularizationNesterov's methodgradient projection algorithmstrong convexitylarge scale problemsfirst-order optimization algorithmsoftware FISTAtomographic reconstruction

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Existence theories for optimal control problems involving partial differential equations (49J20) Numerical methods for inverse problems for integral equations (65R32)

Cites Work

• NESTA: A fast and accurate first-order method for sparse recovery
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Templates for convex cone problems with applications to sparse signal recovery
• Nonlinear total variation based noise removal algorithms
• Title not available (Why is that?)
• Fundamentals of Computerized Tomography
• Smooth minimization of non-smooth functions
• Introductory lectures on convex optimization. A basic course.
• Nonmonotone Spectral Projected Gradient Methods on Convex Sets
• Image Processing and Analysis
• The Barzilai and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem
• Two-Point Step Size Gradient Methods
• Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems
• An algorithm for total variation minimization and applications
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A Nonmonotone Line Search Technique for Newton’s Method
• An Infeasible Primal-Dual Algorithm for Total Bounded Variation--Based Inf-Convolution-Type Image Restoration
• Principles of computerized tomography imaging
• A Nonlinear Primal-Dual Method for Total Variation-Based Image Restoration
• Duality-based algorithms for total-variation-regularized image restoration
• Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
• Image restoration with discrete constrained total variation. I: Fast and exact optimization
• Iterative Methods for Total Variation Denoising
• Discrete inverse problems. Insight and algorithms.
• \(R\)-linear convergence of the Barzilai and Borwein gradient method
• Second-order Cone Programming Methods for Total Variation-Based Image Restoration
• Efficient schemes for total variation minimization under constraints in image processing
• Algorithms and software for total variation image reconstruction via first-order methods

Cited In (17)

• Variational image restoration and segmentation with Rician noise
• Multiresolution parameter choice method for total variation regularized tomography
• A convergent least-squares regularized blind deconvolution approach
• A direct sampling method for the inversion of the Radon transform
• Scaled projected-directions methods with application to transmission tomography
• Simultaneous tomographic reconstruction and segmentation with class priors
• A tensor-based dictionary learning approach to tomographic image reconstruction
• Reconstruction of 3D X-ray CT images from reduced sampling by a scaled gradient projection algorithm
• Tomographic image reconstruction using training images
• Distance computation of ontology vector for ontology similarity measuring and ontology mapping
• A framework for regularization via operator approximation
• A variable metric forward-backward method with extrapolation
• Benchmarking large-scale distributed convex quadratic programming algorithms
• Superiorization of incremental optimization algorithms for statistical tomographic image reconstruction
• A unified analysis of stochastic gradient‐free Frank–Wolfe methods
• Conditional gradient type methods for composite nonlinear and stochastic optimization
• Stability of quasi-simple heteroclinic cycles

Uses Software

• Matlab
• NESTA
• na28
• TFOCS
• TwIST

This page was built for publication: Implementation of an optimal first-order method for strongly convex total variation regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q438730)