Pith. sign in

REVIEW 4 major objections 5 minor 1 cited by

A CUR-based low-rank approximation of the Fourier coefficient matrix can match the accuracy of full two-dimensional Fourier truncation while evaluating only O(I1 S2 + I2 S1) double integrals instead of O(I1 I2).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

The paper presents adaptive CUR-based algorithms that evaluate only a subset of Fourier integrals for 2D hyperinterpolation, but the central error bound is invalid because it confuses max-norm and Frobenius-norm of the coefficient error.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection CUR-for-hyperinterpolation is a sensible idea and the adaptive algorithms are new, but the central L2 error bound rests on a reversed norm inequality, so the advertised guarantee does not hold as stated. the 4 major comments →

arxiv 2510.13204 v2 pith:6CS4RSRO submitted 2025-10-15 math.NA cs.NA

How many integrals should be evaluated at least in two-dimensional hyperinterpolation?

Maolin Che , Congpei An , Yimin Wei , Hong Yan This is my paper
classification math.NA cs.NA MSC 68Q2568R1068U0565D1565F5541A1041A63
keywords hyperinterpolationmatrix CUR decompositiontruncated Fourier serieslow-rank approximationhigh-dimensional approximationadaptive samplingepsilon-rankSobolev spaces
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 tries to show that matrix CUR decomposition can break the curse of dimensionality in two-dimensional Fourier hyperinterpolation. Instead of computing all (2I1+1)(2I2+1) Fourier coefficients, it selects small row and column index sets, computes only the coefficients in those rows and columns plus a small core, and reconstructs an approximation to the full coefficient matrix. The central claim, Theorem 3.3, is that the resulting function has L2 error bounded by C max{I1,I2}^{-alpha}|f|_alpha + epsilon||A||_2 with rank R = O(ln(I1+I2)/epsilon^2), matching the full truncated series asymptotically while needing O(I1 S2 + I2 S1) double integrals. Two adaptive greedy algorithms choose the index sets without ever forming the full coefficient matrix, offering a practical route to high-dimensional spectral approximation from a modest number of integrals.

Core claim

The central claim is that for a continuous bivariate periodic function in the Sobolev space H^alpha, the full Fourier-truncation operator can be replaced by a low-rank CUR approximation of its coefficient matrix A without loss of accuracy. The paper constructs eF f from CUR factors C, U, R selected by index sets T1, T2; the factors are explicitly defined by integrals of f against Fourier modes restricted to those indices. Theorem 3.3 asserts the L2 error of eF f is at most C max{I1,I2}^{-alpha}|f|_alpha + epsilon||A||_2, with rank R = ceil(72 ln(2(I1+I2)+3)/epsilon^2), so the approximation inherits the Sobolev convergence rate of the full truncation and adds a controlled epsilon term. The tw

What carries the argument

The central object is the (2I1+1) x (2I2+1) Fourier coefficient matrix A whose entries are the double integrals alpha_{k1,k2}. The machinery is the CUR decomposition eA = C U R: columns C and rows R are subsets of A's columns and rows indexed by T1 and T2, and U is the Moore-Penrose inverse of the core intersection G = A(T1,...,T2,...). The proof chain uses an epsilon-rank bound (rank R logarithmic in the matrix dimensions and inverse-quadratic in tolerance) to assert that a rank-R approximation exists with max-norm error epsilon||A||_2, converts that matrix error into an L2 function error, and then adds the Sobolev truncation error of Theorem 3.1. The adaptive algorithms select T1 and T2 by

Load-bearing premise

The bound rests on the assertion that the L2 error between the CUR-based function and the truncated Fourier series is at most the maximum absolute entry of the coefficient difference matrix; by Parseval's identity that L2 error is actually the Frobenius norm (square root of the sum of squares), which can be much larger, so the stated guarantee does not follow—and the theorem also uses max{I1,I2} where the cited truncation bound requires min{I1,I2}.

What would settle it

