pith. sign in

arxiv: 2503.01696 · v3 · pith:F2ZIPJ2Inew · submitted 2025-03-03 · 🧮 math.NA · cs.NA

A hybrid Chebyshev-Tucker tensor format for approximation of multivariate functions

Peter Benner , Boris N. Khoromskij , Venera Khoromskaia , Bonan Sun This is my paper

Pith reviewed 2026-05-23 01:29 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords Chebyshev interpolationTucker decompositiontensor approximationmesh-free methodsmultivariate functionselectrostatic potentialsrange-separated formats
0
0 comments X

The pith

A hybrid Chebyshev-Tucker format computes near-optimal low-rank approximations of 3D functions from values at Chebyshev nodes alone.

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

The paper introduces a mesh-free two-level hybrid Chebyshev-Tucker tensor representation that pairs tensor-product Chebyshev interpolation with Tucker decomposition applied to the resulting coefficient tensor. This construction lets one obtain a nearly optimal Tucker decomposition for a 3D function to any prescribed accuracy ε by evaluating the function only at a modest number of Chebyshev nodes, without ever forming a full fine grid. The moderate-sized core tensor of coefficients admits a low-rank Tucker factorization whose ranks can stay far below the interpolation degrees, after which the same format is realized on arbitrarily large grids by simply discretizing the Chebyshev polynomials. The approach is illustrated on the long-range electrostatic potentials of multi-particle systems already stored in range-separated tensor formats.

Core claim

The central claim is that the nearly optimal Tucker decomposition of the 3D function with controllable accuracy ε >0 can be computed without discretizing the function on a full fine grid in the domain, but only using its values at a small set of Chebyshev nodes computed either from the explicit analytic expression or from its data-sparse representation in a rank-structured tensor format with moderate rank parameter; the resulting algebraic Tucker format with optimal ε-rank can then be realized on an arbitrarily large 3D tensor grid by discretizing the Chebyshev polynomials on that grid.

What carries the argument

hybrid Chebyshev-Tucker tensor representation that combines tensor-product Chebyshev interpolation with the low-rank Tucker decomposition of the tensor of Chebyshev coefficients

If this is right

  • The method avoids forming or storing function-related tensors on large spatial grids.
  • The algebraic Tucker representation with optimal ε-rank can be obtained on arbitrarily large computational domains.
  • The technique applies directly to the long-range part of singular electrostatic potentials stored in range-separated tensor formats.
  • Error bounds and complexity estimates scale with the size of the Chebyshev coefficient tensor rather than the full grid size.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same two-level idea could be tested with other polynomial or non-polynomial bases whose coefficient tensors exhibit rapid rank decay.
  • For functions whose singularities are already separated, the hybrid format might serve as a post-processing step that further compresses an existing range-separated representation.
  • Numerical checks on the growth of Tucker ranks versus polynomial degree for standard singular kernels would quantify the regime where the rank reduction holds.

Load-bearing premise

The tensor of Chebyshev interpolation coefficients admits a low-rank Tucker decomposition whose ranks remain much smaller than the polynomial degrees while preserving the target accuracy ε.

What would settle it

If, for any sequence of test functions whose analytic form is known, the Tucker ranks needed to approximate the Chebyshev coefficient tensor to accuracy ε grow proportionally to the polynomial degree, the claimed complexity advantage disappears.

Figures

Figures reproduced from arXiv: 2503.01696 by Bonan Sun, Boris N. Khoromskij, Peter Benner, Venera Khoromskaia.

