Pith. sign in

REVIEW 6 minor 23 references

Some lower bounds for optimal sampling recovery of functions with mixed smoothness

T0 review · 0 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Nonlinear sampling recovery of mixed-smoothness classes cannot beat $m^{-r+1/q-1/p}(\log m)^{(d-1)/p}$ in $L_p$, for $1\le q\le p<\infty$, $p>1$, $r>1/q$.

desk verdict A genuine new lower bound with a log factor for sampling recovery on H^r_q; the main proof is correct, with only routine fixable gaps in the secondary sections. read the letter →

arxiv 2412.02797 v2 pith:RWFZO3VL submitted 2024-12-03 math.NA cs.NAmath.FA

A. Gasnikov , V. Temlyakov This is my paper · ORCID
classification math.NAcs.NAmath.FA MSC 41A4641A6342B05
keywords optimalsamplingrecoverynonlinearlowerboundsmixedsmoothnessH^r_qclasseshyperboliccrossLittlewood-Paleyblockstrigonometricpolynomials
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that no nonlinear rule using $m$ point evaluations can recover every function in the mixed-smoothness class $H^r_q$ (periodic functions with bounded mixed differences in $L_q$) with $L_p$ error better than a constant multiple of $m^{-r+1/q-1/p}(\log m)^{(d-1)/p}$, in the range $1\le q\le p<\infty$, $p>1$, $r>1/q$. The logarithmic factor is the new content: earlier arguments gave only $m^{-r+1/q-1/p}$. The result matters because nonlinear sampling recovery is much harder to lower-bound than linear recovery, since Kolmogorov-width theory does not apply, and the authors show that two simple observations, block separation and symmetry of the class, are enough to force the log factor. A companion result gives an $m^{-r}(\log m)^{d-1}$ lower bound for recovering $H^r_\infty$ in $L_1$. If correct, the main bound matches the known linear-recovery upper bounds in the relevant range and shows the log penalty is an intrinsic feature of the problem.

What carries the argument

The load-bearing object is the dyadic block decomposition of a periodic function: for a multi-index $s$ with nonnegative integer coordinates, $\rho(s)$ is the set of frequencies $k$ with $2^{s_j-1}\le |k_j|<2^{s_j}$, and $A_s(f)$ is the projection of $f$ onto those frequencies. The paper works with the model class $H(Q_n)_q=\{f\in T(Q_n): \|A_s(f)\|_q\le 1\}$, which by Theorem 2.1 embeds into $H^r_q$ with constants independent of $n$. The proof then fixes any set of $m$ sample points, chooses the separated index family $Y_{n,3}$ (multi-indices with all coordinates divisible by 3 and $\|s\|_1=n$), and builds $f=\sum_{s\in Y_{n,3}} g_{\xi,s}K_{2^{s-2}}(x-x^*_s)$, a sum of localized trigonometric blocks each vanishing at the sample points. Separation ensures the blocks do not merge, and a Littlewood-Paley-type norm inequality (Theorem 2.2) gives $\|f\|_p\ge c\,2^{n(1-1/p)}n^{(d-1)/p}$. Finally, the symmetry observation of Proposition 6.1 converts a large-norm function vanishing on the samples into a lower bound for the recovery error.

What would settle it

