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 near-optimal regression designs (geospatial analysis), in optical system design (ray tracing method), and in numerical cubature on polygonal/polyhedral & curved elements for the discretization of PDEs.

Posters

Software

Project

Papers

  1. TetraFreeQ: tetrahedra-free quadrature on polyhedral elements
    draft - A. Sommariva and M. Vianello
  2. Low-cardinality Positive Interior cubature on NURBS-shaped domains
    draft - A. Sommariva and M. Vianello
    BIT Numer. Math., accepted upon revision
  3. Cubature rules with positive weights on union of disks
    preprint - A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA, to appear
  4. Numerical hyperinterpolation over spherical triangles
    preprint - A. Sommariva and M. Vianello
    Math. Comput. Simul. 190 (2021), 15--22
  5. Near-algebraic Tchakaloff-like quadrature on spherical triangles
    preprint - A. Sommariva and M. Vianello
    Appl. Math. Lett. 120 (2021)
  6. Computing Tchakaloff-like cubature rules on spline curvilinear polygons
    preprint - A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA 14 (2021), 1--11
  7. dCATCH: a numerical package for d-variate near G-optimal Tchakaloff regression via fast NNLS
    preprint - M. Dessole, F. Marcuzzi and M. Vianello
    MDPI-Mathematics 8(7) (2020), Special Issue "Numerical Methods"
  8. Quadrature-based polynomial optimization
    preprint - A. Martinez, F. Piazzon, A. Sommariva and M. Vianello
    Optim. Lett. 14 (2020), 1027--1036
  9. Accelerating the Lawson-Hanson NNLS solver for large-scale Tchakaloff regression designs
    preprint - M. Dessole, F. Marcuzzi and M. Vianello
    Dolomites Res. Notes Approx. DRNA 13 (2020), 20--29
  10. Compressed cubature over polygons with applications to optical design
    preprint - B. Bauman (LLNL, USA), A. Sommariva and M. Vianello
    J. Comput. Appl. Math. 370 (2020)
  11. Algebraic cubature on polygonal elements with a circular edge
    preprint - E. Artioli, A. Sommariva and M. Vianello
    Comput. Math. Appl. 79 (2020), 2057--2066
  12. Near G-optimal Tchakaloff designs
    preprint - L. Bos, F. Piazzon and M. Vianello
    Comput. Statistics 35 (2020), 803--819
  13. CaTchDes: Matlab codes for Caratheodory-Tchakaloff Near-Optimal Regression Designs
    Len Bos and M. Vianello
    SoftwareX 10 (2019)
  14. Near optimal polynomial regression on polynomial meshes
    preprint - L. Bos, F. Piazzon and M. Vianello
    Sampling Theory and Applications 2019, IEEE Xplore Digital Library, DOI: 10.1109/SampTA45681.2019.9030910
  15. Tchakaloff polynomial meshes
    preprint - L. Bos and M. Vianello
    Ann. Polon. Math. 122 (2019), 221--231
  16. Near optimal Tchakaloff meshes for compact sets with Markov exponent 2
    preprint - M. Vianello
    Dolomites Res. Notes Approx. DRNA 11 (2018), 92--96 (Special Issue on Norm Levenberg's 60th birthday)
  17. Nearly optimal nested sensors location for polynomial regression on complex geometries
    preprint - A. Sommariva and M. Vianello
    Sampl. Theory Signal Image Process. 17 (2018), 95--101
  18. Caratheodory-Tchakaloff Least Squares
    preprint - F. Piazzon, A. Sommariva and M. Vianello
    Sampling Theory and Applications 2017, IEEE Xplore Digital Library, DOI: 10.1109/SAMPTA.2017.8024337
  19. 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
  20. Optimal polynomial meshes and Caratheodory-Tchakaloff submeshes on the sphere
    preprint - P. Leopardi, A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA 10 (2017), 18--24
  21. Caratheodory-Tchakaloff Subsampling
    F. Piazzon, A. Sommariva and M. Vianello
    Dolomites Res. Notes Approx. DRNA 10 (2017), 5--14
  22. 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
  23. Compressed sampling inequalities by Tchakaloff's theorem
    preprint - M. Vianello
    Math. Inequal. Appl. 19 (2016), 395--400
  24. 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
  25. Compression of multivariate discrete measures and applications
    preprint - A. Sommariva and M. Vianello
    Numer. Funct. Anal. Optim. 36 (2015), 1198--1223