swMATH ID: 11485
Software Authors: Lucet, Yves
Description: Fast Moreau envelope computation I: Numerical algorithms. The present article summarizes the state of the art algorithms to compute the discrete Moreau envelope, and presents a new linear-time algorithm, named NEP for NonExpansive Proximal mapping. Numerical comparisons between the NEP and two existing algorithms: The Linear-time Legendre Transform (LLT) and the Parabolic Envelope (PE) algorithms are performed. Worst-case time complexity, convergence results, and examples are included. The fast Moreau envelope algorithms first factor the Moreau envelope as several one-dimensional transforms and then reduce the brute force quadratic worst-case time complexity to linear time by using either the equivalence with Fast Legendre Transform algorithms, the computation of a lower envelope of parabolas, or, in the convex case, the non expansiveness of the proximal mapping.
Homepage: http://www.netlib.org/numeralgo/
Dependencies: netlib; numeralgo
Keywords: discrete Moreau envelope; Moreau-Yosida approximate; proximal mapping; Legendre-Fenchel transform; quadratic worst-case time complexity
Related Software: na13; Scilab; CCA; SCAT; fenchel; CGAL; Qhull; POGS; TFOCS; UNLocBoX; CVXGEN; PDCO; CSHEP2D
Referenced in: 16 Publications

Referencing Publications by Year