Compute the $L_p$ norm of the test function $f=\sum_{s\in Y_{n,3}} t_s$ from Lemma 3.2 for, say, $d=2$, $q=p=2$, and increasing $n$; if $\|f\|_2$ grows slower than $2^{n/2}n^{1/2}$, the claimed lower bound fails. Alternatively, exhibit any nonlinear recovery rule for $H^r_q$ in $L_p$ with error $o\bigl(m^{-r+1/q-1/p}(\log m)^{(d-1)/p}\bigr)$ along some subsequence $m\to\infty$.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.3: for $1\le q\le p<\infty$, $p>1$, $r>1/q$, the optimal nonlinear sampling recovery error satisfies $\rho^o_m(H^r_q,L_p) \ge c(d)\, m^{-r+1/q-1/p}(\log m)^{(d-1)/p}$. Here $H^r_q$ is the class of multivariate periodic functions whose mixed differences satisfy $\|\Delta^l_{t(e)} f\|_q \le B \prod_{j\in e}|t_j|^r$, and $\rho^o_m$ is the infimum, over all choices of $m$ sample points and all mappings from sample values to functions, of the worst-case $L_p$ error. The proof constructs, for any proposed sampling scheme, a function in a closely related dyadic-block class $H(Q_n)_q$ that vanishes at all $m$ sample points and yet has $L_p$ norm at least $c\,2^{n(1-1/p)}n^{(d-1)/p}$; because the class is symmetric, both this function and its negative are admissible, so any recovery map must err by at least this norm. The new logarithmic factor $n^{(d-1)/p}$, equivalently $(\log m)^{(d-1)/p}$, comes from the number of separated frequency blocks available at level $n$.

Load-bearing premise

The proof needs the equivalence between the mixed-difference definition of $H^r_q$ and the dyadic-block condition to hold with a constant that does not grow with the level $n$, and it needs the frequency blocks $u(s)$ produced by the construction to stay pairwise distinct; the paper asserts the second point with 'it is easy to derive' and does not give the constant bookkeeping.

Editorial extensions

If this is right

  • No nonlinear algorithm, however adaptive, can recover all of $H^r_q$ from $m$ point values in $L_p$ at a rate better than $m^{-r+1/q-1/p}(\log m)^{(d-1)/p}$ in the range $1\le q\le p<\infty$, $p>1$.
  • The logarithmic factor is necessary for every dimension $d>1$ and every finite $p$, not an artifact of particular algorithms.
  • In the range where the known linear-recovery upper bound carries the same $(\log m)^{(d-1)/p}$ factor, the optimal nonlinear recovery rate is now pinned down up to constants.
  • For recovery of $H^r_\infty$ in $L_1$, the full $(\log m)^{d-1}$ factor is forced, matching the known upper bound.
  • Because the sampling functionals in the construction can be replaced by arbitrary linear functionals, the same bounds hold for Gelfand widths of these classes.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The construction is insensitive to how the recovery map processes the samples, so this style of lower bound should also apply to adaptive sampling designs, provided the eventually chosen sample set is among the sets considered.
  • The matching log exponents between this lower bound and known linear upper bounds suggest that, for $H^r_q$ classes in the range $1<q\le 2\le p<\infty$, nonlinear methods may not improve the rate of sampling recovery over linear ones, in contrast to the known situation for $W^r_q$ classes in $L_2$.
  • A natural next test is whether the same block-separation idea transfers to non-periodic or stochastic sampling settings, where the vanishing-at-sample trick would need a different localization argument.
  • The dyadic-block norm comparison used here could be sharpened to give matching constants in the log exponent for the structural classes $H^{a,b}_{A_\beta}$, complementing the upper bounds already known for those classes.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies lower bounds for the optimal nonlinear sampling recovery characteristic rho^o_m(W,L_p) on classes of multivariate periodic functions with mixed smoothness. The main result (Theorem 1.3) states that for 1 ≤ q ≤ p < ∞, p > 1, r > 1/q, one has rho^o_m(H^r_q,L_p) ≥ c(d) m^{-r+1/q-1/p} (log m)^{(d-1)/p}. The proof constructs, for an arbitrary set of m sample points, a trigonometric polynomial f that vanishes at all sample points, has small dyadic-block norms ||A_s(f)||_q (so that a scaled version belongs to a model class H(Q_n)_q), and has large L_p norm by virtue of a Littlewood-Paley-type lower bound. The model-class lower bound is then transferred to H^r_q via the known equivalence between the mixed-difference definition and the dyadic-block decay condition (Theorem 2.1). Additional results include a lower bound rho^o_m(H^r_infty,L_1) ≥ c m^{-r} (log m)^{d-1} (Proposition 1.2), lower bounds for classes with structural coefficient conditions in Section 5, and consequences for Gelfand widths.

