## na24

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 |

all
top 5

### Referenced by 22 Authors

all
top 5

### Referenced in 9 Serials

all
top 5