High-Dimensional Approximation, Sparse Grids, and UQ¶

Job: develop the curse of dimensionality / sparse grids (Smolyak), the QMC / discrepancy (Koksma–Hlawka), the UQ / polynomial chaos (gPC), and the deep / ML — with the sparse grids / QMC as the worked example.

Core¶

The curse of dimensionality and the approximation¶

Curse / $\varepsilon^{-d/s}$ / sparse / Smolyak	Description
Curse of dimensionality	the $\varepsilon^{-d/s}$ the complexity (the $d$ the dimension, the $s$ the smoothness)
Sparse grids (Smolyak)	the $\varepsilon^{-1/s}(\log 1/\varepsilon)^{d-1}$ the sparse (the mixed smoothness)

The quasi-Monte Carlo and the discrepancy¶

QMC / discrepancy / Sobol / Koksma–Hlawka	Description
QMC	the low-discrepancy (the Sobol / the Halton, the $\varepsilon^{-1}$ the QMC)
Koksma–Hlawka	$

The UQ and the polynomial chaos¶

UQ / gPC / orthogonal / probability	Description
UQ	the uncertainty, the stochastic (the probability)
Polynomial chaos (gPC)	the orthogonal polynomials (the probability)

The high-dimensional and the ML / the deep¶

Deep / ML / curse	Description
Deep	the neural network the high-dim (the ML mathematics)
Curse / ML	the ML mathematics the deep the breaking the curse

See it¶

Sparse grids (Smolyak) for the high-dimensional integration and the QMC / Koksma–Hlawka. The sparse: the $d$-dim the Smolyak the $\varepsilon^{-1/s}(\log 1/\varepsilon)^{d-1}$ (the sparse grids the Smolyak, the $s$ the mixed smoothness, the Fourier analysis). The QMC: the $|I-I_N|\le V_{\mathrm{HK}}(f)D_N$ (the Koksma–Hlawka, the $D_N$ the discrepancy, the Sobol / Halton the low-discrepancy, the measure theory). The key point: the sparse grids the Smolyak the $d$-dim, the QMC the Koksma–Hlawka the discrepancy — the high-dimensional the approximation / the integration.

Check¶

Show that the Smolyak sparse grid breaks the curse for the mixed smoothness, and explain the QMC / Koksma–Hlawka.

The curse: the full grid the $\varepsilon^{-d/s}$ (the $d$ the dimension, the $s$ the smoothness, the exponential in $d$). The Smolyak: the sparse grid the $\varepsilon^{-1/s}(\log 1/\varepsilon)^{d-1}$ (the mixed smoothness the $H^s_{\mathrm{mix}}$, the Smolyak the tensor the sparse, the $d$ the logarithmic). The QMC: the $|I-I_N|\le V_{\mathrm{HK}}(f)D_N$ (the Koksma–Hlawka, the $V_{\mathrm{HK}}$ the Hardy–Krause variation, the $D_N$ the star discrepancy, the Sobol / Halton the low-discrepancy the $D_N=O((\log N)^d/N)$, the measure theory). So the Smolyak the mixed smoothness, the QMC the discrepancy.

Explain the polynomial chaos (gPC) and the UQ.

The UQ: the $u(x,\xi)$ the $\xi$ the random (the probability), the $u\approx\sum u_k(x)\phi_k(\xi)$ (the gPC, the $\phi_k$ the orthogonal polynomials w.r.t. the distribution of $\xi$). The Hermite: the $\xi$ Gaussian, the $\phi_k$ the Hermite (the probability). The Legendre: the $\xi$ uniform, the $\phi_k$ the Legendre. The Galerkin: the $u_k$ the Galerkin (the stochastic Galerkin, the UQ). So the gPC the orthogonal, the UQ the stochastic.

Pitfalls¶

The curse the $\varepsilon^{-d/s}$ (the $d$ the dimension, the exponential) — the curse the full grid, the sparse the logarithmic.
The Smolyak the mixed smoothness (the $H^s_{\mathrm{mix}}$, the $\varepsilon^{-1/s}(\log)^{d-1}$) — the Smolyak the mixed, the non-mixed the curse.
The QMC the Koksma–Hlawka (the $V_{\mathrm{HK}}D_N$, the measure theory) — the QMC the discrepancy, the $D_N$ the low-discrepancy.
The gPC the orthogonal (the Hermite / Legendre, the probability) — the gPC the UQ, the stochastic Galerkin.

Refs¶

Smolyak, "Quadrature and interpolation formulas" (1963); the sparse grids
Novak–Ritter, "High-dimensional integration" (1996); the curse / the sparse
Dick–Pillichshammer, Digital Nets and Sequences (2010); the QMC / discrepancy
Xiu–Karniadakis, "The Wiener–Askey polynomial chaos" (2002); the gPC / UQ

Next¶

NA index · Foundations · FEM & Variational · Geometric Integration · Iterative & Multigrid · Measure theory · Probability · ML mathematics