The Christoffel function: Applications, connections and extensions

Jean B. Lasserre

doi:10.3934/naco.2024011

Article Contents

2026, Volume 16: 1-18. Doi: 10.3934/naco.2024011

This volume Previous Article Next Article Moment-SOS hierarchy and exit location of stochastic processes

The Christoffel function: Applications, connections and extensions

Jean B. Lasserre

LAAS-CNRS and Toulouse School of Economics (TSE), France

This paper is handled by Jiawang Nie as guest editor.

Received: November 2023

Revised: March 2024

Early access: March 12, 2024

Published online: March 12, 2024

The author is supported by the ANR-NuSCAP 20-CE-48-0014 and ANR-19-PI3A-0004 program of the (french) national agency ANRS.

Abstract / Introduction Full Text(HTML) Figure(2) Related Papers Cited by

Abstract

We provide an introduction to the Christoffel function (CF), a well-known (and old) tool from the theory of approximation and orthogonal polynomials. We then describe how it provides a simple and easy-to-use tool to address some problems in data analysis and mining, and in approximation and interpolation of discontinuous functions. Finally we also reveal some surprising links of the CF with seemingly different disciplines, including polynomial optimization, positivity certificates, and equilibrium measures of compact sets.

Keywords:

Mathematics Subject Classification: Primary: 42C05 65D05 65D15; Secondary: 90C23 90C22.

Citation:

Full Text(HTML)

Figure 1. Left: Degree-$ 12 $ polynomial approximation of step function by $ p^*_n $ in (25) with Gibbs phenomenon and right: step function approximated by $ f_4 $ in (28). © Reprinted from [25]

Download: Full-size image PowerPoint slide

