REVIEW 3 major objections 5 minor 19 references
Estimation of sparse polynomial approximation error to continuous function
T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read For every continuous function, the error of an l1-minimized sparse polynomial approximation is bounded by the best s-term coefficient error plus the best-approximation tail; sparse polynomials are recovered exactly.
desk verdict The theorems are correct and clean applications of Rauhut–Ward with the best-approximation remainder as noise, but the weighted numerical experiments violate the hypotheses and should not be cited as validation. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing identity is $f(x_l)=p_{\mathrm{opt}}(x_l)+\eta_l$ with $|\eta_l|\le E_N$: samples of the function are noisy samples of its best degree-N polynomial. This turns the problem into $y=Ac_{\mathrm{opt}}+\eta$, so the recovery theorem cited as [10] controls $\|c^\#-c_{\mathrm{opt}}\|_1$. Uniform boundedness $\|\psi_k\|_\infty\le K$ converts coefficient error into $L^\infty$ function error, while orthonormality converts it into $L^2$ error in the L2 theorems. The quasi-norm estimate $\sigma_s(c_{\mathrm{opt}})_1\le s^{1-1/q}\|c_{\mathrm{opt}}\|_q$, cited as [18], carries the sparsity term; the cited smoothness theorem [17] supplies the rates used to turn $E_N$ into explicit powers of $N$.
What would settle it
Run many independent trials under the hypotheses of Theorem 3.1 with a known s-sparse polynomial $f$ (so $E_N=0$ and $\sigma_s(c_{\mathrm{opt}})_1=0$), using $m$ satisfying the sampling bound and $\Theta=1$; the theorem predicts exact recovery except for the stated failure probability, so any systematic non-recovery would disprove it. More generally, choose any $f$ with exactly computed $E_N$, solve (3.2), and check whether $\|f-p^\#\|_\infty$ exceeds the right side of (3.3) more often than the theorem's failure probability allows.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that sparse $\ell^1$-minimization approximates a continuous function with an error that splits into two additive parts: the best s-term truncation error of the coefficient vector of the best polynomial approximation, and the best polynomial approximation error $E_N$ itself. In the unweighted $L^\infty$ case, the claimed bound is $\|f-p^\#\|_\infty \le K D_1 \sigma_s(c_{\mathrm{opt}})_1 + (K D_2 \Theta \sqrt{s}+1)E_N$, and the Stechkin-type estimate gives the alternative form $K D_1 \|p_{\mathrm{opt}}\|_{A_q} s^{1-1/q} + (K D_2 \Theta \sqrt{s}+1)E_N$. The weighted L2 versions replace $E_N$ by $\|T_N\|_\infty$, use the weight-adjusted error $\sigma_s(c_{\mathrm{opt}})_{\omega,1}/\sqrt{s}$, and do not require the orthonormal system to be uniformly bounded. The paper's own reading is that the recovered polynomial is essentially as good as the best s-term truncation of the best degree-N polynomial, plus the unavoidable tail error.
Load-bearing premise
The proof depends on the random sampling matrix satisfying the recovery condition behind the cited theorems: enough samples for the chosen sparsity (roughly $m$ proportional to $s\log^3(s)\log(N+1)$, with an extra $K^2$ factor unweighted), and on $E_N$ or $\|T_N\|_\infty$ being known well enough to set the noise constraint in the $\ell^1$ problem.
Editorial extensions
If this is right
- If $f$ is exactly s-sparse in the chosen basis, then $E_N=\sigma_s(c_{\mathrm{opt}})_1=0$, so the recovered polynomial equals $f$ with the theorem's stated probability.
- For Lipschitz or differentiable functions, combining the main bound with the cited smoothness theorem gives error of order $s^{1-1/q}$ plus $\sqrt{s}\,N^{-\alpha}$ or $\sqrt{s}\,N^{-p}$, and balancing the terms fixes the required degree $N$ as a power of $s$.
- Smoother functions need smaller $N$ for the same accuracy: the paper makes this explicit by choosing $N=\lceil s^{(1/q-1/2)/\alpha}\rceil$ in the Lipschitz case and analogous powers for bounded derivatives.
- The weighted L2 theorems remove the uniform-boundedness requirement, so the same error decomposition applies to orthonormal systems whose sup-norms grow, provided weights satisfy $\omega_j\ge\|\psi_j\|_\infty$ and $s\ge2\|\omega\|_\infty^2$.
- The noise constraint is set by $E_N$ or $\|T_N\|_\infty$ alone, so the method replaces tail-norm estimation by best-approximation error estimation.
Reading between the lines
- Because the proof uses only uniform boundedness of the basis plus a recovery theorem, the same error splitting should transfer to any uniformly bounded orthonormal basis, not just polynomials, whenever a computable best-approximation error exists.
- The numerical finding that large $\Theta$ (up to $10^5$) improves accuracy is consistent with $E_N$ being at machine precision in the tested examples; where $E_N$ is not tiny, the $\Theta\sqrt{s}\,E_N$ term will dominate and $\Theta\approx1$ is the safer choice.
- The obstacle to a multivariate version is not the recovery theory but the absence of an operational algorithm for the multivariate best uniform approximation error, so a practical extension would need a computable upper bound to play the role of $E_N$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a framework for estimating the approximation error of sparse polynomial approximations obtained by l1-minimization. For a continuous function f, its sampled values are viewed as noisy samples of the best approximation polynomial in an N-dimensional polynomial space, with the remainder term treated as noise. Theorems 3.1 and 4.1 give L-infinity and L2 error bounds for the unweighted l1-minimization approach, while Theorems 4.2 and 4.3 give L2 bounds for the weighted l1-minimization approach, all in terms of best s-term approximation errors, best approximation errors, sparsity, and polynomial quasi-norms. The paper also derives corollaries using Jackson's theorem and presents numerical experiments in Section 5.
Significance. If the theorems are correct, the paper provides a principled alternative to cross-validation for choosing the noise bound in sparse polynomial recovery: the bound is expressed in terms of the best uniform (or square) approximation error, which can be estimated by classical approximation algorithms in the univariate case. The proofs are direct but clean applications of the Rauhut-Ward recovery theorems and Stechkin's inequality, and the exact-recovery statement for sparse polynomials is a useful observation. The theoretical results are likely correct. However, the significance is diminished by two factors: (i) the numerical experiments in Section 5 fall outside the hypotheses of the theorems they claim to validate, and (ii) the method relies on a priori knowledge or computation of E_N or ||T_N||_infinity, which the paper admits is unavailable for multivariate functions. The theoretical contribution is still meaningful as an error estimate, but the empirical validation and the claims of practical efficacy are not supported by the reported experiments.
major comments (3)
- [Section 5.2, Tables 1-3] The weighted l1-minimization experiments use weights ω1_i = sqrt(i) and ω2_i = (i+1)/2 for i = 1,...,N+1, with N = 599 or 799 and m = 300 or 400. Theorems 4.2 and 4.3 inherit from Theorem 2.4 the requirement that s ≥ 2||ω||_infinity^2. For ω1 with N=599, ||ω||_infinity = sqrt(600), so s ≥ 1200, and the sample-size condition m ≥ C s log^3(s) log(N+1) then forces m to be on the order of 10^6 or larger. For ω2, the required s is even larger. No value of s can satisfy both conditions at m = 300-400. Therefore Tables 1-3 do not validate Theorems 4.2 and 4.3; the experiments operate in a regime where the theorems do not apply. The authors should either rerun the weighted experiments with weights that satisfy the theorem hypotheses (e.g., ω_j = ||ψ_j||_infinity = sqrt(2) for the normalized Chebyshev system) and report the sparsity s used, or explicitly state that the numerical results are heuristic and outside the scope of the theorems.
- [Section 5.1, Figures 1-4] The unweighted experiments in Section 5.1 do not report the sparsity parameter s used in the l1-minimization problems, even though Theorems 3.1 and 4.1 require m ≥ C K^2 s log^3(s) log(N+1). For N = 999 and m = 400 with K = sqrt(2), typical values of s would require m far larger than 400 to satisfy the hypothesis; without reporting s, the reader cannot verify whether the experiments fall within the theorem's scope. The paper should report s for each experiment and either verify the sample-size condition or qualify the numerical results as illustrative rather than as a validation of the theorems.
- [Section 6, Summary] The paper acknowledges that there is no operational algorithm to compute the best uniform approximation error E_N for multivariate functions, which is a core ingredient in the optimization constraints (3.2) and (4.10). This limitation is honestly stated, but it means the claimed extension to multivariate settings is not currently constructive. Since the constraint set of the l1-minimization problems depends on E_N, the error estimates are not fully a posteriori in the multivariate case. The authors should make this limitation more prominent in the introduction or conclusion, so that readers do not over-interpret the practical scope of the method.
minor comments (5)
- [Throughout] The parameter Θ is described as a positive integer, but the proofs only require Θ ≥ 1; the results hold for any real Θ > 0, so the wording could be relaxed.
- [Theorem 2.3 and Theorem 2.4] The probability bounds are stated as '1 − N^{−γlog3(s)}' and '1 − N^{−log3(3s)}'; it would be clearer to write the exponents as −γ log^3(s) and −log^3(3s) to avoid ambiguity with the notation log3.
- [Section 5.1, Figure 1] The text states that Θ = 10^5 achieves the smallest average relative errors, but for f = cos(36√2 x + 1/3) the difference between Θ = 10^5 and Θ = 10^7 appears small in the figure; a quantitative table would be more informative.
- [Remark 4.2] The comment that 'σ_s(c_opt)_{ω,1}/√s is not significant when s is large' is imprecise: σ_s generally decreases with s, but the division by √s also matters; rewording to 'tends to be small for compressible coefficient vectors' would be more accurate.
- [References] Reference [17] cites Natanson's book but no edition or year is given in the text; the full bibliographic details should be completed.
Circularity Check
No significant circularity: the main theorems apply external Rauhut-Ward recovery results and Jackson/Stechkin bounds to the residual representation, and the numerical Theta-tuning does not enter the proofs.
full rationale
The derivation chain is self-contained with respect to external results. The main theorems treat f(x_l) = p_opt(x_l) + eta_l, with eta bounded by EN or ||T_N||\infty, which is a representation of the residual, not an assumption of the desired error bound. The recovery bounds come from Rauhut-Ward (Theorems 2.3 and 2.4), and the estimates for the approximation terms come from Jackson and Stechkin; none of these are fitted or defined in terms of p#. The multiplier Theta is a hypothesis of the optimization problem; choosing a favorable Theta in Section 5 is a numerical demonstration issue and is not part of the proof. The self-citations [14,15] appear only as background and are not load-bearing. The admitted lack of a multivariate EN algorithm (Section 6) and the apparent violation of the weighted-theorem hypotheses in Tables 1-3 are correctness or scope concerns, not circularity.
Assumptions & free parameters
free parameters (2)
- Theta (noise bound multiplier) =
10^5 in experiments; values 1 to 10^11 tested
- s (sparsity budget) =
not reported in experiments
assumptions (5)
- domain assumption Rauhut-Ward recovery guarantees (Theorems 2.3 and 2.4 from [10,11]) hold for the random sampling matrix A
- standard math A best uniform approximation polynomial p_opt attaining E_N exists in Pi_N = span{psi_0,...,psi_N} for every continuous f
- standard math Jackson's theorem and its corollaries (Theorems 2.1 and 2.2) bound E_N in terms of smoothness
- domain assumption For the weighted theorems, the weight vector must satisfy omega_j >= ||psi_j||_infinity and s >= 2||omega||^2_infinity
- standard math In Theorem 4.1, ||p_opt||_{A_q} <= ||f||_{A_q}, i.e., p_opt's coefficients are the first N+1 Fourier coefficients of f
Cite this review
Pith. "Pith review of Estimation of sparse polynomial approximation error to continuous function." pith.science (2026). https://pith.science/paper/EOT7LX6R
@misc{pith2026250606880,
author = {Pith},
title = {Pith review of: Estimation of sparse polynomial approximation error to continuous function},
year = {2026},
howpublished = {\url{https://pith.science/paper/EOT7LX6R}},
note = {Machine review of arXiv:2506.06880}
}
read the original abstract
The sparse polynomial approximation of continuous functions has emerged as a prominent area of interest in function approximation theory in recent years. A key challenge within this domain is the accurate estimation of approximation errors. This paper focuses on continuous functions, characterizing their sampled values as a combination of the values of their best approximation polynomials within a finite-dimensional polynomial space and the associated remainder terms. Consequently, the sampled values of a function can be interpreted as noisy samples of the values of its best approximation polynomial, with the noise equivalent to the remainder term's values at those points. By selecting a uniformly bounded orthonormal polynomial system as the basis for this finite-dimensional space, it becomes feasible to formulate noise constraint inequalities and l1-minimization problems or their weighted l1-minimization variants. This paper provides estimations for the approximation error of the sparse polynomial derived from the l1-minimization method, characterizing the error in terms of the quasi-norm of the sampled function or its best uniform approximation polynomial, the sparsity, and the best approximation error. The analysis reveals that if the sampled function is a sparse polynomial from a finite-dimensional space, it can be reconstructed exactly. Moreover, it is observed that the smoother the sampled function, the fewer degrees of the sparse polynomial are required to attain a given approximation accuracy. The paper also extends this analysis to estimate the L2-norm approximation error for the sparse polynomial obtained via the weighted l1-minimization method, noting that in this context, the orthonormal polynomial system does not need to be uniformly bounded for the conclusions to hold.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
B. Adcock. Infinite-dimensional l1-minimization and function approximation from point- wise data, Constr. Approx., 45(3): 345–390, 2017
work page 2017
-
[2]
E. J. Cand `es, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruc- tion from highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489- 509, 2006
work page 2006
-
[3]
D. L. Donoho. Compressed sensing. IEEE Trans. Inform. Theory, 52(4):1289-1306, 2006
work page 2006
-
[4]
A. Doostan and H. Owhadi. A non-adapted sparse approximation of PDEs with stochastic inputs. J. Comput. Phys., 230(8): 3015-3034, 2011
work page 2011
-
[5]
J. Hampton and A. Doostan. Compressive sampling of polynomial chaos expansions: Con- vergence analysis and sampling strategies. J. Comput. Phys., 280: 363-386, 2015
work page 2015
-
[6]
L. Mathelin and K. A. Gallivan. A compressed sensing approach for partial differential equa- tions with random input data. Commun. Comput. Phys., 12(4): 919-954, 2012
work page 2012
-
[7]
A. Narayan and T. Zhou. Stochastic collocation on unstructured multivariate meshes. Com- mun. Comput. Phys., 18(1): 1-36, 2015
work page 2015
-
[8]
J. Peng, J. Hampton, and A. Doostan. A weighted l1-minimization approach for sparse poly- nomial chaos expansions. J. Comput. Phys., 267: 92-111, 2014
work page 2014
Show all 19 references
-
[9]
Rauhut and R
H. Rauhut and R. Ward. Sparse recovery for spherical harmonic expansions. In Proceedings of the 9th International Conference on Sampling Theory and Applications, 2011
2011
-
[10]
Rauhut and R
H. Rauhut and R. Ward. Sparse Legendre expansions vial1-minimization. J. Approx. Theory, 164(5):517-533, 2012
2012
-
[11]
Rauhut and R
H. Rauhut and R. Ward. Interpolation via weighted l1-minimization. Appl. Comput. Har- mon. Anal., 40(2): 321-351, 2016
2016
-
[12]
L. Yan, L. Guo, and D. Xiu. Stochastic collocation algorithms using l1-minimization. Int. J. Uncertain. Quantif., 2(3): 279-293, 2012
2012
-
[13]
Yang and G
X. Yang and G. E. Karniadakis. Reweighted l1 minimization method for stochastic elliptic differential equations. J. Comput. Phys., 248: 87-108, 2013
2013
-
[14]
Huang, R
A. Huang, R. Feng and S. Zheng. The recovery guarantee for orthogonal matching pursuit method to reconstruct sparse polynomials. Numer. Math. Theor. Meth. Appl., 15(3): 793-818, 2022
2022
-
[15]
R. Feng, A. Huang, M. Lai and Z. Shen, Reconstruction of sparse polynomials via quasi- orthogonal matching pursuit method, J. Comput. Math., 41(1): 18-38, 2023
2023
-
[16]
B. Adcock. Infinite-dimensional compressed sensing and function interpolation. Found. Comput. Math., 18(3): 661–701, 2018
2018
-
[17]
Natanson
I. Natanson. Constructive function theory, volume one, Science Press, first edition, 1958
1958
-
[18]
Fornasier and H
M. Fornasier and H. Rauhut, Compressive sensing, in: O. Scherzer (Ed.), Handbook of Math- ematical Methods in Imaging, Springer, 187–228, 2011
2011
-
[19]
Yang and Y
J. Yang and Y. Zhang. Alternating direction algorithms for l1-problems in compressive sens- ing. Siam. J. Sci. Comput., 33(1): 250–278, 2011
2011
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.