Poster session of the II Spanish-Brazill Meeting in Mathematics Cadiz, December 11-14, 2018
Quadrature of Quadratures:
Compressed Sampling by Caratheodory-Tchakaloff Points
F. Piazzon, A. Sommariva and M. Vianello ∗
Keywords: multivariate discrete measures, quadrature, compression, Tchakaloff theorem, Least Squares approximation Mathematics Subject Classification (2010): 41A10, 65D32, 65K05, 93E24
A discrete version of Tchakaloff theorem on the existence of positive algebraic cubature formulas (via Caratheodory theo- rem on conical vector combinations), entails that the informa- tion 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 Program- ming, we obtain compression of Algebraic Quadrature and Least Squares approximation on multivariate compact sets and manifolds.
Since the ℓ
1-norm of the weights is constant by construction, this technique differs substantially from popular compressed sensing methods based on ℓ
1-minimization.
Applications arise, for example, in Geospatial Analysis (con- struction of efficient sensor networks), Optical System Design (ray tracing on variable geometry pupil masking), Numerical PDEs (efficient quadrature formulas for polygonal/polyhedral finite elements), Polynomial Optimization (discretization of Lasserre measure-based hierarchies).
Acknowledgements
Work partially supported by the Horizon 2020 ERA-PLANET European project “GEOEssential”, by the DOR funds and the biennial project BIRD163015 of the University of Padova, and by the GNCS-INdAM. This research has been accomplished within the RITA: “Research ITalian network on Approximation”.
References
[1] CAA: “Padova-Verona Research Group on Constructive Approxima- tion and Applications”, CATCH: Research program on Caratheodory- Tchakaloff Subsampling (with online publications and preprints).
http://www.math.unipd.it/~marcov/Tchakaloff.html [2] A. Martinez, F. Piazzon, A. Sommariva and M. Vianello, Quadrature-
based Polynomial Optimization. Draft, July 2018 (see [1]).
[3] A. Sommariva and M. Vianello, Compression of multivariate discrete measures and applications. Numer. Funct. Anal. Optim. 20 (2015), 1198–
1223.
[4] A. Sommariva and M. Vianello, Nearly optimal nested sensors location for polynomial regression on complex geometries. Sampl. Theory Signal Image Process. 17 (2018), 1198–1223.
[5] Y. Sudhakar, A. Sommariva, M. Vianello and W.A. Wall, On the use of compressed polyhedral quadrature formulas in embedded interface meth- ods. SIAM J. Sci. Comput. 10 (2017), B571-B587.
[6] V. Tchakaloff, Formules de cubatures mécaniques à coefficients non né- gatifs. (French) Bull. Sci. Math. 81 (2017) (1957), 123–134.
∗
