High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality

Moritz Moeller, Sebastian Neumayer, Kateryna Pozharska, Tizian Sommerfeld, Tino Ullrich · 2025

Read High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality by Moritz Moeller, Sebastian Neumayer, Kateryna Pozharska, Tizian Sommerfeld, Tino Ullrich (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-16209.txt.

Introduction

Moritz Moeller and Sebastian Neumayer lead a team showing that three sparse recovery decoders can rebuild a whole function from a sprinkling of random samples. Their paper appeared in two thousand twenty-five. Reconstructing high-dimensional functions from few evaluations is a core sampling problem. Guarantees matter as much as algorithms.

Root-lasso, greedy pursuit, and a matching pursuit variant all earned the same style of guarantee. Their error tracks the best possible sparse approximation plus the cost of the search space. Sample counts need only grow with sparsity and mild log factors. A lower bound proves one log factor cannot be removed. That makes the guarantees instance-optimal in a precise sense. Numerical experiments found the bounds realistic in practice. Sampling widths for function classes follow as corollaries. The work unifies algorithms usually analyzed apart.

Catalog record

CREATORMoritz Moeller, Sebastian Neumayer, Kateryna Pozharska, Tizian Sommerfeld, Tino Ullrich
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE116 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-16209

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

High-dimensional sparse recovery from function samples – Decoders, guarantees and instance optimality Moritz Moeller, Sebastian Neumayer, Kateryna Pozharska, Tizian Sommerfeld, Tino Ullrich Abstract 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 V J V_{J} spanned by dictionary elements indexed by J J and a sparsity parameter n n to guarantee an L 2 L_{2} -approximation error decaying no worse than a best n n -term approximation error and the truncation error with respect to the search space V J V_{J} and the uniform norm. We show that this happens simultaneously for all admissible functions if the number of samples scales as n ​ log 2 ​ n ​ log ⁡ | J | n\log^{2}n\log|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 | J | |J| is indeed necessary to obtain such 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. 0 0 footnotetext: Keywords and phrases: multivariate approximation; best n -term approximation; uniform norm; rate of convergence; sampling recovery. 0 0 footnotetext: 2020 Mathematics subject classification: 42A10, 94A20, 41A46, 46E15, 42B35, 41A25, 41A17, 41A63 1 Introduction Many real-world applications aim to reveal correlations and dependencies in data. Mathematically, we model the quantity of interest by a function f\colon\Omega\to\mathbb{C} to which we have access only through point evaluations at sampling points \mathbf{X}=\{x^{1},\ldots,x^{m}\}\subset\Omega . Thus, we have to approximate the unknown function f from its values f(\mathbf{X})=(f(x^{1}),\ldots,f(x^{m}))^{\top}\in\mathbb{C}^{m} at the points \mathbf{X} , a process often referred to as decoding. In practice, these samples f(\mathbf{X}) are commonly perturbed by noise. Let \mathcal{B}=\{b_{j}\in C(\Omega)\colon\;j\in I\} be a countable L_{2}(\mu) -orthonormal basis of continuous functions. We aim to approximate f by (finitely many) atoms b_{j} indexed by j\in J\subset I . To recover the associated coefficients \mathbf{c}\in\mathbb{C}^{\lvert J\rvert} , we may solve the (potentially underdetermined) linear system (1.1) \mathbf{A}\mathbf{c}=\mathbf{y},\qquad\text{where}\quad\mathbf{A}=m^{-\nicefrac{{1}}{{2}}}\bigl(b_{j}\bigl(x^{k}\bigr)\bigr)_{k=1,\ldots,m,\,j\in J}\,,\quad\mathbf{y}=m^{-\nicefrac{{1}}{{2}}}\bigl(f\bigl(x^{k}\bigr)\bigr)_{k=1,\ldots,m}. Here, we implicitly assume that the index set J is equipped with an enumeration. Below, we refer to a (non-linear) solution operator T_{\mathbf{X}} for ( 1.1 ) with f(\mathbf{X})\mapsto\sum_{j\in J}c_{j}b_{j} as decoder. The recovery turns out to be particularly easy if f can be well-represented by only a few atoms from the orthonormal basis \mathcal{B} . In this case, we can deploy the non-linear decoders Square Root Lasso ( rLasso ) [ 8 ] , as well as Orthogonal Matching Pursuit ( OMP ) [ 34 ] and the related Compressive Sampling Matching Pursuit ( CoSaMP ) [ 41 ] . The greedy decoders OMP and CoSaMP utilize an iterative atom selection process to exploit the intrinsic sparsity of the target function f . Both algorithms require only the search spaces V_{J}=\mathrm{span}(b_{j}\colon\;j\in J) and a sparsity parameter n as “parameters” to produce an output vector with \mathcal{O}(n) nonzero entries. Following a different strategy, rLasso recovers (approximate) coefficients \mathbf{c} by solving the convex optimization program (1.2) \argmin_{\mathbf{c}\in\mathbb{C}^{\lvert J\rvert}}\bigl\{\lVert\mathbf{c}\rVert_{\ell_{1}}+\lambda\lVert\mathbf{Ac-\mathbf{y}}\rVert_{\ell_{2}}\bigr\}, which is noise-blind: the regularization parameter \lambda>0 is a function of n , independent of potential noise. A natural question is whether we can control the approximation error \lVert f-T_{\mathbf{X}}(f)\rVert_{V} with respect to a norm \lVert\cdot\rVert_{V} . In general, this quantity depends on the chosen search spaces V_{J} and the sampling points \mathbf{X} . For the proposed non-linear decoders, the role of V_{J} turns out to be not as crucial as for (weighted) least-squares decoders [ 14 , 31 , 18 ] , for which one has to know the optimal subspace V_{J} for the considered approximation, see also Remark 5.2 . Throughout, we consider independent and identically distributed (iid) points \mathbf{X} sampled from the orthogonality measure \mu . Contribution First, we investigate the conditions, in particular the required sample size m=\lvert\mathbf{X}\rvert , for the deployed decoders T_{\mathbf{X}} to achieve an approximation error comparable to the truncation error \lVert f-P_{J}f\rVert_{L_{\infty}} , where P_{J}f denotes the L_{2}(\mu) -orthogonal projection P_{J}f=\sum_{j\in J}\langle f,b_{j}\rangle b_{j} . Our sparse recovery result in Theorem 2.9 for rLasso and OMP involves the best n -term approximation error (1.3) \sigma_{n}(f)_{V}\coloneqq\sigma_{n}(f;\mathcal{B})_{V}\coloneqq\inf\limits_{\begin{subarray}{c}J\subset I\\ \lvert J\rvert\leq n\end{subarray}}\,\inf\limits_{\begin{subarray}{c}c_{j}\in\mathbb{C}\\ j\in J\end{subarray}}\,\Bigl\lVert f-\sum\limits_{j\in J}c_{j}b_{j}\Bigr\rVert_{V} with respect to the Wiener space V=\mathcal{A}_{1} . The norm of this space is the sum over absolute values of the Fourier coefficients, defined in ( 2.15 ). This establishes for any 2\leq q\leq\infty the universal bound (1.4) \lVert f-T_{\mathbf{X}}(f)\rVert_{L_{q}(\mu)}\leq C_{\mathcal{B}}n^{\nicefrac{{1}}{{2}}-\nicefrac{{1}}{{q}}}\bigl(n^{-\nicefrac{{1}}{{2}}}\sigma_{n}(f;\mathcal{B})_{\mathcal{A}_{1}}+\lVert f-P_{J}f\rVert_{L_{\infty}}\bigr), which holds with high probability for all f\in\mathcal{A}_{1} provided that the number of samples m scales as (1.5) m\gtrsim n\log^{2}n\log\lvert J\rvert. The sample complexity bound ( 1.5 ) relies on recent improved bounds for RIP matrices based on bounded orthonormal systems, see [ 24 ] , [ 2 ] . Note that the dependence of the bound ( 1.4 ) on the best n -term approximation error of f relates to instance optimality , a term introduced by Cohen, Dahmen and DeVore in [ 13 ] . We extend Theorem 2.9 to CoSaMP in Theorem 5.1 , and moreover we discuss the case of unbounded systems in Section 2.3 . Building upon techniques from combinatorics [ 20 , 21 ] , we also establish a lower bound on the number of required sampling points for any decoder, see Theorem 3.6 : If ( 1.4 ) is to hold for all f\in\mathcal{A}_{1} , then we must have (1.6) m\gtrsim n\log(\lvert J\rvert/4n). Consequently, the \log\lvert J\rvert -factor in ( 1.5 ) cannot be avoided. Finally, we present variants of our results for trigonometric approximation in Section 4 , highlighting their implications for sampling complexity in function spaces. To illustrate our theoretical observations, we conduct large-scale recovery experiments, for which we focus on the widely used Fourier and Chebyshev systems as \mathcal{B} . While Legendre polynomials are theoretically admissible by the results of Section 2.3 , their efficient numerical implementation turned out infeasible. To control the size of the search space V_{J} , we rely on hyperbolic crosses [ 15 ] . For OMP , we solve the least-squares problem via an iterative update of the Cholesky decomposition [ 47 ] , while we use the iterative least-squares solver LSQR for CoSaMP . To solve the rLasso optimization program ( 1.2 ), we employ a restarted primal-dual algorithm based on [ 3 ] . Although the theoretical approximation bounds coincide, our numerical experiments show that rLasso and CoSaMP are preferable when the number of coefficients required for a given approximation accuracy is large. This is unsurprising, since each OMP update adds only a single support point at the cost of solving a linear system. On the other hand, our experiments show that both OMP and CoSaMP are superior to rLasso for highly sparse solutions, i.e., if we have to perform only few iterations. Another interesting observation is that we frequently outperform the theoretically guaranteed asymptotic

Read the complete text