Figure 2. Two Eckhoff functions [7] approximated by $ f_{10} $ in (28). © Reprinted from [25]

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	M. Anjos and J. B. Lasserre, Handbook of Semidefinite, Conic and Polynomial Optimization, Springer, New York, 2011. doi: 10.1007/978-1-4614-0769-0_1.
[2]	M. Baran, Complex equilibrium measure and Bernstein type theorems for compact sets in ${\mathbb{R}}^n$, Proc. Amer. Math. Soc., 123 (1995), 485-494. doi: 10.2307/2160906.
[3]	E. Bedford and B. A. Taylor, The complex equilibrium measure of a symmetric convex set in ${\mathbb{R}}^n$, Trans. Amer. Math. Soc., 294 (1986), 705-717. doi: 10.2307/2000210.
[4]	S. L. Brunton and J. N. Kutz, Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control, Cambridge University Press, 2019. doi: 10.1017/9781108380690.
[5]	K. Ducharlet, L. Travé-Massuyès, J. B. Lasserre, M.-V. Le Lann and Y. Miloudi, Leveraging the Christoffel Function for Outlier Detection in Data Streams, hal-03562614, 2022.
[6]	C. F. Dunkl and Yuan Xu, Orthogonal Polynomials of Several Variables, 2$^{nd}$ edition, Cambridge University Press, Cambridge, UK, 2014. doi: 10.1017/CBO9781107786134.
[7]	K. S. Eckhoff, Accurate and efficient reconstruction of discontinuous functions from truncated series expansions, Math. Comput., 61 (1993), 745-763. doi: 10.2307/2153251.
[8]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, version 2.1., http://cvxr.com/cvx, 2014. doi: 10.1145/2700586.
[9]	D. Henrion, M. Korda and J. B. Lasserre, The Moment-SOS Hierarchy: Lectures in Probability, Statistics, Computational Geometry, Control and Nonlinear PDEs, World Scientific, Singapore, 2022.
[10]	D. Henrion and J. B. Lasserre, Graph recovery from incomplete moment information, Constr. Approx., 56 (2022), 165-187. doi: 10.1007/s00365-022-09563-8.
[11]	A. Kroó and D. S. Lubinsky, Christoffel functions and universality in the bulk for multivariate orthogonal polynomials, Canad. J. Math., 65 (2012), 600-620. doi: 10.4153/CJM-2012-016-x.
[12]	J. B. Lasserre, Optimisation globale et théorie des moments, C. R. Acad. Sci. Paris, Série I, 331 (2000), 929-934. doi: 10.1016/S0764-4442(00)01750-X.
[13]	J. B. Lasserre, Moments, Positive Polynomials and Their Applications, Imperial College Press, London, 2009.
[14]	J. B. Lasserre, Introduction to Polynomial and Semi-Algebraic Optimization, Cambridge University Press, Cambridge, UK, 2015. doi: 10.1017/CBO9781107447226.
[15]	J. B. Lasserre, The Moment-SOS hierarchy and the Christoffel-Darboux kernel, Optim. Letters, 15 (2021), 1835-1845. doi: 10.1007/s11590-021-01713-4.
[16]	J. B. Lasserre, On the Christoffel function and classification in data analysis, Comptes Rendus Mathématique, 360 (2022), 919-928. doi: 10.5802/crmath.358.
[17]	J. B. Lasserre, A disintegration of the Christoffel function, Comptes Rendus Mathématique, 360 (2022), 1071-1079. doi: 10.5802/crmath.380.
[18]	J. B. Lasserre, Pell's equation, sum-of-squares and equilibrium measures of compact sets, Comptes Rendus Mathématique, 361 (2023), 935-952. doi: 10.5802/crmath.465.
[19]	J. B. Lasserre, A modified Christoffel function and its asymptotic properties, J. Approx. Theory, 295 (2023), Article ID: 105955. doi: 10.1016/j.jat.2023.105955.
[20]	J. B. Lasserre, The Moment-SOS hierarchy: Applications and related topics, Acta Numerica, (2023), to appear.
[21]	J. B. Lasserre and E. Pauwels, Sorting out typicality via the inverse moment matrix SOS polynomial, in Advances in Neural Information Processing Systems (eds. D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon and R. Garnett), Curran Associates, Inc., (2016), 190-198.
[22]	J. B. Lasserre and E. Pauwels, The empirical Christoffel function with applications in data analysis, Adv. Comput. Math., 45 (2019), 1439-1468. doi: 10.1007/s10444-019-09673-1.
[23]	J. B. Lasserre, E. Pauwels and M. Putinar, The Christoffel-Darboux Kernel for Data Analysis, Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, Cambridge, UK, 2022. doi: 10.1017/9781108937078.
[24]	J. B. Lasserre and Yuan Xu, A generalized Pell's equation for a class of orthogonal polynomials, arXiv: 2307.10668.
[25]	S. Marx, E. Pauwels, T. Weisser, D. Henrion and J. B. Lasserre, Semi-Algebraic approximation using Christoffel-Darboux kernel, Constr. Approx., 54 (2021), 391-429. doi: 10.1007/s00365-021-09535-4.
[26]	J. Mc Laughlin, Multivariable-polynomial solutions to Pell's equation and fundamental units in real quadratic fields, Pacific J. Math., 210 (2002), 335-348. doi: 10.2140/pjm.2003.210.335.
[27]	M. Laurent, Sums of squares, moment matrices and optimization over polynomials, in Emerging Applications of Algebraic Geometry (eds. M. Putinar and S. Sullivant), Springer, New York, (2008), 157-270. doi: 10.1007/978-0-387-09686-5_7.
[28]	Y. Nesterov, Squared functional systems and optimization problems, in High Performance Optimization (eds.H. Frenk, K. Roos, T. Terlaky and Shuzong Zhang), Applied Optimization Series vol 33, Springer, Boston MA, (2000), 405-440. doi: 10.1007/978-1-4757-3216-0_17.
[29]	P. Nevai and G. Freud, Orthogonal polynomials and Christoffel functions, J. Approx. Theory, 48 (1986), 3-167. doi: 10.1016/0021-9045(86)90016-X.
[30]	R. O'Donnell, SoS is not fully automatisable, even approximately, in 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), Leibniz Intern. Proc. Informatics (LIPIcs) (ed. H. Papadimitriou), Vol. 67 (2017), Dagstuhl, Germany, 59: 1-59: 10.
[31]	E. Pauwels, M. Putinar and J. B. Lasserre, Data analysis from empirical moments and the Christoffel function, Found. Comput. Math., 21 (2021), 243-273. doi: 10.1007/s10208-020-09451-2.
[32]	M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ Math. J., 42 (1993), 969-984. doi: 10.1512/iumj.1993.42.42045.
[33]	K. Schmüdgen, The Moment Problem, Springer Cham, 2017.
[34]	B. Simon, The Christoffel-Darboux kernel, in Perspective in Partial Ddifferential Erations, Harmonic Analysis and Applications, Proc. Symp. Pure Math. 79 (2008), 295-335, American Mathematical Society, Providence, RI, 2008. doi: 10.1090/pspum/079/2500498.
[35]	H. Stahl and V. Totik, General Orthogonal Polynomials, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1992. doi: 10.1017/CBO9780511759420.
[36]	V. Totik, Universality and fine zero spacing on general sets, Ark. Mat., 47 (2009), 361-391. doi: 10.1007/s11512-008-0071-3.
[37]	W. Webb and Hi sashi Yokota, Polynomial Pell's equation, Proc. Amer. Math. Soc., 131 (2002), 993-1006. doi: 10.1090/S0002-9939-02-06934-4.