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.

References in zbMATH (referenced in 16 articles )

Showing results 1 to 16 of 16.
Sorted by year (citations)

  1. Planiden, C.: Conditions for the existence, identification and calculus rules of the threshold of prox-boundedness (2021)
  2. Zhang, Kewei; Orlando, Antonio; Crooks, Elaine: Compensated convexity on bounded domains, mixed Moreau envelopes and computational methods (2021)
  3. Kumar, Deepak; Lucet, Yves: Computation of the epsilon-subdifferential of convex piecewise linear-quadratic functions in optimal worst-case time (2019)
  4. Liu, Tianxiang; Pong, Ting Kei; Takeda, Akiko: A successive difference-of-convex approximation method for a class of nonconvex nonsmooth optimization problems (2019)
  5. Daniilidis, Aris; Haddou, Mounir; Le Gruyer, Erwan; Ley, Olivier: Explicit formulas for (C^1,1) Glaeser-Whitney extensions of (1)-Taylor fields in Hilbert spaces (2018)
  6. Haque, Tasnuva; Lucet, Yves: A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions (2018)
  7. Borwein, Jonathan M.; Luke, D. Russell: Duality and convex programming (2015)
  8. Gardiner, Bryan; Jakee, Khan; Lucet, Yves: Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions (2014)
  9. Gardiner, Bryan; Lucet, Yves: Computing the conjugate of convex piecewise linear-quadratic bivariate functions (2013)
  10. Lucet, Yves: Techniques and open questions in computational convex analysis (2013)
  11. Gardiner, Bryan; Lucet, Yves: Graph-matrix calculus for computational convex analysis (2011)
  12. Johnstone, Jennifer A.; Koch, Valentin R.; Lucet, Yves: Convexity of the proximal average (2011)
  13. Gardiner, Bryan; Lucet, Yves: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis (2010)
  14. Lucet, Yves; Bauschke, Heinz H.; Trienis, Mike: The piecewise linear-quadratic model for computational convex analysis (2009)
  15. Bauschke, Heinz H.; Lucet, Yves; Trienis, Michael: How to transform one convex function continuously into another (2008)
  16. Lucet, Yves: Fast Moreau envelope computation I: Numerical algorithms (2006)