Infinite-dimensional $\ell^1$ minimization and function approximation from pointwise data
For researchers in approximation theory and signal processing, this work offers a principled framework for ℓ1-based function approximation with theoretical guarantees, though it is incremental in extending known techniques to infinite-dimensional settings.
This paper introduces an infinite-dimensional ℓ1 minimization approach for function approximation from pointwise data, providing interpolatory approximations without a priori bounds on expansion tails. It achieves optimal approximation for smooth one-dimensional functions using weighted ℓ1 minimization with Jacobi polynomials.
We consider the problem of approximating a smooth function from finitely-many pointwise samples using $\ell^1$ minimization techniques. In the first part of this paper, we introduce an infinite-dimensional approach to this problem. Three advantages of this approach are as follows. First, it provides interpolatory approximations in the absence of noise. Second, it does not require \textit{a priori} bounds on the expansion tail in order to be implemented. In particular, the truncation strategy we introduce as part of this framework is independent of the function being approximated, provided the function has sufficient regularity. Third, it allows one to explain the key role weights play in the minimization; namely, that of regularizing the problem and removing aliasing phenomena. In the second part of this paper we present a worst-case error analysis for this approach. We provide a general recipe for analyzing this technique for arbitrary deterministic sets of points. Finally, we use this tool to show that weighted $\ell^1$ minimization with Jacobi polynomials leads to an optimal method for approximating smooth, one-dimensional functions from scattered data.