Take an N x N coefficient matrix A and set the CUR error matrix Delta = A - E F* to have every entry equal to 1/sqrt(N). Then ||Delta||_max = 1/sqrt(N) but ||Delta||_F = 1. By Parseval, the L2 error ||eF f - F f||_L2 equals ||Delta||_F = 1, independent of epsilon. With epsilon||A||_2 small this would violate the theorem's bound if such a Delta arose from the CUR construction, making the key inequality directly testable.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If Theorem 3.3 holds, bivariate Fourier hyperinterpolation can achieve the full truncation's asymptotic accuracy with far fewer coefficient integrals, reducing cost from O(I1 I2) to O(I1 S2 + I2 S1).
  • The adaptive index-selection algorithms provide a way to build the approximation without ever forming the entire coefficient matrix, making large truncation orders (I ~ 3000) tractable.
  • Because the rank R grows only logarithmically in I1+I2 for fixed tolerance, storage cost is compressed relative to the full coefficient matrix.
  • The same CUR structure can be combined with sparse tensor-product quadrature to reduce the number of function evaluations as well as double integrals.
  • For functions whose Fourier coefficient matrices are exactly rank-R, the approximation recovers the function's dominant modes exactly, up to quadrature error.

Where Pith is reading between the lines

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

  • A direct test of the framework: apply the two algorithms to a function whose Fourier coefficient matrix is dense with slowly decaying singular values; the rank needed to reach a target L2 error will show whether the logarithmic epsilon-rank bound is realistic or whether the max-norm-to-Frobenius gap forces a larger rank.
  • The same index-selection idea could combine with sparse grids or Monte Carlo quadrature to cut the number of function evaluations, a direction the paper flags as future work.
  • For N > 2 variables, the natural analogue is a tensor CUR or tensor-train decomposition of the coefficient tensor; the paper's two-dimensional machinery is the base case of that extension.
  • If the truncation theorem's min{I1,I2} were restored in place of max{I1,I2}, the error bound would improve; the current bound is conservative in one variable and sharp in the other.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes using matrix CUR decompositions to approximate the truncated bivariate Fourier series of a periodic function, claiming to reduce the number of double integrals from O(I1 I2) to O(I1 S2 + I2 S1). Two strategies are presented: a fixed-size index selection approach and two adaptive greedy algorithms. The central theoretical result, Theorem 3.3, aims to show that a CUR-based approximation attains the same asymptotic L2 accuracy as the full truncated Fourier series, with rank R = O(log(I1+I2)/ε^2). Numerical experiments compare running times and errors against the full truncated Fourier series for three test functions and three tensor-product quadrature rules.

Significance. If Theorem 3.3 were correct, the paper would offer a meaningful bridge between matrix CUR decompositions and function approximation, with a concrete asymptotic guarantee and a clear reduction in the number of integrals. The availability of shared MATLAB code and the systematic comparison across quadrature rules are positive features. However, the central error bound is mathematically unsound: the proof of Theorem 3.3 relies on a reversed norm inequality, and the statement strengthens the truncation term from min to max without justification. Since the advertised equivalence with full truncated Fourier series rests entirely on this bound, the core contribution is not established. The adaptive algorithms have no supporting error analysis, and the numerical results cannot compensate for the invalid theory.

major comments (4)
  1. [§3.1, proof of Theorem 3.3] The proof asserts ||Ṽf − Ff||_{L2} ≤ ||A−EF*||_max. This inequality has the wrong direction. With the paper's normalization the exponentials e^{i(k1x1+k2x2)} are orthonormal in L2(H⁰₂), so by Parseval ||Ṽf − Ff||_{L2} = ||A−EF*||_F. Since ||A−EF*||_F ≥ ||A−EF*||_max, the max-norm bound from Theorem 3.2 does not control the L2 error. The best immediate bound would introduce a factor √((2I1+1)(2I2+1)), destroying the claimed asymptotic equivalence with the full truncation. This invalidates the paper's central theorem.
  2. [§3.1, Theorem 3.3] The statement replaces the min{I1,I2}^{−α} truncation error of Theorem 3.1 with max{I1,I2}^{−α} without any proof or justification. This is a strengthening of the bound in the wrong direction: max{I1,I2}^{−α} can be much larger than min{I1,I2}^{−α}, and no argument is given for why the larger exponent should hold. The error term in Theorem 3.3 is therefore not supported by the cited Theorem 3.1.
  3. [§4.1, Corollary 4.1] Corollary 4.1 inherits the same two defects as Theorem 3.3. Theorem 4.1 bounds the max norm of the CUR error, but the L2 error of the approximating function requires the Frobenius norm of the coefficient error, and the two are not comparable in the direction needed. The corollary also uses max{I1,I2}^{−α}. As a result, the claimed L2 error bound is unsupported.
  4. [§4.2, Algorithms 1 and 2] No theoretical error bound is proven for the adaptive stopping criteria. The conditions involving σ_min(C), σ_min(R), and σ_min(G) are not connected to either ||CUR − A||_max or ||Ṽf − f||_{L2}; they merely indicate numerical rank deficiency of the sampled blocks. The numerical experiments tune (b1,b2) and τ per test function, so they cannot validate a general guarantee. The paper's conclusion that adaptive algorithms provide controllable accuracy is therefore not justified by the analysis.
