The devil in the (de)tails: an improved recovery guarantee for sparse approximation

Ben Adcock, Simone Brugiapaglia, Avi Gupta · 2026

Read The devil in the (de)tails: an improved recovery guarantee for sparse approximation by Ben Adcock, Simone Brugiapaglia, Avi Gupta (2026) 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-2606-26459.txt.

Introduction

Ben Adcock, Simone Brugiapaglia, and Avi Gupta improve a key step in sparse approximation. Many functions are nearly sparse, meaning a few building blocks from a large dictionary describe them well. Compressed sensing recovers such functions from random point samples. First, though, the endless dictionary must be cut down to a finite list. That cut introduces a truncation error at the sample points.

Standard bounds treat that error in the worst case. They ignore the randomness of the sample points entirely. The dictionary must then stay unnecessarily large, which inflates computing cost. The authors exploit the random structure of the samples instead. Their new bound follows the faster-decaying average error rather than the worst case. Smaller truncation sets and cheaper recovery follow. Applications to two weighted function spaces show the gains in practice.

Catalog record

CREATORBen Adcock, Simone Brugiapaglia, Avi Gupta
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26459

Browse the full library · About the Tower of Babel

Full text

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

The devil in the (de)tails: an improved recovery guarantee for sparse approximation Ben Adcock, Simone Brugiapaglia, Avi Gupta Abstract Many functions exhibit approximate sparsity in their coefficients with respect to a given dictionary. In recent literature, sparse approximation in such a dictionary from i.i.d. pointwise samples, underpinned by compressed sensing, has become a powerful tool for high-dimensional function approximation. A key step in this framework is truncating the (typically countably-infinite) dictionary to a finite index set of size n n , so that compressed sensing tools can be used to approximate the function by a sparse combination of these truncated dictionary elements. This introduces a discrete L 2 L^{2} -truncation error over the sample points, which in standard approaches, is bounded by the continuous L ∞ L^{\infty} -norm. Such a deterministic, worst-case bound ignores the randomness of the sample points entirely. As a result, n n must be taken unnecessarily large to keep the truncation error under control, which directly inflates the size of the matrix involved in the sparse recovery algorithm and increases computational cost. In this paper, we show that by exploiting the i.i.d. structure of the sample points, the discrete L 2 L^{2} truncation error admits a bound that instead reflects the faster decay behaviour of the continuous L 2 L^{2} -norm truncation error and yields significantly smaller truncation sets and decreased computational cost. We demonstrate this through applications to weighted Wiener spaces and anisotropic Sobolev spaces, in each case obtaining significantly smaller truncation sets than recent works. In addition, we also present an improved bound of independent interest for sparse approximation in bounded Riesz systems, where the measurement condition exhibits a smaller (and scale-invariant) dependence on the Riesz constants than in previous works. Keywords and phrases: High-dimensional approximation, Sparse approximation, Nonlinear approximation, Compressed sensing, Random samples, Universal algorithms, Riesz bases MSC 2020: 65D15, 65Y20, 65D40, 41A25, 65T40, 41A46 1 Introduction In recent years, sparse approximation in an orthonormal basis or dictionary has been established as an effective means to approximate functions from pointwise samples. Methods involving sparse approximation have proved effective in practice for, notably, high-dimensional approximation tasks [ 44 , 45 , 4 , 2 ] . More recently, sparse approximation has also been used effectively to establish new results on sampling numbers for various function spaces [ 38 , 39 , 36 , 37 , 35 , 26 , 6 , 8 , 7 , 9 ] , including classical Sobolev spaces, dominating mixed smoothness Sobolev spaces, mixed Wiener spaces and anisotropic spaces of infinite-dimensional holomorphic functions. 1.1 Sparse approximation Let (D,\mathcal{D},\rho) be a probability space, L^{2}_{\rho}(D) be the space of square-integrable functions f:D\rightarrow\mathbb{C} and \{\phi_{i}\}_{i\in\mathbb{N}} be a Riesz basis 1 1 1 Many of the aforementioned works consider orthonormal bases. A secondary contribution of this paper is to derive guarantees in the general setting of Riesz bases—see § 1.7 for further discussion. Since any orthonormal basis is a Riesz basis with a_{\phi}=b_{\phi}=1 , all our results apply seamlessly to orthonormal bases as well. of L^{2}_{\rho}(D) with constants a_{\phi},b_{\phi}>0 , i.e., such that a_{\phi}{\|c\|}^{2}_{2}\leq{\left\|\sum_{i\in\mathbb{N}}c_{i}\phi_{i}\right\|}^{2}_{L^{2}_{\rho}}\leq b_{\phi}{\|c\|}^{2}_{2},\hskip 10.00002pt\forall c\in\ell^{2}(\mathbb{N}). (1.1) We also assume that \{\phi_{i}\}_{i\in\mathbb{N}} is bounded, with constant K_{\phi}<\infty , i.e., K_{\phi}=\sup_{i\in\mathbb{N}}{\|\phi_{i}\|}_{L^{\infty}_{\rho}}<\infty. (1.2) The basic idea of sparse approximation is to approximate an unknown function f from samples 2 2 2 Our extend readily to the noisy setting, since the SR-LASSO decoder we use (see § 2.1 ) is designed to handle samples corrupted by additive noise. Specifically, if y_{i}=f(x_{i})+\eta_{i} , i=1,\ldots,m , the corresponding error bounds acquire an additional term proportional to \|\eta\|_{2}/{\sqrt{m}} . We focus on noiseless samples ( 1.3 ) for simplicity. (x_{1},f(x_{1})),\ldots,(x_{m},f(x_{m})) (1.3) by an s -sparse function in \{\phi_{i}\}_{i\in\mathbb{N}} , i.e., f\approx\hat{f}=\hat{c}_{i_{1}}\phi_{i_{1}}+\cdots+\hat{c}_{i_{s}}\phi_{i_{s}}. (1.4) This is typically done by recasting the problem as a sparse recovery problem for the coefficients of f . One first truncates the orthonormal basis using a finite, but large n\geq m , writes f=\sum^{\infty}_{i=1}c_{i}\phi_{i} and then observes that the vector c_{[n]}=(c_{i})^{n}_{i=1} of the first n coefficients satisfies b=Ac_{[n]}+e, (1.5) where b=\frac{1}{\sqrt{m}}(f(x_{i}))^{n}_{i=1},\hskip 10.00002ptA=\frac{1}{\sqrt{m}}\left(\phi_{j}(x_{i})\right)^{m,n}_{i,j=1},\hskip 10.00002pte=\frac{1}{\sqrt{m}}(f(x_{i})-f_{n}(x_{i}))^{m}_{i=1} (1.6) and f_{n}=\sum^{n}_{i=1}c_{i}\phi_{i} is the truncated expansion of f . One then seeks a sparse approximate solution of the linear system ( 1.5 ). This can be done by, for instance, solving a convex \ell^{1} -minimization problem, using a greedy algorithm such as Orthogonal Matching Pursuit (OMP) or by various other methods. For convenience, we shall write \mathcal{R}_{s,n} for the sparse recovery procedure that takes the samples ( 1.3 ) of f and produces an approximation \hat{f}=\mathcal{R}_{s,n}(f) . The specific procedure we use in this paper is defined in § 2.1 . Now consider the error f-\hat{f} . This can be written as f-\hat{f}=\underbrace{f_{n}-\hat{f}}_{\mathrm{(a)}}+\underbrace{f-f_{n}}_{\mathrm{(b)}}. Here (a) is the sparse recovery error , i.e., the error in recovering the approximately sparse vector of coefficients c_{[n]} and (b) is the tail error , i.e., the error due to truncation. In particular, n should be chosen sufficiently large such that (b) is no larger than (a). 1.2 The devil in the (de)tail Sparse approximation is undergirded by the theory of Compressed Sensing (CS) [ 25 ] . A typical result takes the following form (for completeness, we prove this result in § 3 ). Theorem 1.1 (Standard CS bound) . Let 0<\varepsilon<1 , s\in\mathbb{N} and x_{1},\ldots,x_{m}\sim_{\mathrm{i.i.d.}}\rho , where m satisfies m\geq c\cdot\left(\frac{K^{2}_{\phi}}{a_{\phi}}\right)\cdot s\cdot\left(\log^{2}\left(2\frac{K^{2}_{\phi}}{a_{\phi}}s\right)\log(2n)+\log(1/\varepsilon)\right) (1.7) for some universal constant c>0 . Then the following holds with probability at least 1-\varepsilon . For any f\in L^{2}_{\rho}(D) that is defined everywhere, the approximation \hat{f}=\mathcal{R}_{s,n}(f) is at most 2s -sparse and satisfies, for all p\in[2,\infty] , {\|f-\hat{f}\|}_{L^{p}_{\rho}}\lesssim(b_{\phi})^{\frac{1}{p}}(K_{\phi})^{1-\frac{2}{p}}\left(\frac{\sigma_{s}(c_{[n]})_{1}}{s^{\frac{1}{p}}}+\frac{s^{\frac{1}{2}-\frac{1}{p}}}{\sqrt{a_{\phi}}}{\|f-f_{n}\|}_{L^{\infty}_{\rho}}\right). (1.8) Here and elsewhere, we write a\lesssim b to mean a\leq Cb for some universal constant C>0 , a\gtrsim b to mean b\lesssim a , and a\asymp b to mean both a\lesssim b and a\gtrsim b . When we write \lesssim_{\lambda} the implicit constant may depend on the parameter(s) \lambda . For succinctness, we do not specify how \hat{f} is computed in Theorem 1.1 , nor in our main result below. However, it is based on solving an \ell^{1} -minimization problem followed by a thresholding step to obtain a 2s -sparse approximation. See § 2.1 for the full details (note that one can obtain an s -sparse approximation subject to an additional term s^{\frac{1}{2}-\frac{1}{p}}\sigma_{s}(c_{[n]})_{2} in the error bound, as explained in Remark 2.1 ). We remark in passing that other decoders, such as OMP, Compressive Sampling Matching Pursuit (CoSaMP) or Hard Thresholding Pursuit (HTP) [ 25 ] , could readily be considered, with minimal changes. In Theorem 1.1 , the term \sigma_{s}(c)_{1} is \ell^{1} -norm best s -term approximation error of c . In general, for 1\leq p\leq\infty , we define the \ell^{p} -norm best s -term approximation error of c as \sigma_{s}(c)_{p}:=\inf\{{\|c-z\|}_{p}:\text{$z$ is $s$-sparse}\}\equiv\left(\sum_{i>s}|c_{\pi(i)}|^{p}\right)^{1/p} where \pi:\mathbb{N}\rightarrow\mathbb{N} is a bijection that gives a nonincreasing rearrangement of c=(c_{i})_{i\in\mathbb{N}} by absolute value (also, “ s -sparse” means that z has at most s nonzero entries). Notice also that {\|f-f_{n}\|}_{L^{\infty}_{\rho}}\leq\sqrt{K_{\phi}}\sum_{i>n}|c_{i}|=:\tau_{n}(c)_{1}, where we likewise define the \ell^{p} -norm n -term approximation error of c as \tau_{n}(c)_{p}=\inf\{{\|c-z\|}_{p}:\text{$z$ is nonzero in its first $n$ entries}\}\equiv\left(\sum_{i>n}|c_{i}|^{p}\right)^{1/p}. Hence, in the literature, one often encounters the following bound: {\|f-\hat{f}\|}_{L^{p}_{\rho}}\lesssim\frac{\sigma_{s}(c)_{1}}{s^{\frac{1}{p}}}+\sqrt{\frac{K_{\phi}}{a_{\phi}}}s^{\frac{1}{2}-\frac{1}{p}}\tau_{n}(c)_{1}. (1.9) This result is broad and powerful, and has found used in the majority of the aforementioned works. However, it suffers from a

Read the complete text