Randomized weakly admissible meshes

2021/01/11 by Yiming Xu, Xu, Yiming, Akil Narayan +1 · 2 citations
Mathematics · #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Geometry and complex manifolds #Numerical Analysis (math.NA) #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2101.04043

openalex publication_date 2021/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A weakly admissible mesh (WAM) on a continuum real-valued domain is a sequence of discrete grids such that the discrete maximum norm of polynomials on the grid is comparable to the supremum norm of polynomials on the domain. The asymptotic rate of growth of the grid sizes and of the comparability constants must grow in a controlled manner. In this paper, we generalize the notion of a WAM to a hierarchical subspaces of not necessarily polynomial functions, and we analyze particular strategies for random sampling as a technique for generating WAM's. Our main results show that WAM's and their stronger variant, admissible meshes (AM's), can be generated by random sampling, and our analysis provides concrete estimates for growth of both the meshes and the discrete-continuum comparability constants.

Cited by

• Hybrid least squares for learning functions from highly noisy data
• Sparse grids vs. random points for high-dimensional polynomial approximation

Related

• Meshes that trap random subspaces
• Random Sampling in Computational Algebra: Helly Numbers and Violator\n Spaces
• Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
• Randomized subspace iteration: Analysis of canonical angles and\n unitarily invariant norms
• Stability of Least Squares Approximation under Random Sampling