Polynomial argmin for recovery and approximation of multivariate discontinuous functions

arXiv2302.06945MaRDI QIDQ6426412FDOQ6426412

Authors: Didier Henrion, Milan Korda, J. B. Lasserre 

Publication date: 14 February 2023

Abstract: We propose to approximate a (possibly discontinuous) multivariate function f (x) on a compact set by the partial minimizer arg miny p(x, y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when f is a piecewise polynomial) we prove that the approximation is exact with a low-degree polynomial p. Our approach has three distinguishing features: (i) It is mesh-free and does not require the knowledge of the discontinuity locations. (ii) It is model-free in the sense that we only assume that the function to be approximated is available through samples (point evaluations). (iii) The size of the semidefinite program is independent of the ambient dimension and depends linearly on the number of samples. We also analyze the sample complexity of the approach, proving a generalization error bound in a probabilistic setting. This allows for a comparison with machine learning approaches.

This page was built for publication: Polynomial argmin for recovery and approximation of multivariate discontinuous functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426412)