Significance. If the result is correct, Theorem 1.3 provides a new lower bound with a logarithmic factor (log m)^{(d-1)/p} for nonlinear sampling recovery on the H^r_q classes, improving on the previously known m^{-r+1/q-1/p} bound that follows from trigonometric-width techniques. The argument is elementary and self-contained once the cited tools (Theorem 2.1, Theorem 2.2, Lemma 3.1 from [21], and the quadrature example from [15]) are accepted; these are published results with independent proofs, and no circularity is apparent. The paper also demonstrates the usefulness of a simple two-function comparison principle (Proposition 6.1) and gives lower bounds for related structural classes and Gelfand widths. The proofs are constructive and checkable, though some deductions are terse.

minor comments (6)
  1. [Section 3, Lemma 3.2 and Theorem 1.3] The constant in the lower bound is written as c(d), but the proof passes through Theorem 2.2 with u = p, whose constants depend on p, and through Theorem 2.1, whose constants depend on r,d,q,l. The deduction also introduces a factor depending on r through the scaling 2^{-rn}. Please rephrase the statements to make the parameter dependence of the constant explicit (e.g., c(r,d,p,q)), or explain why the constant can be chosen independent of these parameters.
  2. [Section 3, after Lemma 3.2] The statement that Theorem 1.3 is a direct corollary of Lemma 3.2 is not accompanied by the derivation. Since the transition from the model class H(Q_{n+b})_q to H^r_q and the change of variables from n to m is a key step, please add a short paragraph showing that choosing n with m ≤ S_n/2 and S_n ≍ 2^n yields 2^{-n} ≍ m^{-1} and n^{(d-1)/p} ≍ (log m)^{(d-1)/p}.
  3. [Section 3, display (3.4)] The claim 'It is easy to derive from here that for each s ... there exists u(s) ...' is correct but terse. Please add one or two sentences explaining that t_s has frequency support contained in the union of the 3^d blocks {s_j-1, s_j, s_j+1}^d and that the sup norm of t_s is bounded by the sum of the sup norms of its block projections, so that one block must contain at least a fixed fraction of the norm.
  4. [Section 5, bound (5.15)] The lower bound for p = 1 is derived by saying 'in the same way as we derived Theorem 5.1 from the example built in the proof of Lemma 3.2', but the analogous block-norm estimates for the functions from Section 4 are not shown. Since (5.15) is a new result, please provide the key estimates for |δ_s(t)|_{A_β} and ||t||_1 that lead to the stated exponent.
  5. [Section 1, Proposition 1.1] In the proof of (1.4), the step from (2.8) to (2.9) implicitly uses that the number of indices s with ||s||_1 = j is O(j^{d-1}); stating this explicitly would help the reader follow the bookkeeping.
  6. [Abstract and Introduction] There are several spacing and typographical errors (e.g., 'M ostly', 'boun ds', 'pro blem') in the abstract and first paragraphs; these should be corrected in the final version.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1.3 is derived from explicit constructions and external, parameter-free theorems; self-citations are not load-bearing.

full rationale