minor comments (5)
  1. [§3, Definition of L2(H⁰₂)] The definition states that f ∈ L2(H⁰₂) if ∑ |f̂(k1,k2)| < ∞. This is an ℓ1 condition, not the L2 condition; the correct condition is ∑ |f̂|² < ∞. This affects the stated Hilbert space setup.
  2. [§5, paragraph after Eq. (1)] In the numerical setup the text says 'F f(x1,x2) in (4) is the truncated Fourier series expression,' but the truncated series is defined in Eq. (1), not (4). This typo makes the description confusing.
  3. [§5.3, Table 3] The text concludes that Algorithms 1 and 2 are faster than Truncated Fourier for all cases. Table 3 shows a counterexample: for f3 with CC, Algorithm 1 takes 14.7140 seconds versus 12.1434 for Truncated Fourier. The claim should be qualified.
  4. [§5.2, parameter choice] The paper sets M1 = M2 = 5001 for all quadrature rules but does not analyze the quadrature error or its interaction with the claimed error bounds. Since integrals in (5)–(7) are only approximated, a complete error analysis should include this term.
  5. [Appendix C, text] The sentence 'We now compare the efficiencies of Algorithms 2 and C.1 via three test functions f1(x1,x2), f3(x1,x2) and f3(x1,x2)' appears to contain a typo; f3 is listed twice, likely one occurrence should be f2.

Circularity Check

0 steps flagged

No significant circularity: the central error bound is assembled from independent external theorems, and the tuned numerical parameters do not enter the theoretical result.

full rationale

The paper's central claim, Theorem 3.3, is an additive combination of an external Sobolev truncation estimate (Theorem 3.1, citing Canuto et al.) and an external max-norm low-rank matrix approximation bound (Theorem 3.2, citing Udell and Townsend). The CUR factors E and F are taken from the matrix approximation guaranteed by the latter, so the claimed error is not defined in terms of the quantity being predicted. Corollary 4.1 similarly imports the Osinsky–Zamarashkin maximal-volume bound rather than relying on a conclusion supplied by the paper itself. No fitted parameter appears in these theoretical bounds: the block sizes (b1,b2) and tolerance tau are chosen empirically in Section 5.2, and they do not enter Theorem 3.3 or Corollary 4.1. Thus this is parameter tuning, not a fitted input repackaged as a prediction. The self-citations ([3,4,5,17,18]) occur in literature surveys and algorithmic remarks, not as load-bearing justification of the main result, and no uniqueness theorem or ansatz is imported from the authors' own prior work. I note that the proof of Theorem 3.3 appears to contain a norm inequality with the wrong direction: by Parseval, the L2 error of a Fourier polynomial equals the Frobenius norm of the coefficient difference, not the max norm, and Theorem 3.3 states max{I1,I2}^{-alpha} where Theorem 3.1 has min{I1,I2}^{-alpha}. These are correctness/validity concerns and are not instances of circular reasoning under the criteria used here.

Axiom & Free-Parameter Ledger

4 free parameters · 6 axioms · 0 invented entities

The paper introduces no new physical or mathematical entities. It relies on standard theorems plus heuristic algorithmic assumptions. The main hidden assumptions are that the Fourier coefficient matrix is low-rank and that the adaptive stopping criterion ensures accuracy—both unproven.

free parameters (4)
  • block sizes (b1,b2) = e.g., (4,4), (6,6), (14,14) depending on test function and quadrature; selected in §5.2
    Block sizes for the adaptive algorithms; chosen by scanning Table 1 and Figs. 1-3, no a priori rule.
  • tolerance τ = 1e-5
    Tolerance for the stopping criterion; chosen by scanning Table 2; no theoretical link to final approximation error.
  • quadrature node counts M1, M2 = 5001 each
    Set arbitrarily in §5; no convergence or error analysis is provided for the quadrature.
  • smoothness α, constant C, seminorm |f|_α, target ε = α=2, C=1, |f|_α=1, ε=1e-7
    Hand-chosen in §5 to set (I1,I2)=(3163,3163) via Theorem 3.1; the true constants are unknown, so the truncation indices are artificial.
