Session III.5 - Information-Based Complexity
Poster
Efficient recovery of non-periodic functions via samples
Nicolas Nagel
TU Chemnitz, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We combine periodization and subsampling techniques to obtain an efficent reconstruction algorithm for multivariate, non-periodic functions $f: [-1, 1]^d \rightarrow \mathbb{C}$ using samples. Firstly, transforming $f$ to a periodic function $Tf: \mathbb{T}^d \rightarrow \mathbb{C}$ via a cosine composition allows us to use well-known and optimal algorithms for the periodic case and pull them back to the non-periodic one. This leads to approximating $f$ via Chebyshev polynomials using function values on Chebyshev distributed sample points. Secondly, we reduce the sampling budget via frame subsampling from $O(m \log m)$ to $O(m)$ sample points ($m$ the number of used basis functions, derived from a hyperbolic cross) while still keeping good approximation properties. This set of sample points will be used for the whole function class and needs to be calculated only once. In total, we obtain an implementable algorithm to approximate $s$-smooth, non-periodic functions $f: [-1, 1]^d \rightarrow \mathbb{C}$ via $n$ samples with $L_2$-error of near-optimal order $n^{-s} (\log n)^{(d-1)s+1/2}$. We also apply this algorithm to a test function constructed from a quadratic B-spline of smoothness $s=5/2$ and observe the predicted decay rate. With this work we aim to give a theoretical connection between the approximation of periodic and non-periodic functions without loss in the main decay rate, as well as demonstrate the versitility of subsampling.
Joint work with Felix Bartel (TU Chemnitz), Kai Lüttgen (TU Chemnitz) and Tino Ullrich (TU Chemnitz).