The paper's central claim, Theorem 1.3, is obtained as a direct corollary of Lemma 3.2, whose proof builds an explicit trigonometric polynomial f (Equation (3.1)) vanishing at the m sampling points, then measures ||f||_p via the known Littlewood-Paley type relation (2.11). The transfer from the block model class H(Q_n)_q to H^r_q uses Theorem 2.1, quoted from [18] p.137, which is a classical equivalence between mixed differences and dyadic-block L_q bounds with constants independent of n; this is a parameter-free external theorem, not a restatement of the target lower bound. The lower bound for polynomials, Lemma 3.1 from [21], and the quadrature example from [15] used in Sections 4-5 are prior published results with independent proofs; while the authors cite themselves, none of these citations assumes Theorem 1.3 or the logarithmic factor being proved. No fitted parameter is renamed as a prediction, and no quantity is defined in terms of the conclusion. The terseness in the proof of Lemma 3.2, such as the 'it is easy to derive' distinctness of the u(s) blocks, concerns presentation rather than circularity: the argument is reconstructible from the displayed disjoint-support reasoning and does not import the desired inequality. Therefore the derivation chain is self-contained for the purposes of circularity analysis.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard results from harmonic analysis (Theorem 2.2 from [14], kernel norm estimates from [18]) and on prior constructions by the same research line (Lemma 3.1 from [21], the test-function family from [15]). No free parameters are fitted and no new entities are postulated; all constants are generic and depend only on r,d,p,q. The axioms are external theorems, not assumptions tailored to force the result.

assumptions (6)
  • domain assumption Equivalence of H^r_q with different l, and the dyadic block characterization (Theorem 2.1, quoted from [18], p.137): f ∈ H^r_q iff ||A_s(f)||_q ≤ C 2^{-r||s||_1}.
    Used in Section 3 to embed the model class H(Q_n)_q into H^r_q with constant C(b) independent of n, and to normalize h in Lemma 3.2. Without it the lower bound for the model class would not transfer to the true H^r_q class.
  • standard math Theorem 2.2 (Littlewood-Paley type norm estimates, from [14]): sup over G(ε,v) and inf over F(ε,v) are ≍ (∑ ε_s^u 2^{||s||_1(u/v-1)})^{1/u}.
    Used to derive the L_p lower bound (3.6) for f = ∑ t_s and the L1 bounds in Section 4. The key property is that disjoint blocks contribute additively in the relevant norm.
  • standard math A-norm (ℓ1 norm of Fourier coefficients) comparison on dyadic blocks: Theorem 2.3 and Proposition 5.1 for general uniformly bounded orthonormal systems.
    Used in the embedding proof of Proposition 1.1 and in Section 5 to estimate the A_β quasi-norm of the test functions t_s.
  • domain assumption Lemma 3.1 from [21]: for m ≤ ϑ(N)/2, ρ^o_m(T(2N,d)_q, L_p) ≥ c(d) ϑ(N)^{1/q-1/p}.
    Starting point for the refined Lemma 3.2 and for the W^r_q lower bound in Remark 3.1. The paper extends this lemma to a more carefully selected set of frequency blocks.
  • domain assumption The construction of [15] (see also [18], pp.264-266): for any N ≤ 2^{n-1} points there exist t_s ∈ T(2^{s-1},d) vanishing at the points, ‖t_s‖_∞ ≤ 1, with ∫ t(x) dx ≥ c(d) n^{d-1} for t = ∑_{‖s‖_1=n} t_s.
    Load-bearing for Proposition 1.2 and the p=1 bound (5.15); the H^r_∞ membership of a scaled version of t is proven in the paper using Theorem 2.1.
  • standard math Standard norm estimates for the Fejér and de la Vallée Poussin kernels, e.g., ‖K_{2^{s-2}}‖_q ≤ C 2^{n(1-1/q)} and K(0) ≍ 2^n.
    Used in inequalities (3.2) and (3.5) to control the L_q norm and point values of t_s = g K.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Some lower bounds for optimal sampling recovery of functions with mixed smoothness." pith.science (2026). https://pith.science/paper/RWFZO3VL

@misc{pith2026241202797,
  author       = {Pith},
  title        = {Pith review of: Some lower bounds for optimal sampling recovery of functions with mixed smoothness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RWFZO3VL}},
  note         = {Machine review of arXiv:2412.02797}
}
read the original abstract