axioms (6)
  • standard math Parseval identity equates L2 norm of a Fourier polynomial to the ℓ2 norm of its coefficients
    This is standard, but the paper's proof of Theorem 3.3 contradicts it by bounding L2 error by max-norm.
  • standard math Truncated Fourier series error bound of Theorem 3.1 (from [15])
    Used as the baseline truncation error; the paper modifies min to max in Theorem 3.3.
  • standard math Low-rank approximation bound of Theorem 3.2 (from [71]) in max norm
    Used to derive rank R; however the L2 transfer would require a Frobenius-norm bound, which is not provided.
  • domain assumption Maximal volume index selection error bound (from [54])
    Theorem 4.1 requires G to have maximal volume among all S1×S2 submatrices; the adaptive algorithms do not enforce or verify this, so Corollary 4.1 does not apply to the implemented methods.
  • domain assumption Coefficient matrix A is approximately low-rank with small S1,S2
    The claimed efficiency gain depends on the decay of the singular values of the Fourier coefficient matrix; this is demonstrated only empirically for three test functions, not established theoretically.
  • ad hoc to paper Quadrature error from tensor-product rules with M1=M2=5001 is negligible
    The algorithms compute coefficients via quadrature, but no error analysis or convergence study for the quadrature is given; the paper sets M1=M2=5001 'for clarity' in §5.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of How many integrals should be evaluated at least in two-dimensional hyperinterpolation?." pith.science (2026). https://pith.science/paper/6CS4RSRO

@misc{pith2026251013204,
  author       = {Pith},
  title        = {Pith review of: How many integrals should be evaluated at least in two-dimensional hyperinterpolation?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6CS4RSRO}},
  note         = {Machine review of arXiv:2510.13204}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

This paper introduces a novel approach to approximating continuous functions over high-dimensional hypercubes by integrating matrix CUR decomposition with hyperinterpolation techniques. Traditional Fourier-based hyperinterpolation methods suffer from the curse of dimensionality, as the number of coefficients grows exponentially with the dimension. To address this challenge, we propose two efficient strategies for constructing low-rank matrix CUR decompositions of the coefficient matrix, significantly reducing computational complexity while preserving accuracy. The first method employs structured index selection to form a compressed representation of the tensor, while the second utilizes adaptive sampling to further optimize storage and computation. Theoretical error bounds are derived for both approaches, ensuring rigorous control over approximation quality. Additionally, practical algorithms -- including randomized and adaptive decomposition techniques -- are developed to efficiently compute the CUR decomposition. Numerical experiments demonstrate the effectiveness of our methods in drastically reducing the number of required coefficients without compromising precision. Our results bridge matrix/tensor decomposition and function approximation, offering a scalable solution for high-dimensional problems. This work advances the field of numerical analysis by providing a computationally efficient framework for hyperinterpolation, with potential applications in scientific computing, machine learning, and data-driven modeling.

Figures

Figures reproduced from arXiv: 2510.13204 by Congpei An, Hong Yan, Maolin Che, Yimin Wei.

