Fast Moreau envelope computation I: Numerical algorithms (Q870763)

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}.