Recently, there was a substantial progress in the problem of sampling recovery on function classes with mixed smoothness. Mostly, it has been done by proving new and sometimes optimal upper bounds for both linear sampling recovery and for nonlinear sampling recovery. In this paper we address the problem of lower bounds for the optimal rates of nonlinear sampling recovery. In the case of linear recovery one can use the well developed theory of estimating the Kolmogorov and linear widths for establishing some lower bounds for the optimal rates. In the case of nonlinear recovery we cannot use the above approach. It seems like the only technique, which is available now, is based on some simple observations. We demonstrate how these observations can be used.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

  1. [21]

    Sparse sampling recovery in integral norms on some function classes

    V. Temlyakov, Sparse sampling recovery in integral norms on so me function classes, arXiv:2401.14670v1 [math.NA] 26 Jan 2024. 21

    work page Pith review arXiv 2024

  2. [15]

    Temlyakov, On a way of obtaining lower estimates for the er- rors of quadrature formulas, Matem

    V.N. Temlyakov, On a way of obtaining lower estimates for the er- rors of quadrature formulas, Matem. Sbornik, 181 (1990), 1403–1413; English transl. in Math. USSR Sbornik, 71 (1992)

    work page 1990

  3. [1]

    A sharp upper bound for sampling numbers in $L_{2}$

    M. Dolbeault , D. Krieg, and M. Ullrich, A sharp upper bound for sampling numbers in L2, Appl. Comput. Harmon. Anal. 63 (2023), 113–134; arXiv:2204.12621v1 [math.NA] 26 Apr 2022

    work page Pith review arXiv 2023

  4. [2]

    Universal discretization and sparse sampling recovery

    F. Dai and V.N. Temlyakov, Universal discretization and sparse s am- pling recovery, arXiv:2301.05962v1 [math.NA] 14 Jan 2023

    work page Pith review arXiv 2023

  5. [3]

    Random points are good for universal discretization

    F. Dai and V.N. Temlyakov, Random points are good for uni- versal discretization, J. Math. Anal. Appl., 529 (2024) 127570; arXiv.2301.12536[math.F A] 5 Feb 2023

    work page Pith review arXiv 2024

  6. [4]

    Lebesgue-type inequalities in sparse sampling recovery

    F. Dai and V.N. Temlyakov, Lebesgue-type inequalities in sparse s am- pling recovery, arXiv:2307.04161v1 [math.NA] 9 Jul 2023

    work page Pith review arXiv 2023

  7. [5]

    Hyperbolic Cross Approximation

    Dinh D˜ ung, V.N. Temlyakov, and T. Ullrich, Hyperbolic Cross Ap- proximation, Advanced Courses in Mathematics CRM Barcelona, Birkh¨ auser, 2018; arXiv:1601.03978v2 [math.NA] 2 Dec 2016

    work page Pith review arXiv 2018

  8. [6]

    T. Jahn, T. Ullrich, and F. Voigtlaender, Sampling numbers of smoothness classes via ℓ1-minimization, arXiv:2212.00445v3 [math.NA] 31 Jul 2023

    work page Pith review arXiv 2023