Figure 1
Figure 1. Figure 1: When setting τ = 1e − 5, with different pairs (b1, b2), the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Newton-Cotes quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 18 [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: When setting τ = 1e−5, with different pairs (b1, b2), the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Clenshaw-Curtis quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 19 [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: When setting τ = 1e−5, with different pairs (b1, b2), the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Gauss-Legendre quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 20 [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: For the special choice of (b1, b2), with different τ , the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Newton-Cotes quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 21 [PITH_FULL_IMAGE:figures/full_fig_p021_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: For the special choice of (b1, b2), with different τ , the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Clenshaw-Curtis quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 22 [PITH_FULL_IMAGE:figures/full_fig_p022_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: For the special choice of (b1, b2), with different τ , the values of e(x1, x2) obtained by applying Algorithm 2 with the tensor-product Gauss-Legendre quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 23 [PITH_FULL_IMAGE:figures/full_fig_p023_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: For the special choice of (b1, b2) and τ = 1e − 5, the values of the truncated Fourier series expression and its approximation, and the associated error function obtained by applying Algorithms 1 and 2 with the tensor-product Newton-Cotes quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 25 [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: For the special choice of (b1, b2) and τ = 1e − 5, the values of the truncated Fourier series expression and its approximation, and the associated error function obtained by applying Algorithms 1 and 2 with the tensor-product Clenshaw-Curtis quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 26 [PITH_FULL_IMAGE:figures/full_fig_p026_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: For the special choice of (b1, b2) and τ = 1e − 5, the values of the truncated Fourier series expression and its approximation, and the associated error function obtained by applying Algorithms 1 and 2 with the tensor-product Gauss-Legendre quadrature to the test functions f1(x1, x2), f2(x1, x2) and f3(x1, x2). 27 [PITH_FULL_IMAGE:figures/full_fig_p027_9.png] view at source ↗

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation

    math.NA 2026-07 reject novelty 5.0

    The paper asserts low-epsilon-Tucker-rank compressibility of hyperinterpolation coefficient tensors and gives unified TCUR error bounds, but the central rank formula exceeds the tensor dimensions and the advertised pr...

Reference graph

Works this paper leans on

79 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    Ailon and B

    N. Ailon and B. Chazelle , The fast J ohnson-- L indenstrauss transform and approximate nearest neighbors , SIAM Journal on Computing, 39 (2009), pp. 302--322

    2009

  2. [2]

    An and J

    C. An and J. Ran , Hard thresholding hyperinterpolation over general regions , J. Sci. Comput., 102 (2025), pp. 26, Paper No. 37

    2025

  3. [3]

    An and H.-N

    C. An and H.-N. Wu , Lasso hyperinterpolation over general regions , SIAM Journal on Scientific Computing, 43 (2021), pp. A3967--A3991

    2021

  4. [4]

    1899--1919

    height 2pt depth -1.6pt width 23pt, On the quadrature exactness in hyperinterpolation , BIT Numerical Mathematics, 62 (2022), pp. 1899--1919

    2022

  5. [5]

    height 2pt depth -1.6pt width 23pt, Bypassing the quadrature exactness assumption of hyperinterpolation on the sphere , Journal of Complexity, 80 (2024), p. 101789

    2024

  6. [6]

    Bamberger, F

    S. Bamberger, F. Krahmer, and R. Ward , J ohnson-- L indenstrauss embeddings with K ronecker structure , SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 1806--1850

    2022

  7. [7]

    Bartel, A

    F. Bartel, A. D. Gilbert, F. Y. Kuo, and I. H. Sloan , Minimal subsampled rank-1 lattices for multivariate approximation with optimal convergence rate , arXiv preprint arXiv:2506.07729, (2025)

    arXiv 2025

  8. [8]

    Bebendorf , Approximation of boundary element matrices , Numerische Mathematik, 86 (2000), pp

    M. Bebendorf , Approximation of boundary element matrices , Numerische Mathematik, 86 (2000), pp. 565--589

    2000

  9. [9]

    Beckermann and A

    B. Beckermann and A. Townsend , Bounds on the singular values of matrices with displacement structure , SIAM Review, 61 (2019), pp. 319--344

    2019

  10. [10]

    Bigoni, A

    D. Bigoni, A. P. Engsig-Karup, and Y. M. Marzouk , Spectral tensor-train decomposition , SIAM Journal on Scientific Computing, 38 (2016), pp. A2405--A2439

    2016

  11. [11]

    E. K. Bjarkason , Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views , SIAM Journal on Scientific Computing, 41 (2019), pp. A2355--A2383

    2019

  12. [12]

    Boutsidis, P

    C. Boutsidis, P. Drineas, and M. Magdon-Ismail , Near-optimal column-based matrix reconstruction , SIAM Journal on Computing, 43 (2014), pp. 687--717

    2014

  13. [13]

    Boutsidis and A

    C. Boutsidis and A. Gittens , Improved matrix algorithms via the subsampled randomized H adamard transform , SIAM Journal on Matrix Analysis and Applications, 34 (2013), pp. 1301--1340

    2013

  14. [14]

    Boutsidis and D

    C. Boutsidis and D. P. Woodruff , Optimal CUR matrix decompositions , SIAM Journal on Computing, 46 (2017), pp. 543--589

    2017

  15. [15]

    Canuto, M

    C. Canuto, M. Hussaini, A. Quarteroni, and T. Zang , S pectral M ethods: F undamentals in S ingle D omains , Springer, Berlin, 2006

    2006

  16. [16]

    Chaturantabut and D

    S. Chaturantabut and D. C. Sorensen , Nonlinear model reduction via discrete empirical interpolation , SIAM Journal on Scientific Computing, 32 (2010), pp. 2737--2764

    2010

  17. [17]

    Che and Y

    M. Che and Y. Wei , Randomized algorithms for the approximations of T ucker and the tensor train decompositions , Advances in Computational Mathematics, 45 (2019), pp. 395--428

    2019

  18. [18]

    M. Che, Y. Wei, and H. Yan , Efficient randomized algorithms for fixed precision problem of approximate tucker decomposition , SIAM Journal on Matrix Analysis and Applications, 46 (2025), pp. 256--297

    2025

  19. [19]

    Chen and R

    K. Chen and R. Jin , Tensor-structured sketching for constrained least squares , SIAM Journal on Matrix Analysis and Applications, 42 (2021), pp. 1703--1731

    2021

  20. [20]

    K. Chen, Q. Li, K. Newton, and S. J. Wright , Structured random sketching for PDE inverse problems , SIAM Journal on Matrix Analysis and Applications, 41 (2020), pp. 1742--1770

    2020

  21. [21]

    Chiu and L

    J. Chiu and L. Demanet , Sublinear randomized algorithms for skeleton decompositions , SIAM Journal on Matrix Analysis and Applications, 34 (2013), pp. 1361--1383

    2013

  22. [22]

    K. L. Clarkson and D. P. Woodruff , Numerical linear algebra in the streaming model , in Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, pp. 205--214

    2009

  23. [23]

    height 2pt depth -1.6pt width 23pt, Low-rank approximation and regression in input sparsity time , Journal of the ACM (JACM), 63 (2017), pp. 1--45

    2017

  24. [24]

    Cortinovis and D

    A. Cortinovis and D. Kressner , Low-rank approximation in the F robenius norm by column and row subset selection , SIAM Journal on Matrix Analysis and Applications, 41 (2020), pp. 1651--1673

    2020

  25. [25]

    Dai , On generalized hyperinterpolation on the sphere , Proceedings of the American Mathematical Society, 134 (2006), pp

    F. Dai , On generalized hyperinterpolation on the sphere , Proceedings of the American Mathematical Society, 134 (2006), pp. 2931--2941

    2006

  26. [26]

    Derezinski and M

    M. Derezinski and M. W. Mahoney , Determinantal point processes in randomized numerical linear algebra , Notices of the American Mathematical Society, 68 (2021), pp. 34--45

    2021

  27. [27]

    H. Diao, Z. Song, W. Sun, and D. Woodruff , Sketching for K ronecker product regression and p-splines , in International Conference on Artificial Intelligence and Statistics, PMLR, 2018, pp. 1299--1308

    2018

  28. [28]

    Dolgov, D

    S. Dolgov, D. Kressner, and C. Str\" o ssner , Functional T ucker approximation using C hebyshev interpolation , SIAM Journal on Scientific Computing, 43 (2021), pp. A2190--A2210

    2021

  29. [29]

    Drineas, M

    P. Drineas, M. W. Mahoney, and S. Muthukrishnan , Relative-error CUR matrix decompositions , SIAM Journal on Matrix Analysis and Applications, 30 (2008), pp. 844--881

    2008

  30. [30]

    J. A. Duersch and M. Gu , Randomized projection for rank-revealing matrix factorizations and low-rank approximations , SIAM Review, 62 (2020), pp. 661--682

    2020

  31. [31]

    Foucart and H

    S. Foucart and H. Rauhut , A M athematical I ntroduction to C ompressive S ensing , Applied and Numerical Harmonic Analysis, Birkh \"a user New York, NY, 1 ed., 2013

    2013

  32. [32]

    P. Y. Gidisu and M. E. Hochstenbach , A hybrid DEIM and leverage scores based method for CUR index selection , in European Consortium for Mathematics in Industry, Springer, 2021, pp. 147--153

    2021

  33. [33]

    Golub and C

    G. Golub and C. Van Loan , Matrix C omputations , Johns Hopkins University Press, Baltimore, MD, fourth ed., 2013

    2013

  34. [34]

    S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin , A theory of pseudoskeleton approximations , Linear Algebra and its Applications, 261 (1997), pp. 1--21

    1997

  35. [35]

    Griebel and H

    M. Griebel and H. Harbrecht , Analysis of tensor approximation schemes for continuous functions , Foundations of Computational Mathematics, 23 (2023), pp. 219--240

    2023

  36. [36]

    Griebel, H

    M. Griebel, H. Harbrecht, and R. Schneider , Low-rank approximation of continuous functions in S obolev spaces with dominating mixed smoothness , Mathematics of Computation, 92 (2023), pp. 1729--1746

    2023

  37. [37]

    Gu and S

    M. Gu and S. C. Eisenstat , Efficient algorithms for computing a strong rank-revealing QR factorization , SIAM Journal on Scientific Computing, 17 (1996), pp. 848--869

    1996

  38. [38]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, Y. Shkolnisky, and M. Tygert , An algorithm for the principal component analysis of large data sets , SIAM Journal on Scientific computing, 33 (2011), pp. 2580--2594

    2011

  39. [39]

    Halko, P.-G

    N. Halko, P.-G. Martinsson, and J. A. Tropp , Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions , SIAM Review, 53 (2011), pp. 217--288

    2011

  40. [40]

    Hallman , A block bidiagonalization method for fixed-accuracy low-rank matrix approximation , SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp

    E. Hallman , A block bidiagonalization method for fixed-accuracy low-rank matrix approximation , SIAM Journal on Matrix Analysis and Applications, 43 (2022), pp. 661--680

    2022

  41. [41]

    Hamm and L

    K. Hamm and L. Huang , Perturbations of CUR decompositions , SIAM Journal on Matrix Analysis and Applications, 42 (2021), pp. 351--375

    2021

  42. [42]

    Harbrecht, M

    H. Harbrecht, M. Peters, and R. Schneider , On the low-rank approximation by the pivoted C holesky decomposition , Applied Numerical Mathematics, 62 (2012), pp. 428--440

    2012

  43. [43]

    Hashemi and L

    B. Hashemi and L. N. Trefethen , Chebfun in three dimensions , SIAM Journal on Scientific Computing, 39 (2017), pp. C341--C363

    2017

  44. [44]

    R. Jin, T. G. Kolda, and R. Ward , Faster J ohnson-- L indenstrauss transforms with K ronecker products , Information and Inference: A Journal of the IMA, 10 (2021), pp. 1533--1562

    2021

  45. [45]

    T. G. Kolda and B. W. Bader , Tensor decompositions and applications , SIAM review, 51 (2009), pp. 455--500

    2009

  46. [46]

    Le Gia and I

    T. Le Gia and I. Sloan , The uniform norm of hyperinterpolation on the unit sphere in an arbitrary number of dimensions , Constructive approximation, 17 (2001), pp. 249--265

    2001

  47. [47]

    S.-B. Lin, Y. G. Wang, and D.-X. Zhou , Distributed filtered hyperinterpolation for noisy data on the sphere , SIAM Journal on Numerical Analysis, 59 (2021), pp. 634--659

    2021

  48. [48]

    M. W. Mahoney and P. Drineas , CUR matrix decompositions for improved data analysis , Proceedings of the National Academy of Sciences, 106 (2009), pp. 697--702

    2009

  49. [49]

    Martinsson and S

    P.-G. Martinsson and S. Voronin , A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices , SIAM Journal on Scientific Computing, 38 (2016), pp. S485--S507

    2016

  50. [50]

    J. C. Mason , Near-best multivariate approximation by F ourier series, C hebyshev series and C hebyshev interpolation , Journal of Approximation Theory, 28 (1980), pp. 349--358

    1980

  51. [51]

    Meier and Y

    M. Meier and Y. Nakatsukasa , Fast randomized numerical rank estimation for numerically low-rank matrices , Linear Algebra and its Applications, 686 (2024), pp. 1--32

    2024

  52. [52]

    Musco and C

    C. Musco and C. Musco , Randomized block K rylov methods for stronger and faster approximate singular value decomposition , Advances in neural information processing systems, 28 (2015)

    2015

  53. [53]

    I. V. Oseledets , Tensor-train decomposition , SIAM Journal on Scientific Computing, 33 (2011), pp. 2295--2317

    2011

  54. [54]

    Osinsky and N

    A. Osinsky and N. L. Zamarashkin , Pseudo-skeleton approximations with better accuracy estimates , Linear Algebra and its Applications, 537 (2018), pp. 221--249

    2018

  55. [55]

    Pagh , Compressed matrix multiplication , ACM Transactions on Computation Theory (TOCT), 5 (2013), pp

    R. Pagh , Compressed matrix multiplication , ACM Transactions on Computation Theory (TOCT), 5 (2013), pp. 1--17

    2013

  56. [56]

    Park and Y

    T. Park and Y. Nakatsukasa , Accuracy and stability of CUR decompositions with oversampling , SIAM Journal on Matrix Analysis and Applications, 46 (2025), pp. 780--810

    2025

  57. [57]

    Reimer , Multivariate P olynomial A pproximation , vol

    M. Reimer , Multivariate P olynomial A pproximation , vol. 144, Birkh \"a user, 2012

    2012

  58. [58]

    Rokhlin, A

    V. Rokhlin, A. Szlam, and M. Tygert , A randomized algorithm for principal component analysis , SIAM Journal on Matrix Analysis and Applications, 31 (2010), pp. 1100--1124

    2010

  59. [59]

    A. K. Saibaba, R. Minster, and M. E. Kilmer , Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions , Advances in Computational Mathematics, 48 (2022). artile no. 66

    2022

  60. [60]

    Shin and D

    Y. Shin and D. Xiu , A randomized algorithm for multivariate function approximation , SIAM Journal on Scientific Computing, 39 (2017), pp. A983--A1002

    2017

  61. [61]

    I. H. Sloan , Polynomial interpolation and hyperinterpolation over general regions , Journal of Approximation Theory, 83 (1995), pp. 238--254

    1995

  62. [62]

    Sobczyk and E

    A. Sobczyk and E. Gallopoulos , P ylspack: P arallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores , ACM Transactions on Mathematical Software, 48 (2022), pp. 1--27

    2022

  63. [63]

    M. B. Soley, P. Bergold, A. A. Gorodetsky, and V. S. Batista , Functional tensor-train C hebyshev method for multidimensional quantum dynamics simulations , Journal of C hemical T heory and C omputation, 18 (2021), pp. 25--36

    2021

  64. [64]

    D. C. Sorensen and M. Embree , A DEIM induced CUR factorization , SIAM Journal on Scientific Computing, 38 (2016), pp. A1454--A1482

    2016

  65. [65]

    G. W. Stewart , On the early history of the singular value decomposition , SIAM Review, 35 (1993), pp. 551--566

    1993

  66. [66]

    L. N. Trefethen , Cubature, approximation, and isotropy in the hypercube , SIAM Review, 59 (2017), pp. 469--491

    2017

  67. [67]

    L. N. Trefethen , Multivariate polynomial approximation in the hypercube , Proceedings of the American Mathematical Society, 145 (2017), pp. 4837--4844

    2017

  68. [68]

    height 2pt depth -1.6pt width 23pt, Approximation T heory and A pproximation P ractice , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019

    2019

  69. [69]

    J. A. Tropp and R. J. Webber , Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications , arXiv preprint arXiv:2306.12418, (2023)

    Pith/arXiv arXiv 2023

  70. [70]

    J. A. Tropp, A. Yurtsever, M. Udell, and V. Cevher , Practical sketching algorithms for low-rank matrix approximation , SIAM Journal on Matrix Analysis and Applications, 38 (2017), pp. 1454--1485

    2017

  71. [71]

    Udell and A

    M. Udell and A. Townsend , Why are big data matrices approximately low rank? , SIAM Journal on Mathematics of Data Science, 1 (2019), pp. 144--160

    2019

  72. [72]

    Voronin and P.-G

    S. Voronin and P.-G. Martinsson , Efficient algorithms for CUR and interpolative matrix decompositions , Advances in Computational Mathematics, 43 (2017), pp. 495--516

    2017

  73. [73]

    Wade , On hyperinterpolation on the unit ball , Journal of Mathematical Analysis and Applications, 401 (2013), pp

    J. Wade , On hyperinterpolation on the unit ball , Journal of Mathematical Analysis and Applications, 401 (2013), pp. 140--145

    2013

  74. [74]

    Y. G. Wang, Q. T. Le Gia, I. H. Sloan, and R. S. Womersley , Fully discrete needlet approximation on the sphere , Applied and Computational Harmonic Analysis, 43 (2017), pp. 292--316

    2017

  75. [75]

    D. P. Woodruff et al. , Sketching as a tool for numerical linear algebra , Foundations and Trends in Theoretical Computer Science, 10 (2014), pp. 1--157

    2014

  76. [76]

    Woolfe, E

    F. Woolfe, E. Liberty, V. Rokhlin, and M. Tygert , A fast randomized algorithm for the approximation of matrices , Applied and Computational Harmonic Analysis, 25 (2008), pp. 335--366

    2008

  77. [77]

    K. Wu, Y. Shin, and D. Xiu , A randomized tensor quadrature method for high dimensional polynomial approximation , SIAM Journal on Scientific Computing, 39 (2017), pp. A1811--A1833

    2017

  78. [78]

    Xia , Making the N ystr \"o m method highly accurate for low rank approximations , SIAM Journal on Scientific Computing, 46 (2024), pp

    J. Xia , Making the N ystr \"o m method highly accurate for low rank approximations , SIAM Journal on Scientific Computing, 46 (2024), pp. A1076--A1101

    2024

  79. [79]

    W. Yu, Y. Gu, and Y. Li , Efficient randomized algorithms for the fixed-precision low-rank matrix approximation , SIAM Journal on Matrix Analysis and Applications, 39 (2018), pp. 1339--1359

    2018

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.