{"id":"827b3d53-3562-4357-a8aa-7b6cbc3a5bb7","arxiv_id":"2506.06880","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Using the best-approximation polynomial as the reference signal, the paper treats the residual as bounded noise in l1-minimization and derives L-infinity and L2 error bounds for sparse polynomial approximation of continuous functions.","lead":"This paper derives a priori error bounds for sparse polynomial approximations of continuous functions by treating the best-approximation remainder as bounded noise in an l1-minimization problem. The bounds link approximation error to sparsity, a coefficient quasi-norm, and the best approximation error, and imply exact recovery when the target is itself a sparse polynomial.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The weighted l1 experiments in Tables 1–3 violate the hypotheses of Theorems 4.2/4.3: for ω1_i=√i and N=599, s≥2||ω||_∞^2=1200 forces m≳2.7e6, yet m=300–400, so the numerical validation lies outside the theorem's scope.","rationale":"I read the paper in good faith. The central mathematical contribution is a set of error bounds for sparse polynomial approximation by l1 and weighted l1 minimization, treating the best-approximation remainder as bounded noise. The proofs are short and correctly reduce to the cited Rauhut–Ward recovery theorems (Theorems 2.3 and 2.4), and the exact-recovery statement for sparse polynomial targets follows from the zero-noise case. The L∞ and L2 derivations are internally consistent, and the use of Stechkin's inequality and Jackson's theorem is sound. I therefore do not see a flaw that would falsify the theorems. The load-bearing weakness is in the evidential support for the weighted claims. The numerical experiments for Theorems 4.2 and 4.3 use weights that grow with the index and sample sizes that are tiny compared with the theorem's requirements. The condition s ≥ 2||ω||_∞^2 alone forces s to be at least O(N), and then m ≥ C s log^3(s) log(N+1) becomes superlinear in N, far exceeding the reported m. The paper checks only ω_j ≥ ||ψ_j||_∞ and never reports s, so the reader cannot tell whether the experiments fall under the theorems. Since the weighted experiments are a central part of the paper's claimed validation, this is a genuine concern. The reader's conditional verdict already captures this, and my analysis does not change the verdict: the theoretical claims appear correct, but the numerical support is insufficient as presented. The proposed concrete test—computing the minimum required m for the chosen weights and checking weighted sparsity—would settle the question of whether the experiments can be brought under Theorems 4.2/4.3.","tokens_in":16630,"tokens_out":25351,"duration_ms":262425,"concrete_test":"For the weights and N used in Tables 1–3, compute the minimal sample size m_min(s) = C s log^3(s) log(N+1) with C = 1 over all s ≥ 2||ω||_∞^2. If m_min(s) > m for every feasible s, as it does for ω1 and ω2, the experiments violate the theorem's hypotheses. Equivalently, report the weighted sparsity s# = ∑_{j: c#_j ≠ 0} ω_j^2 of the recovered vector from Table 1; if s# < 2||ω1||_∞^2 ≈ 1200, the condition s ≥ 2||ω||_∞^2 cannot be met, and the experiment is outside Theorem 4.2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 4.2 and 4.3 inherit from Rauhut–Ward the requirement that the sparsity parameter s satisfy both s ≥ 2||ω||_∞^2 and m ≥ C s log^3(s) log(N+1). The numerical section chooses weights ω1_i = √i and ω2_i = (i+1)/2 for i = 1,...,N+1, with N = 599 or 799 and m = 300 or 400. For ω1, ||ω1||_∞ = √(N+1), so s ≥ 2(N+1) ≈ 1200–1600; the sample condition alone then requires m ≥ C·1200·log^3(1200)·log(600) ≈ C·2.7×10^6 for C = 1, orders of magnitude above the reported m. For ω2, ||ω2||_∞ ≈ (N+2)/2 ≈ 300–400, forcing s ≳ 1.8×10^5 and m ≳ 10^11. No value of s satisfies both hypotheses at the used sample sizes. The paper only verifies the weight lower bound ω_j ≥ ||ψ_j||_∞ and never reports s or the weighted sparsity of the recovered vector. Consequently, Tables 1–3 cannot be cited as evidence for the effectiveness of the weighted l1 error estimates: the experiments operate in a regime where Theorems 4.2/4.3 do not apply. The unweighted experiments (N = 999, m = 400) similarly omit s, so their coverage under Theorem 3.1 is unverified. The theorems themselves are direct applications of the cited recovery results and appear mathematically sound; what is not supported is the paper's claim that the numerical results validate the proposed weighted scheme.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16959,"tokens_out":5833,"duration_ms":61281,"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":[{"comment":"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":"Section 5.2, Tables 1-3"},{"comment":"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":"Section 5.1, Figures 1-4"},{"comment":"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.","section":"Section 6, Summary"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"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":"Theorem 2.3 and Theorem 2.4"},{"comment":"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.","section":"Section 5.1, Figure 1"},{"comment":"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.","section":"Remark 4.2"},{"comment":"Reference [17] cites Natanson's book but no edition or year is given in the text; the full bibliographic details should be completed.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The theoretical core of the paper appears sound, and the error estimates are useful. The main weakness is the numerical section: the weighted experiments violate the stated hypotheses, and the unweighted experiments omit the required sparsity parameter, so the empirical claims are not supported. I recommend major revision rather than rejection because the theory is correct and the numerical issue is fixable by reporting s, using weights that satisfy s ≥ 2||ω||_infinity^2, or clearly labeling the experiments as heuristic. The authors should also temper the claim of practical efficacy given the acknowledged lack of a multivariate E_N computation method."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core theoretical contribution is real: the paper makes the l1 noise bound explicit by using the best uniform approximation error E_N as the noise level, and then derives L∞ and L2 error estimates for sparse polynomial recovery of continuous functions. The proofs in Sections 3 and 4 check out—the triangle inequality, the orthonormality step, and the use of the cited Rauhut–Ward theorems are all valid. The Jackson-based degree–sparsity trade-offs are a nice addition, and the exact recovery statement for sparse polynomial targets follows correctly from the zero-noise case. I agree with the reader that the mathematical heart is sound.\n\nWhere the paper is weak is the numerical section, and the stress-test note is right on target. In Tables 1–3, the weighted experiments use ω1_i = √i and ω2_i = (i+1)/2 with N=599 or 799 and m=300–400. For these weights, ||ω||_∞ is roughly √600 or 400, so the theorem condition s ≥ 2||ω||_∞^2 forces s to be at least 1200 (for ω1) or about 320000 (for ω2). The required m then grows to millions or billions, so the experiments operate far outside the regime of Theorems 4.2 and 4.3. The paper never reports s, which is a basic omission. The unweighted experiments also omit s, so one cannot verify that m=400 satisfies condition (3.1). The tuning of Θ to 10^5 is post hoc and the paper itself concedes there is no universal choice—that is honest, but it means the experiments demonstrate a heuristic rather than validate the theorems. The reliance on E_N being computable, which the paper admits is not the case in multivariate settings, is a minor point but makes the 'extends to multivariate' claim mostly aspirational.\n\nThere is also a small sloppiness in Theorem 4.1: using ||f||_{A_q} for general continuous f requires the Fourier coefficients to be in ℓ_q for q<1, which is not automatic; for many continuous functions that quasi-norm is infinite. The bound is still true when the norm is finite, but the statement would be cleaner if it said 'whenever the right-hand side is finite.'\n\nBottom line: this is a modest but sound theoretical paper. The central estimates are new as stated and worth having in the literature. The numerical validation needs to be either brought under the hypotheses or explicitly reframed as a heuristic study. I would send it to peer review, with the expectation that the experimental section gets revised or trimmed. A serious referee should catch the hypothesis violation, but the theory itself deserves a careful look.","headline":"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.","tokens_in":17558,"tokens_out":3394,"would_cite":true,"duration_ms":42604,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A10","41A05","65D15","46B09","68P30","90C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["l1-minimization method","weighted l1-minimization method","sparse polynomial approximation","best approximation","best s-term approximation error","continuous functions","approximation error estimates"],"falsifier":"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.","tokens_in":16352,"feed_emoji":"📉","tokens_out":13449,"duration_ms":129536,"temperature":0.7,"pith_summary":"This paper aims to turn the heuristic that smooth functions are nearly sparse in orthogonal polynomial bases into a quantitative error bound for a practical algorithm. The algorithm samples a continuous function, solves an $\\ell^1$-minimization problem whose noise level is set by the best uniform approximation error $E_N$ (or by the best square approximation tail in the L2 variants), and outputs a sparse polynomial $p^\\#$. The main theorems bound $\\|f-p^\\#\\|_\\infty$ and $\\|f-p^\\#\\|_2$ by a sum of a best s-term coefficient error and $E_N$, with constants depending on the basis sup-norm bound and the chosen noise multiplier $\\Theta$. The explicit form matters because it says how the error depends on quantities one can estimate before solving: sparsity, coefficient quasi-norm, and the best-approximation tail. A corollary is that exactly sparse polynomials are reconstructed exactly and that smoother functions require fewer degrees to reach a given accuracy.","feed_headline":"Sparse recovery error splits into sparsity term plus best-fit tail","feed_subtitle":"For any continuous function, l1-minimization error is controlled by sparsity s, coefficient quasi-norm, and tail E_N.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the unweighted l1 recovery guarantee that controls the coefficient error from noisy samples, the main engine of Theorem 3.1.","marker":"[10]"},{"why":"Supplies the weighted l1 recovery guarantee used in Theorems 4.2 and 4.3, including the removal of the uniform-boundedness condition.","marker":"[11]"},{"why":"Supplies the smoothness-to-approximation-rate results used to convert the tail $E_N$ into explicit powers of $N$ in the corollaries.","marker":"[17]"},{"why":"Supplies the quasi-norm estimate $\\sigma_s(c)_1\\le s^{1-1/q}\\|c\\|_q$ that produces the sparsity term in the final bounds.","marker":"[18]"},{"why":"Supplies the solver used for the l1 and weighted l1 numerical experiments reported in Section 5.","marker":"[19]"}],"fun_headline_variants":["Sparse recovery error: sparsity term plus tail","Error split: sparsity cost + best-fit tail","Exact sparse recovery when function is sparse polynomial","Weighted l1 skips uniform basis bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sparse recovery error: sparsity term plus tail","Error split: sparsity cost + best-fit tail","Exact sparse recovery when function is sparse polynomial","Weighted l1 skips uniform basis bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000259,"raw_usage":{"total_tokens":1659,"prompt_tokens":1089,"completion_tokens":570,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":705,"completion_tokens_details":{"reasoning_tokens":509}},"tokens_in":705,"tokens_out":570,"duration_ms":6157,"temperature":1.0,"reasoning_tokens":509,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:48:08.690200+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Rauhut and R","cited_arxiv_id":null,"evidence_quote":"Supplies the unweighted l1 recovery guarantee that controls the coefficient error from noisy samples, the main engine of Theorem 3.1."},{"cited_title":"Rauhut and R","cited_arxiv_id":null,"evidence_quote":"Supplies the weighted l1 recovery guarantee used in Theorems 4.2 and 4.3, including the removal of the uniform-boundedness condition."},{"cited_title":"Natanson","cited_arxiv_id":null,"evidence_quote":"Supplies the smoothness-to-approximation-rate results used to convert the tail $E_N$ into explicit powers of $N$ in the corollaries."},{"cited_title":"Fornasier and H","cited_arxiv_id":null,"evidence_quote":"Supplies the quasi-norm estimate $\\sigma_s(c)_1\\le s^{1-1/q}\\|c\\|_q$ that produces the sparsity term in the final bounds."},{"cited_title":"Yang and Y","cited_arxiv_id":null,"evidence_quote":"Supplies the solver used for the l1 and weighted l1 numerical experiments reported in Section 5."}],"review_version":1}