Optimal sampling for functions on general domains

This repository tackle the problem of approximating a multivariate function defined on a general domain in high-dimensions from sample points.

We solve a regression problem via weighted-least-squares. We developed a novel sampling method in general domains which leads to probably accurate and well-conditioned approximations based on Christoffel functions associated to the finite dimensional space associated the the weighted-LS.

This library shows the efficacy of our framework on irregular domains with polynomials. You can use the tools provided in this repository for your own data.

This is a repository associated with the paper:

Near-optimal sampling strategies for multivariate function on general domains by Ben Adcock and Juan M. Cardenas

published by SIMODS 2019, available at https://epubs.siam.org/doi/10.1137/19M1279459 and https://arxiv.org/abs/1908.01249.

If you have questions or comments about the code, please contact juan.cardenascardenas@colorado.edu, or ben_adcock@sfu.ca.

Code organization

Files are organized into four main directories:

src

Contains the main Matlab files used to create figures in each section

Organized in sections

utils

Contains various python functions needed across main scripts

data

Contains .mat files generated by scripts in src

Organized in sections

Filenames

These generaically take the form

fig_[sec][number]_[row]_[col]

where [sec] is the section number, [number], [number1] and [number2] are the figure numbers and [row] and [col] are the row number and column number is multi-panel figures.

Installation and Quick Start

You can install the functions and folder of the repository in a local folder. Then run opt_sam_v3.m

Citing

In case you use optimal sampling for general domains in academic papers or scientific reports, please go ahead and cite:

@article{doi:10.1137/19M1279459,
author = {Adcock, Ben and Cardenas, Juan M.},
title = {Near-Optimal Sampling Strategies for Multivariate Function Approximation on General Domains},
journal = {SIAM Journal on Mathematics of Data Science},
volume = {2},
number = {3},
pages = {607-630},
year = {2020},
doi = {https://doi.org/10.1137/19M1279459}
}

Structure

• Function: Opt_sam_v1.m

  This function sampling points in any iteration with respect the dimension and polynomial degree.

  Basic sctructure:

  • Set up: Define the parameters.
  • Generate K points under uniform measure: Generate the grid.
  • Pre-processing:
    • Under hyperbolic cross index this generate n_max and N_max (polynomial degree and number of bases).
    • Reorder index set: The first index set correspond to n_1 and the second index until n_2 and continues.
    • Generate B matrix: This matrix contain the Legendre polynomials evaluates on the grid.
    • Compute measure mu.
    • Evaluate f on the grid.
  • Compute W-LS approximation:
    • Choose M points.
    • Compute the mu related to iteration.
    • sampling M points under mu.
    • solve w-LS approximation.
    • save singular values of A and Error.

---

• Function: Opt_sam_v3.m

  This function use a sequantial sampling the dimension and polynomial degree.

  Basic sctructure:

  • Set up: Define the parameters.
  • Generate K points under uniform measure: Generate the grid.
  • Pre-processing:
    • Under hyperbolic cross index this generate n_max and N_max (polynomial degree and number of bases).
    • Reorder index set: The first index set correspond to n_1 and the second index until n_2 and continues.
    • Generate B matrix: This matrix contain the Legendre polynomials evaluates on the grid.
    • Compute measure mu.
    • Evaluate f on the grid.
  • Compute W-LS approximation:
    • Choose M points and k points.
    • sampling k points under mu_j.
    • sampling k_ad (additional) points under mu_{j-1}.
    • Re-order index.
    • solve w-LS approximation.
    • save singular values of A and Error.

---

• Functions: Newsam_Recover_Plot_r1.m and Firstsam_Recover_plot_r1.m

  This function plot the result obtained under the sequentaly sampling(Opt_sam_v3.m), and optimal sampling(Opt_sam_v1.m). Note: The _r1 it is label for the Annular domain radio 1. You can change the script save for your convenience.

  Basic sctructure:

  • Save errors: The files related from d = 2 to d = 10 are separate of d = 15, because they have different size.
  • Compute the median.
  • plot the figures.