Fast Moreau envelope computation I: Numerical algorithms
From MaRDI portal
The paper is focused on the numerical computation of the discrete Moreau envelope of an extended real-valued function. The author is concerned with the numerical computation of the value of the Moreau envelope not only at one point but especially on a grid of points. The computation of the discrete Moreau envelope represents a quadratic worst-case time complexity. Here, a new linear-time nonexpansive proximal mapping algorithm to compute the discrete Moreau envelope on a grid is presented and its comparison with two algorithms which are well known -- the linear-time Legendre transform and parabolic envelope -- is given. The achieved results can be used in many fields such as image processing, robot navigation, etc. The numerical computation of the Moreau envelope and the proximal mapping of many functions and a comparison of the Moreau envelope algorithms is supported on \url{http://www.netlib.org/numeralgo/na24}.
Recommendations
- Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis
- A fast computational algorithm for the Legendre-Fenchel transform
- Faster than the fast Legendre transform, the linear-time Legendre transform
- Fast envelope algorithms
- A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation
Cites work
- A \(\mathcal{VU}\)-algorithm for convex minimization
- A Convergence Theory for Saddle Functions
- A family of variable metric proximal methods
- A fast computational algorithm for the Legendre-Fenchel transform
- A fast Legendre transform algorithm and applications to the adhesion model
- A Moreau-Yosida regularization of a difference of two convex functions
- A preconditioning proximal Newton method for nondifferentiable convex optimization
- A quasi-second-order proximal bundle algorithm
- A Variable Metric Proximal Point Algorithm for Monotone Operators
- Combining The Proximal Algorithm And Tikhonov Regularization
- Convergence analysis of a proximal newton method1
- Convex Analysis
- Coupling proximal methods and variational convergence
- Coupling the proximal point algorithm with approximation methods
- Distance transforms of sampled functions
- Entropic Proximal Mappings with Applications to Nonlinear Programming
- Entropy-Like Proximal Methods in Convex Programming
- Fast Legendre–Fenchel Transform and Applications to Hamilton–Jacobi Equations and Conservation Laws
- Fast Moreau envelope computation I: Numerical algorithms
- Faster than the fast Legendre transform, the linear-time Legendre transform
- Generalized Hessian Properties of Regularized Nonsmooth Functions
- Growth conditions and \(U\)-Lagrangians
- scientific article; zbMATH DE number 4092631 (Why is no real title available?)
- scientific article; zbMATH DE number 3678487 (Why is no real title available?)
- scientific article; zbMATH DE number 1306982 (Why is no real title available?)
- scientific article; zbMATH DE number 687723 (Why is no real title available?)
- scientific article; zbMATH DE number 1014811 (Why is no real title available?)
- scientific article; zbMATH DE number 1568991 (Why is no real title available?)
- scientific article; zbMATH DE number 823375 (Why is no real title available?)
- scientific article; zbMATH DE number 2201295 (Why is no real title available?)
- scientific article; zbMATH DE number 3187170 (Why is no real title available?)
- Kicked Burgers turbulence
- Lipschitz r-continuity of the approximative subdifferential of a convex function.
- Monotone Operators and the Proximal Point Algorithm
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- On \(\mathcal{VU}\)-theory for functions with primal-dual gradient structure
- On Second-Order Properties of the Moreau–Yosida Regularization for Constrained Nonsmooth Convex Programs
- On the Convergence of the Proximal Point Algorithm for Convex Minimization
- On the decay of Burgers turbulence
- On the relation between \(\mathcal U\)-Hessians and second-order epi-derivatives
- On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating
- Piecewise smoothness for Moreau-Yosida approximation to a piecewise C^2 convex function
- Practical Aspects of the Moreau--Yosida Regularization: Theoretical Preliminaries
- Primal-Dual Gradient Structured Functions: Second-Order Results; Links to Epi-Derivatives and Partly Smooth Functions
- Properties of the Moreau-Yosida regularization of a piecewise C^2 convex function
- Prox-regular functions in Hilbert spaces
- Prox-regular functions in variational analysis
- Prox-regularity of functions and sets in Banach spaces
- Proximité et dualité dans un espace hilbertien
- Quasi-Newton Bundle-Type Methods for Nondifferentiable Convex Optimization
- Second-order analysis of the Moreau-Yosida regularization
- Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization
- Singularities and the distribution of density in the Burgers/adhesion model
- Submonotone mappings and the proximal point algorithm
- The decay of multiscale signals -- a deterministic model of Burgers turbulence
- The inviscid Burgers equation with initial data of Brownian type
- The 𝒰-Lagrangian of a convex function
- Uniform prox-regularity of functions and epigraphs in Hilbert spaces
- Variable metric bundle methods: From conceptual to implementable forms
- 𝒱𝒰-smoothness and proximal point results for some nonconvex functions
Cited in
(26)- A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions
- Conditions for the existence, identification and calculus rules of the threshold of prox-boundedness
- Compensated convexity on bounded domains, mixed Moreau envelopes and computational methods
- Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time
- A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems
- Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions
- A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation
- Duality and Convex Programming
- Graph-matrix calculus for computational convex analysis
- Explicit formulas for \(C^{1,1}\) Glaeser-Whitney extensions of \(1\)-Taylor fields in Hilbert spaces
- Computing the conjugate of convex piecewise linear-quadratic bivariate functions
- Envelope computation in the plane by approximate implicitization
- Fast envelope algorithms
- Polar convolution
- Techniques and open questions in computational convex analysis
- A Decomposition Algorithm for Two-Stage Stochastic Programs with Nonconvex Recourse Functions
- Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis
- Convexity of the proximal average
- Compensated convex-based transforms for image processing and shape interrogation
- A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions
- A four-operator splitting algorithm for nonconvex and nonsmooth optimization
- Closest univariate convex linear-quadratic function approximation with minimal number of pieces
- Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
- A note on fast envelope estimation
- The piecewise linear-quadratic model for computational convex analysis
- Fast Moreau envelope computation I: Numerical algorithms
This page was built for publication: Fast Moreau envelope computation I: Numerical algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870763)
