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.
Keywords for this software
References in zbMATH (referenced in 10 articles )
Showing results 1 to 10 of 10.
- Borwein, Jonathan M.; Luke, D.Russell: Duality and convex programming (2015)
- Gardiner, Bryan; Jakee, Khan; Lucet, Yves: Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions (2014)
- Gardiner, Bryan; Lucet, Yves: Computing the conjugate of convex piecewise linear-quadratic bivariate functions (2013)
- Lucet, Yves: Techniques and open questions in computational convex analysis (2013)
- Gardiner, Bryan; Lucet, Yves: Graph-matrix calculus for computational convex analysis (2011)
- Johnstone, Jennifer A.; Koch, Valentin R.; Lucet, Yves: Convexity of the proximal average (2011)
- Gardiner, Bryan; Lucet, Yves: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis (2010)
- Lucet, Yves; Bauschke, Heinz H.; Trienis, Mike: The piecewise linear-quadratic model for computational convex analysis (2009)
- Bauschke, Heinz H.; Lucet, Yves; Trienis, Michael: How to transform one convex function continuously into another (2008)
- Lucet, Yves: Fast Moreau envelope computation I: Numerical algorithms (2006)