2025/03/20 by Moritz Moeller, Moeller, Moritz, Neumayer, Sebastian +5
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #FOS: Mathematics #Neural Networks and Applications #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.2503.16209
openalex publication_date 2025/03/20 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/31
We investigate the reconstruction of multivariate functions from samples using sparse recovery techniques. For Square Root Lasso, Orthogonal Matching Pursuit, and Compressive Sampling Matching Pursuit, we demonstrate both theoretically and empirically that they allow us to recover functions from a small number of random samples. In contrast to Basis Pursuit Denoising, the deployed decoders only require a search space VJ spanned by dictionary elements indexed by J and a sparsity parameter n to guarantee an L2-approximation error decaying no worse than a best n-term approximation error and the truncation error with respect to the search space VJ and the uniform norm. We show that this happens simultaneously for all admissible functions if the number of samples scales as nlog2 nlog |J|, coming from known bounds for the RIP for matrices built upon bounded orthonormal systems. As a consequence, we obtain bounds for sampling widths in function classes. In addition, we establish lower bounds on the required sample complexity, which show that the log-factor in \vert J \vert is indeed necessary to obtain such \em instance-optimal error guarantees. Finally, we conduct several numerical experiments to show that our theoretical bounds are reasonable and compare the discussed decoders in practice.