Figure 1
Figure 1. Figure 1: Left: the canonical vectors p (1) k for k = 1, . . . , R, R = 26, along the x-axis for the rank-R CP tensor approximation of collocation tensor of size PR ∈ R n×n×n with n = 256. Right: canonical vectors a (1) k of the long-range part in the total potential ARl ∈ R n×n×n with N = 500 particles and grid size n = 256 for k = 1, . . . , 8. Cartesian grid for n = 256, presented for example in [37, 34]. In this… view at source ↗
Figure 2
Figure 2. Figure 2: Relative ℓ∞ error (4.5) of the Chebyshev interpolation of the canonical vectors vs. the degree of the Chebyshev interpolant. Each line represents the error of the Chebyshev interpolant of a canonical vector pk for k = 1, . . . , 15 (left) and k = 16, . . . , 39 (middle). Right: Relative ℓ∞ error of the degree m = 129 Chebyshev interpolation of the canonical vectors vs. the index k of the univariate functio… view at source ↗
Figure 3
Figure 3. Figure 3: Absolute values of the Chebyshev coefficients of the degree-129 Chebyshev [PITH_FULL_IMAGE:figures/full_fig_p018_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Left: Middle slice ARl (:, :, n/2) of the (compressed) long-range part of the RS tensor for the electrostatic potential of the biomolecule with N = 500 particles computed on the 3D n × n × n Cartesian grid with n = 1024 and rank Rl = 506. Middle: the error of the canonical-to-Tucker transform, with ε = 10−6 . Right: the total error of the canonical-to-canonical tensor transform with the ε = 10−5 . 4.2.1. T… view at source ↗
Figure 5
Figure 5. Figure 5: Left: the middle slice ˆfm(:, :, tn/2) ≈ ARl (:, :, n/2) of the degree m = 129 ChebTuck format of the biomolecule with N = 500 and n = 256. Middle: the error during RHOSVD compression, i.e. ˆfm(:, :, tn/2)− ˜fm(:, :, tn/2). Right: the total error ˆfm(:, :, tn/2) − ARl (:, :, n/2) [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The degree m = 129 ChebTuck approximation total error ˆfm(:, :, tn/2)−ARl (: , :, n/2) of the biomolecule for grid sizes n = 512, 1024, 2048 from left to right. We can see that the Tucker rank grows only mildly with respect to the number of particles N. To have a closer look at the actual behavior, we also plot the singular values of the mode-2 side matrices of the Chebyshev coefficient tensor C (which is … view at source ↗
Figure 7
Figure 7. Figure 7: The total error ˆfm(:, :, tn/2) − ARl (:, :, n/2) of the degree m = 129 ChebTuck approximation of the biomolecule for grid size n = 2048 with different univariate interpolations in (3.8). Left: cubic spline, middle: piecewise linear, right: nearest neighbor [PITH_FULL_IMAGE:figures/full_fig_p023_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Left: Singular values of the mode-2 side matrices of the Chebyshev coefficient tensor C ∈ R m×m×m with m = 129 for the long-range part of the total potential in the biomolecule with n = 2048. Right: the zoom-in from the 10th to the 40th singular values of the same plot. proach to lattice summation of electrostatic potentials. Fast computation of lattice potentials was since longer an important topic of num… view at source ↗
Figure 9
Figure 9. Figure 9: Left: the middle slice ˆfm(:, :, tn/2) ≈ ARl (:, :, n/2) of the degree m = 129 ChebTuck format for the long-range part of a lattice structure with N = 2304 and n = 960. Middle: the error during RHOSVD compression, i.e. ˆfm(:, :, tn/2) − ˜fm(:, : , tn/2). Right: the total error ˆfm(:, :, tn/2) − ARl (:, :, n/2). 5. Conclusions. We introduce and analyze a mesh-free two-level hybrid Tucker tensor format for a… view at source ↗
read the original abstract

We introduce and analyze a mesh-free two-level hybrid Chebyshev-Tucker tensor representation for approximating multivariate functions, which combines tensor-product Chebyshev interpolation with the low-rank Tucker decomposition of the tensor of Chebyshev coefficients. This construction allows to avoid the expensive rank-structured grid-based approximation of function-related tensors on large spatial grids, while benefiting from the Tucker decomposition of the moderate-sized core tensor of Chebyshev coefficients. Thus, we can compute the nearly optimal Tucker decomposition of the 3D function with controllable accuracy $\varepsilon >0$ without discretizing the function on a full fine grid in the domain, but only using its values at a small set of Chebyshev nodes computed either from the explicit analytic expression of the target function or from its data-sparse representation in a rank-structured tensor format with moderate rank parameter. Finally, we can represent the function in the algebraic Tucker format with optimal $\varepsilon$-rank on an arbitrarily large 3D tensor grid in the computational domain by discretizing the Chebyshev polynomials on that grid. The rank parameters of the nonlinear Tucker-ALS decomposition of the coefficient tensor can be much smaller than the polynomial degrees of the initial Chebyshev linear interpolation in the function independent polynomial basis set. It is shown that our techniques can be gainfully applied to the long-range part of the singular electrostatic potential of multi-particle systems represented on a fine grid in the range-separated (RS) tensor format. We provide error and complexity estimates and demonstrate the computational efficiency of the proposed techniques on challenging examples, including the collective electrostatic potential for large bio-molecular systems and lattice-type compounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a hybrid Chebyshev-Tucker tensor format that combines tensor-product Chebyshev interpolation of a multivariate function with a subsequent Tucker decomposition applied to the moderate-sized tensor of Chebyshev coefficients. This construction is claimed to yield a nearly optimal algebraic Tucker representation of controllable accuracy ε for 3D functions (in particular the long-range part of singular electrostatic potentials given in rank-separated format) while using only function evaluations at a small set of Chebyshev nodes and avoiding discretization on a full fine spatial grid; error and complexity estimates are stated to be derived, and numerical efficiency is demonstrated on bio-molecular and lattice examples.

Significance. If the central low-rank property of the Chebyshev-coefficient tensor holds with ranks substantially smaller than the polynomial degree, the method offers a mesh-free route to near-optimal Tucker approximations whose cost scales with the coefficient-tensor size rather than the target grid size; this would be a useful addition to the existing toolkit of tensor methods for high-dimensional approximation in computational physics and chemistry. The paper supplies both theoretical estimates and concrete numerical evidence on challenging electrostatic problems, which strengthens its practical relevance.

major comments (2)
  1. [Abstract, §3] Abstract and the paragraph following Eq. (3.4) (or the corresponding complexity statement): the advertised complexity saving relative to a direct fine-grid Tucker approximation rests on the claim that the Tucker ranks r of the (n+1)^3 Chebyshev-coefficient tensor satisfy r ≪ n while preserving the target accuracy ε. No explicit general bound relating r to ε, the smoothness of the long-range kernel, or the RS separation parameter is provided; only numerical evidence for specific electrostatic instances is shown. Without such a bound the O(n^3 r) cost of the Tucker-ALS step on the coefficient tensor may not remain sub-cubic in n, undermining the central complexity claim.
  2. [§4] Section 4 (error estimates): the error analysis appears to combine the standard Chebyshev interpolation error with the Tucker truncation error, but the interaction term arising when the coefficient tensor is only approximately low-rank is not bounded explicitly in terms of the RS rank and the separation distance; this interaction is load-bearing for the controllable-accuracy statement when the target function is given only in RS format.
minor comments (2)
  1. [§2] Notation for the Tucker core and factor matrices is introduced without a single consolidated table; a small summary table would improve readability.
  2. [§5] The numerical examples report CPU times and storage but do not tabulate the observed Tucker ranks versus polynomial degree n and tolerance ε; adding such a table would make the rank-reduction claim easier to verify.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address the two major comments point by point below, indicating the revisions that will be made.

read point-by-point responses

  1. Referee: [Abstract, §3] Abstract and the paragraph following Eq. (3.4) (or the corresponding complexity statement): the advertised complexity saving relative to a direct fine-grid Tucker approximation rests on the claim that the Tucker ranks r of the (n+1)^3 Chebyshev-coefficient tensor satisfy r ≪ n while preserving the target accuracy ε. No explicit general bound relating r to ε, the smoothness of the long-range kernel, or the RS separation parameter is provided; only numerical evidence for specific electrostatic instances is shown. Without such a bound the O(n^3 r) cost of the Tucker-ALS step on the coefficient tensor may not remain sub-cubic in n, undermining the central complexity claim.

    Authors: We agree that no explicit general bound relating the Tucker ranks r to ε, kernel smoothness, or RS parameters is derived. The complexity statements in the abstract and following Eq. (3.4) are based on the observed property that r ≪ n for the range-separated electrostatic potentials considered, as demonstrated by the numerical experiments in Section 5. We will revise the abstract and the relevant paragraph in §3 to state explicitly that the O(n^3 r) cost yields a practical complexity advantage when the low-rank property holds (as verified numerically for the target class of functions), rather than claiming unconditional sub-cubic scaling in n. This clarifies the scope of the complexity claim without overstating the theoretical guarantees. revision: partial

  2. Referee: [§4] Section 4 (error estimates): the error analysis appears to combine the standard Chebyshev interpolation error with the Tucker truncation error, but the interaction term arising when the coefficient tensor is only approximately low-rank is not bounded explicitly in terms of the RS rank and the separation distance; this interaction is load-bearing for the controllable-accuracy statement when the target function is given only in RS format.

    Authors: The error estimate in Section 4 is formed as the sum of the standard Chebyshev interpolation error and the Tucker truncation error on the coefficient tensor. For functions supplied in RS format the coefficients are computed directly from the RS representation, so the total error is controlled by separately bounding each term and choosing the Tucker ranks to meet the target accuracy on the coefficient tensor. We acknowledge that an explicit bound on the cross term involving the RS rank and separation distance is not provided. We will add a clarifying paragraph in Section 4 stating that the controllable-accuracy claim for RS inputs relies on numerical verification that the Tucker approximation of the coefficient tensor achieves the desired tolerance, and that a sharper analytic bound on the interaction would require additional assumptions on the kernel. This revision will make the error analysis more precise. revision: yes

Circularity Check

0 steps flagged

No circularity; hybrid method combines established techniques with provided estimates

full rationale

The paper proposes a hybrid Chebyshev-Tucker format that applies standard tensor-product Chebyshev interpolation to obtain a moderate-sized coefficient tensor, followed by Tucker-ALS decomposition on that tensor. Error and complexity estimates are derived from the properties of Chebyshev interpolation and Tucker approximation. The low-rank Tucker structure of the coefficient tensor is shown to hold for the electrostatic examples considered, rather than being defined into existence or obtained by fitting a parameter that is then renamed as a prediction. The range-separated (RS) format is used only as an optional input representation for the target function; the core derivation does not reduce to a self-citation chain or to any input quantity by construction. The method remains self-contained against external benchmarks of Chebyshev and Tucker theory.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The approach rests on standard assumptions from approximation theory and tensor decompositions; no new entities are introduced.

free parameters (2)
  • Tucker ranks
    Chosen to achieve target accuracy ε in the decomposition of the Chebyshev coefficient tensor
  • Chebyshev polynomial degrees
    Selected to control interpolation accuracy for the multivariate function
axioms (2)
  • domain assumption Target functions admit accurate tensor-product Chebyshev interpolation from values at a moderate number of nodes
    Underpins the initial evaluation step that avoids full-grid discretization
  • domain assumption The resulting coefficient tensor possesses low Tucker rank relative to the polynomial degrees
    Required for the compression step to yield substantial rank reduction while preserving accuracy

pith-pipeline@v0.9.0 · 5829 in / 1305 out tokens · 92097 ms · 2026-05-23T01:29:35.061594+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Bachmayr,Low-rank tensor methods for partial differential equations, Acta Numer., 32 (2023), pp

    [1]M. Bachmayr,Low-rank tensor methods for partial differential equations, Acta Numer., 32 (2023), pp. 1–121. [2]M. Bachmayr, R. Schneider, and A. Uschmajew,Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations, Found. Comput. Math., 16 (2016), pp. 1423–1472. [3]M. Bebendorf,Adaptive cross approximati...

    work page 2023

  2. [2]

    Benner, V

    [5]P. Benner, V. Khoromskaia, B. Khoromski, C. Kweyu, and S. M.,Regularization of Poisson–Boltzmann type equations with singular source terms using the range-separated tensor format, SIAM J. Sci. Comput., 43 (2021), pp. A415–A445. [6]P. Benner, V. Khoromskaia, and B. N. Khoromskij,Range-separated tensor format for many-particle modeling, SIAM J. Sci. Comp...

    work page 2021

  3. [3]

    Berrut,Rational functions for guaranteed and experimentally well-conditioned global interpolation, Comput

    [9]J.-P. Berrut,Rational functions for guaranteed and experimentally well-conditioned global interpolation, Comput. Math. Appl., 15 (1988), pp. 1–16. [10]J.-P. Berrut and L. N. Trefethen,Barycentric Lagrange interpolation, SIAM Rev., 46 (2004), pp. 501–517. [11]C. Bertoglio and B. N. Khoromskij,Low-rank quadrature-based tensor approximation of the Galerki...

    work page 1988

  4. [4]

    Canc `es and C

    [14]E. Canc `es and C. Le Bris,Mathematical modeling of point defects in materials science, Math. Models Methods Appl. Sci., 23 (2013), pp. 1795–1859. [15]M. Che and Y. Wei,Randomized algorithms for the approximations of Tucker and the tensor train decompositions, Adv. Comput. Math., 45 (2019), pp. 395–428. [16]P. L. Chebyshev,Sur les questions de minima ...

    work page 2013

  5. [5]

    De Lathauwer, B

    [18]L. De Lathauwer, B. De Moor, and J. Vandewalle,A multilinear singular value decom- position, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253–1278. [19]L. De Lathauwer, B. De Moor, and J. Vandewalle,On the best rank-1 and rank- (R1, R2,· · ·, R N)approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324–1342. [20]S. Dolgov,...

    work page 2000

  6. [6]

    Ewald,Die berechnung optische und elektrostatischer gitterpotentiale, Annalen der Physik, 369 (1921), pp

    [23]P. Ewald,Die berechnung optische und elektrostatischer gitterpotentiale, Annalen der Physik, 369 (1921), pp. 253–287. [24]Z. Gao, J. Liang, and Z. Xu,A kernel-independent sum-of-exponentials method, J. Sci. Com- put., 93, 40 (2022). [25]L. Greengard, S. Jiang, and Y. Zhang,The anisotropic truncated kernel method for convolu- tion with free-space Green...

    work page 1921

  7. [7]

    Khoromskaia and B

    [35]V. Khoromskaia and B. N. Khoromskij,Ubiquitous nature of the reduced higher order SVD in tensor-based scientific computing, Front. Appl. Math. Stat., 8:826988 (2022). 26P. BENNER, B. N. KHOROMSKIJ, V. KHOROMSKAIA, B. SUN [36]B. N. Khoromskij,O(dlogN)-quantics approximation ofN-dtensors in high-dimensional numerical modeling, Constr. Approx., 34 (2011)...

    work page 2022

  8. [8]

    [38]B. N. Khoromskij and V. Khoromskaia,Low rank Tucker-type tensor approximation to classical potentials, Cent. Eur. J. Math., 5 (2007), pp. 523–550. [39]B. N. Khoromskij and V. Khoromskaia,Multigrid accelerated tensor approximation of func- tion related multidimensional arrays, SIAM J. Sci. Comput., 31 (2009), pp. 3002–3026. [40]D. Kressner, B. Vanderey...

    work page 2007

  9. [9]

    [48]I. V. Oseledets,Tensor-train decomposition, SIAM J. Sci. Comput., 33 (2011), pp. 2295–2317. [49]I. V. Oseledets, D. V. Savostianov, and E. E. Tyrtyshnikov,Tucker dimensionality re- duction of three-dimensional arrays in linear time, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 939–956. [50]M. V. Rakhuba and I. V. Oseledets,Fast multidimensional convolut...

    work page 2011

  10. [10]

    Str ¨ossner, B

    [54]C. Str ¨ossner, B. Sun, and D. Kressner,Approximation in the extended functional tensor train format, Adv. Comput. Math., 50, 54 (2024). [55]V. Subramanian, S. Das, and V. Gavini,Tucker tensor approach for accelerating Fock Exchange computations in a real-space finite-element discretization of generalized Kohn- Sham density functional theory, J. Chem....

    work page 2024

  11. [11]

    Townsend and L

    [57]A. Townsend and L. N. Trefethen,An extension of Chebfun to two dimensions, SIAM J. Sci. Comput., 35 (2013), pp. C495–C518. [58]A. Townsend and L. N. Trefethen,Continuous analogues of matrix factorizations, Proc. A., 471 (2015), pp. 20140585,

    work page 2013

  12. [12]

    [60]L. R. Tucker,Some mathematical notes on three-mode factor analysis, Psychometrika, 31 (1966), pp. 279–311. [61]H. Yserentant,An iterative method for the solution of Laplace-like equations in high and very high space dimensions, Numer. Math., 156 (2024), pp. 777–811

    work page 1966