Back to "Padova-Verona research group on Constructive Approximation and Applications" (CAA) Home Page

CATCH: Caratheodory-Tchakaloff Subsampling

A discrete version of Tchakaloff theorem on the existence of positive algebraic cubature formulas, that can be proved by the well-known Caratheodory theorem on conical combinations of finite-dimensional vectors, entails that the information required for multivariate polynomial approximation can be suitably compressed. The framework here is approximating a discrete measure by another one, with the same polynomial moments up to a certain degree, and a (much) smaller support.

Extracting such "Caratheodory-Tchakaloff points" from the support of discrete measures by Linear or Quadratic Programming, we obtain compression of algebraic quadrature, QMC integration, Least Squares approximation and polynomial meshes on multivariate compact sets and manifolds.

Applications arise, for example, in the construction of efficient sensor networks (geospatial analysis), in optical system design (ray tracing method), and in the optimization of 3D discretization methods for CFD simulations.




  1. Lune-based quadrature on vignetted annular pupils with application to the LSST camera
    in preparation, with B. Bauman (LLNL, USA) and A. Sommariva
  2. Nearly optimal nested sensors location for polynomial regression on complex geometries
    draft - A. Sommariva and M. Vianello
  3. Caratheodory-Tchakaloff Least Squares
    preprint - F. Piazzon, A. Sommariva and M. Vianello
    2017 International Conference on Sampling Theory and Applications (SampTA), IEEE Xplore Digital Library, DOI: 10.1109/SAMPTA.2017.8024337
  4. On the use of compressed polyhedral quadrature formulas in embedded interface methods
    preprint - Y. Sudhakar, A. Sommariva, M. Vianello and W.A. Wall
    SIAM J. Sci. Comput. 39 (2017), B571-B587
  5. Optimal polynomial meshes and Caratheodory-Tchakaloff submeshes on the sphere
    P. Leopardi, A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA 10 (2017), 18--24
  6. Caratheodory-Tchakaloff Subsampling
    F. Piazzon, A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA 10 (2017), 5--14
  7. A new quasi-Monte Carlo technique based on nonnegative least-squares and approximate Fekete points
    preprint - L. Bittante, S. De Marchi and G. Elefante
    Numer. Math. Theory Methods Appl. 9 (2016), 609--632
  8. Compressed sampling inequalities by Tchakaloff's theorem
    preprint - M. Vianello
    Math. Inequal. Appl. 19 (2016), 395--400
  9. Polynomial Meshes: Computation and Approximation
    preprint - S. De Marchi, F. Piazzon, A. Sommariva and M. Vianello
    Proceedings of CMMSE 2015, 414--425, ISBN 978-84-617-2230-3, ISSN 2312-0177
  10. Compression of multivariate discrete measures and applications
    preprint - A. Sommariva and M. Vianello
    Numer. Funct. Anal. Optim. 36 (2015), 1198--1223