Show all 23 references
  1. [7]

    Kosov and V

    E. Kosov and V. Temlyakov, Bounds for the sampling discretiza- tion error and their applications to universal sampling discretization , arXiv:2312.05670v2 [math.NA] 27 Jan 2024

    2024 arXiv

  2. [8]

    Krieg and M

    D. Krieg and M. Ullrich, Function values are enough for L2-ap- proximation, Found. Comp. Math. , doi:10.1007/s10208-020-09481-w; arXiv:1905.02516v4 [math.NA] 19 Mar 2020

    1905 arXiv

  3. [9]

    Krieg and M

    D. Krieg and M. Ullrich, Function values are enough for L2- approximation: Part II, J. Complexity , doi:10.1016/j.jco.2021.101569; arXiv:2011.01779v1 [math.NA] 3 Nov 2020

    2021

  4. [10]

    Nagel, M

    N. Nagel, M. Sch¨ afer, T. Ullrich, A new upper bound for sam- pling numbers, Found. Comp. Math. , Pub Date: 2021-04-26, DOI: 10.1007/s10208-021-09504-0; arXiv:2010.00327v1 [math.NA] 30 S ep 2020. 20

    2021 arXiv

  5. [11]

    Smolyak, Quadrature and interpolation formulas for tenso r prod- ucts of certain classes of functions

    S.A. Smolyak, Quadrature and interpolation formulas for tenso r prod- ucts of certain classes of functions. Dokl. Akad. Nauk SSSR, 148 (1963), 10421045; English translation in Soviet Math. Dokl., 4 (1963 )

    1963

  6. [12]

    Solodov and V.N

    A.P. Solodov and V.N. Temlyakov, Sampling recovery on function classes with a structural condition, arXiv:2404.07210v2 [math.NA] 2 5 Jun 2024

    2024 arXiv

  7. [13]

    Temlyakov, Approximation of Periodic Functions of Several Vari- ables by Bilinear Forms, Izvestiya AN SSSR, Ser

    V.N. Temlyakov, Approximation of Periodic Functions of Several Vari- ables by Bilinear Forms, Izvestiya AN SSSR, Ser. Mat., 50 (1986), 137–155; English transl. in Mathematics of the USSR-Izvestia, 28 (1987), 133–150

    1986

  8. [14]

    Temlyakov, Approximation of functions with bounded mixed derivative, Trudy MIAN, 178 (1986), 1–112

    V.N. Temlyakov, Approximation of functions with bounded mixed derivative, Trudy MIAN, 178 (1986), 1–112. English transl. in Proc. Steklov Inst. Math., 1 (1989)

    1986

  9. [16]

    Temlyakov, On Approximate Recovery of Functions with Bounded Mixed Derivative, J

    V.N. Temlyakov, On Approximate Recovery of Functions with Bounded Mixed Derivative, J. Complexity, 9 (1993), 41–59

    1993

  10. [17]

    Temlyakov, Constructive sparse trigonometric approxima tion and other problems for functions with mixed smoothness, arXiv: 1412.8647v1 [math.NA] 24 Dec 2014, 1–37; Matem

    V.N. Temlyakov, Constructive sparse trigonometric approxima tion and other problems for functions with mixed smoothness, arXiv: 1412.8647v1 [math.NA] 24 Dec 2014, 1–37; Matem. Sb., 206 (2015), 131–160

    2015 arXiv

  11. [18]

    Temlyakov, Multivariate Approximation , Cambridge University Press, 2018

    V. Temlyakov, Multivariate Approximation , Cambridge University Press, 2018

    2018

  12. [19]

    Temlyakov, On optimal recovery in L2, J

    V.N. Temlyakov, On optimal recovery in L2, J. Complexity 65 (2021), 101545; arXiv:2010.03103v1 [math.NA] 7 Oct 2020

    2021 arXiv

  13. [20]

    Temlyakov, Sparse sampling recovery by greedy algorithms, arXiv:2312.13163v2 [math.NA] 30 Dec 2023

    V. Temlyakov, Sparse sampling recovery by greedy algorithms, arXiv:2312.13163v2 [math.NA] 30 Dec 2023

    2023 arXiv

  14. [22]

    Temlyakov and T

    V.N. Temlyakov and T. Ullrich, Bounds on Kolmogorov widths of classes with small mixed smoothness, J. Complexity, Available online 4 May 2021, 101575; arXiv:2012.09925v1 [math.NA] 17 Dec 2020

    2021 arXiv

  15. [23]

    Traub, G.W

    J.F. Traub, G.W. Wasilkowski, and H. Wo´ zniakowski, Information - Based Complexity, Academic Press, Inc., 1988. A.V. Gasnikov, Ivannikov institute for System Programming of Russian Acad emy of Sci- ences, Moscow, Russia; Steklov Mathematical Institute of Russian Academy of Sc...

    1988

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.