Abstract

A new algorithm, named the Parametric Legendre Transform (PLT) algorithm, to compute the Legendre-Fenchel conjugate of a convex function of one variable is presented. It returns a parameterization of the graph of the conjugate except for some affine parts corresponding to nondifferentiable points of the function. The approach is extended to the computation of the Moreau envelope, resulting in a simple yet efficient algorithm. Theoretical results, the description (and extension) of the algorithm, its approximation error and the convergence, as well as the comparison with known algorithms are included.

Author information

Contact details are reproduced from the original publication and may be historical.

Jean-Baptiste Hiriart-Urruty

Laboratoire de Mathématiques pour l'Industrie et la Physique, Institut de Mathématiques, Université Paul Sabatier, 118 Route de Narbonne, 31062 Toulouse, France

jbhu@cict.fr

Yves Lucet

Dept. of Computer Science, I. K. Barber School of Arts and Sciences, University of British Columbia, Okanagan – 3333 University Way, Kelowna BC V1V 1V7, Canada

yves.lucet@ubc.ca

Keywords

  • Legendre-Fenchel transform
  • Fenchel conjugate
  • Moreau envelope
  • Moreau-Yosida regularization
  • fast algorithm
  • computational convex analysis

Mathematics Subject Classification

65Y20, 52A41, 90C25

References

  1. D. G. Bailey: An efficient Euclidean distance transform, in: Combinatorial Image Analysis (Auckland, 2004), R. Klette, J. Žunić (eds.), Lecture Notes in Computer Science 3322, Springer, Berlin (2004) 394–408.https://doi.org/10.1007/978-3-540-30503-3_28Google Scholar
  2. H. Bauschke, M. von Mohrenschildt: Symbolic computation of Fenchel conjugates, ACM SIGSAM Bulletin, to appear.Google Scholar
  3. H. H. Bauschke, M. von Mohrenschildt: Fenchel conjugates and subdifferentials in Maple, Tech. Rep. CORR 97-23, Department of Combinatorics and Optimization, University of Waterloo, Waterloo (1997).Google Scholar
  4. J. Benoist, J.-B. Hiriart-Urruty: What is the subdifferential of the closed convex hull of a function?, SIAM J. Math. Anal. 27 (1996) 1661–1679.https://doi.org/10.1137/S0036141094265936Google Scholar
  5. J. Borwein, A. S. Lewis: Convex Analysis and Nonlinear Optimization. Theory and Examples, CMS Books in Mathematics 3, Springer, New York (2000).https://doi.org/10.1007/978-1-4757-9859-3Google Scholar
  6. L. Corrias: Fast Legendre-Fenchel transform and applications to Hamilton Jacobi equations and conservation laws, SIAM J. Numer. Anal. 33 (1996) 1534–1558.https://doi.org/10.1137/S0036142993260208Google Scholar
  7. O. Cuisenaire, B. Macq: Fast and exact signed Euclidean distance transformation with linear complexity, in: Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing (Phoenix, 1999), IEEE Computer Society Press (1999) 3293–3296.https://doi.org/10.1109/ICASSP.1999.757545Google Scholar
  8. P. F. Felzenszwalb, D. P. Huttenlocher: Distance transforms of sampled functions, Tech. Rep. TR2004-1963, Cornell Computing and Information Science, Cornell University, Cornell (2004).Google Scholar
  9. M. Gavrilova, M. H. Alsuwaiyel: Two algorithms for computing the euclidean distance transform, Tech. Rep. 2000-661-13, Computer Science Technical Reports, University of Calgary, Calgary (2000).Google Scholar
  10. C. H. Hamilton: Symbolic Convex Analysis, M.Sc. Thesis, Department of Mathematics, Simon Fraser University, Burnaby (2005).Google Scholar
  11. W. Hesselink: A linear-time algorithm for euclidean feature transform sets, available at http://www.cs.rug.nl/~wim/pub/mans.html (2005).Google Scholar
  12. J.-B. Hiriart-Urruty: Lipschitz r-continuity of the approximate subdifferential of a convex function, Math. Scand. 47 (1980) 123–134.https://doi.org/10.7146/math.scand.a-11878Google Scholar
  13. J.-B. Hiriart-Urruty, C. Lemaréchal: Convex Analysis and Minimization Algorithms, I: Fundamentals; II: Advanced Theory and Bundle Methods, Comprehensive Studies in Mathematics 305, 306, Springer, Berlin (1993).https://doi.org/10.1007/978-3-662-06409-2Google Scholar
  14. J. Toriwaki, K. Mori: Distance transformation and skeletonization of 3d pictures and their applications to medical images, in: Digital and Image Geometry: Advanced Lectures, G. Bertrand et al. (ed.), Lecture Notes in Computer Science 2243, Springer, Berlin (2001) 412–429.https://doi.org/10.1007/3-540-45576-0_25Google Scholar
  15. C. R. Maurer Jr., R. Qi, V. V. Raghavan: A linear time algorithm for computing exact euclidean distance transforms of binary images in arbitrary dimensions, IEEE Trans. Pattern Anal. Mach. Intell. 25 (2003) 265–270.https://doi.org/10.1109/TPAMI.2003.1177156Google Scholar
  16. Y. Lucet: A fast computational algorithm for the Legendre-Fenchel transform, Comput. Optim. Appl. 6 (1996) 27–57.https://doi.org/10.1007/BF00248008Google Scholar
  17. Y. Lucet: Faster than the fast Legendre transform, the linear-time Legendre transform, Numer. Algorithms 16 (1997) 171–185.https://doi.org/10.1023/A:1019191114493Google Scholar
  18. Y. Lucet: Fast Moreau envelope computation I: Numerical algorithms, Tech. Rep., University of British Columbia Okanagan, Kelowna (2005).Google Scholar
  19. Y. Lucet: A linear euclidean distance transform algorithm based on the linear-time Legendre transform, in: Proc. Second Canadian Conference on Computer and Robot Vision (Victoria, 2005), IEEE Computer Society Press (2005) 262–267.https://doi.org/10.1109/CRV.2005.7Google Scholar
  20. S. Mauch: A fast algorithm for computing the closest point and distance transform, Tech. Rep. 077, ASC Center for Simulation of Dynamic Response of Materials, California Institute of Technology, Pasadena (2000).Google Scholar
  21. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, New York (1970).Google Scholar
  22. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  23. C. Sigg, R. Peikert, M. Gross: Signed distance transform using graphics hardware, in: Proceedings of IEEE Visualization (Zürich, 2003), IEEE Computer Society Press (2003) 83–90.https://doi.org/10.1109/VISUAL.2003.1250358Google Scholar

Suggested citation

J.-B. Hiriart-Urruty, Y. Lucet. “Parametric Computation of the Legendre-Fenchel Conjugate with Application to the Computation of the Moreau Envelope.” Journal of Convex Analysis 14 (2007), No. 3, 657–666. https://doi.org/10.68381/jca14039

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2007. Rights now held by Banach Press LLC.