Pith. sign in

REVIEW 4 major objections 4 minor 152 references

Hyperinterpolation coefficient tensors are intrinsically low-rank: per-mode Tucker ranks need only grow logarithmically with tensor size, with entrywise error bounds nearly independent of dimension.

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 ↗

T0 review · deepseek-v4-flash

2026-08-01 11:50 UTC pith:PZQR4GN3

load-bearing objection The advertised low-epsilon-Tucker-rank theorem is vacuous in the regime the paper tests; the unified TCUR error formula is a useful synthesis, but the central compressibility claim is not established. the 4 major comments →

arxiv 2607.19741 v2 pith:PZQR4GN3 submitted 2026-07-22 math.NA cs.NA

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

Maolin Che , Yimin Wei , Chong Wu This is my paper
classification math.NA cs.NA MSC 41A1041A6365D1565F5568Q2568R1068U05
keywords hyperinterpolationtensor CUR decompositionTucker decompositionlow-rank tensor approximationcurse of dimensionalitygreedy adaptive algorithmsepsilon-rankhigh-dimensional approximation
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 paper tries to establish that the coefficient tensors produced by high-dimensional hyperinterpolation are intrinsically compressible: for any prescribed tolerance epsilon, a Tucker-format tensor exists that approximates the coefficient array to entrywise accuracy with per-mode ranks that scale logarithmically, not exponentially, with polynomial degrees and dimension. If true, this removes the curse-of-dimensionality bottleneck that forces practitioners to assemble the full coefficient tensor, and makes tensor-free hyperinterpolation—where only a few adaptively chosen cubature inner products are evaluated—theoretically sound. The paper unifies the two dominant tensor CUR variants under one error-analysis framework and gives greedy algorithms with stopping criteria certified by the theory. A sympathetic reader would care because the claims convert hyperinterpolation from an algorithm that cannot scale past moderate dimension into one whose cost is set by the intrinsic multilinear complexity of the function being approximated.

Core claim

Theorem 4.1 is the central object: for every hyperinterpolation coefficient tensor A and every 0<epsilon<1, there is a Tucker-format tensor B with ||A-B||_max <= epsilon (a^N-1)/(a-1) ||A||_F, where a=1+epsilon sqrt(prod_n(I_n+1)), and per-mode ranks R_n = ceil(72 ln((I_n+1)+prod_{k<n}R_k prod_{l>n}(I_l+1)+1)/epsilon^2). Since these ranks enter only logarithmically, the theorem asserts intrinsic low-epsilon-Tucker-rank structure. The paper then derives unified Frobenius-norm error bounds for Chidori- and Fiber-type tensor CUR decompositions, proves convergence and stability of greedy adaptive index selection, and composes the whole chain—Sobolev regularity, hyperinterpolation discretization,

What carries the argument

The theory extends matrix epsilon-rank to tensors by recursive mode-wise approximation: at each mode, a matrix epsilon-rank theorem supplies a low-rank factor, and the singular spectra of mode unfoldings plus the volumes of selected index submatrices control all error constants. The unified TCUR factorization A_TCUR = G x_1(C_1 U_1^dagger) ... x_N(C_N U_N^dagger) is the working object; the pseudoinverse norms ||W^dagger_{n,R_n,I_n}|| and ||V^dagger_{n,R_n,J_n}|| measure how well the chosen indices capture the dominant subspaces. The greedy index-selection algorithms are designed to approximate maximum-volume submatrices of the SVD factors, which keeps these norms bounded and makes the error

Load-bearing premise

The algorithmic guarantees rest on the unproved assertion that greedily expanding index blocks in fixed order approximates maximum-volume submatrices of the mode-n singular factor matrices; if that fails, the certified stopping criteria and volume-based stability constants in the error bounds no longer follow.

What would settle it

Compute the rank bound of Theorem 4.1 at the paper's own test setting (I_n=20, epsilon=0.01): if the resulting R_n exceeds I_n+1=21, the claimed compression (per-mode rank below the full tensor size) fails in the regime where the experiments are run. Alternatively, on a small tensor, compare the greedy index selection to the true maximum-volume submatrix and check whether the pseudoinverse norms satisfy the bounds of Remark 4.10.

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

If this is right

  • Practitioners could estimate required Tucker ranks before computing any hyperinterpolation coefficient, turning compression from a post-hoc step into an a priori resource calculation.
  • A fully tensor-free hyperinterpolation workflow becomes possible: only the selected cubature inner products need evaluation, not the full coefficient array.
  • Both Chidori-type and Fiber-type TCUR share one error formula, so implementations can switch between them without re-deriving guarantees.
  • The single end-to-end error chain lets users allocate error budgets across polynomial degree, index sampling, and final Tucker truncation.
  • The greedy algorithms come with certified stopping criteria, removing the need for heuristic iteration counts.

Where Pith is reading between the lines

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

  • If the theorem generalizes, other spectral approximation methods whose coefficient arrays arise from tensor-product inner products may inherit the same intrinsic low-rank structure, not only hyperinterpolation.
  • A testable extension is to check whether the rank bounds remain logarithmic when the cubature rule or the domain changes (spheres, balls), which the authors list as future work.
  • The greedy selection's near-maximum-volume property could be verified empirically by comparing selected index sets to true maximum-volume submatrices on small tensors; if the comparison holds, the stability constants in the error bounds become certifiable.

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 / 4 minor

Summary. The paper claims to establish a rigorous theory of intrinsic low-ε-Tucker-rank for hyperinterpolation coefficient tensors, unified Chidori- and Fiber-type tensor CUR (TCUR) decompositions, provable near-optimal greedy index selection, and an end-to-end error chain with tensor-free workflows. The central theoretical result is Theorem 4.1, which asserts that every hyperinterpolation coefficient tensor admits a Tucker approximation with entrywise error tolerance ε and per-mode ranks R_n = ⌈72 ln((I_n+1)+∏_{k<n}R_k∏_{l>n}(I_l+1)+1)/ε²⌉. Algorithms 5.1–5.4 implement greedy adaptive index selection, and Appendix A provides a TCUR-to-Tucker recompression pipeline. Numerical experiments on three 3D test functions are presented as validation.

Significance. If Theorem 4.1 were correct and non-vacuous, it would provide a valuable a priori tool for estimating compression ranks in high-dimensional hyperinterpolation without constructing the full coefficient tensor. The unified treatment of two TCUR variants, the explicit error decomposition in Theorem 4.4, and the recompression pipeline in Appendix A are useful organizational contributions. The authors also provide a public GitHub repository with code for their experiments, which aids reproducibility. However, the central existence theorem is vacuous in the parameter regimes used in the paper's own experiments: its rank bound exceeds the mode dimension, so it cannot certify low-rank compressibility. The algorithmic near-optimality claim is asserted without proof, and the 'tight' bound in Theorem 4.4 is numerically many orders of magnitude loose. These issues undermine the paper's main claims, so the significance of the contribution as it stands is limited.

major comments (4)
  1. [Section 4.2, Theorem 4.1 and Remark 4.1(c)] The rank formula in Theorem 4.1 is vacuous in the tested regime. For N=3, I_n=20, ε=0.01, the formula gives R_1 = ⌈72 ln(21+441+1)/10⁻⁴⌉ ≈ 4.42×10⁶, which exceeds the mode dimension 21; the same happens recursively for R_2 and R_3. Since any tensor with mode size 21 has mode-1 rank ≤21, the bound is automatically satisfied by all tensors and does not establish intrinsic low-rank structure. Remark 4.1(c), which claims R_n < I_n+1 'always holds' as I_n grows, is only true for astronomically large I (for ε=0.01, around I≈2.4×10⁷), far outside the practical regime claimed in the paper. This is a load-bearing flaw: Theorem 4.1 is the paper's main existence result and the stated basis for a priori rank estimation.
  2. [Section 5, bullet (a) and Remark 4.10] The paper asserts that 'the incremental index selection process approximates maximum-volume submatrices of the mode-n singular factor matrices W_{n,R_n} and V_{n,R_n}, satisfying the volume-based pseudoinverse norm bounds in Remark 4.10.' This is never proved. The stopping criteria in Algorithms 5.1–5.4 are based on singular-value ratios of C_n or G(n), not on any measure of volume or on closeness to maximum-volume submatrices. Without a proof connecting the greedy selection to the volume bounds, the stability constants and certified error bounds of Theorem 4.4 and Theorem 4.5 do not apply to the algorithms. The near-optimality claim is therefore unsupported.
  3. [Section 6.4, Tables 6–8; Theorem 4.4] Theorem 4.4 is introduced as a 'tight and computable upper bound', but the numerical experiments show that the bound E_th exceeds the exact error by factors of 10⁷ to 10¹¹ (Tables 6–8, e.g., E_th/E_exact = 1.168×10¹¹ for Algorithm 5.1 with b=2). The tighter bound E_tight from Remark 4.9 is within a factor of ~1–4 of the exact error, but that bound is not the one stated as Theorem 4.4. The abstract's claim of 'tight' Frobenius-norm estimates is therefore not supported by the theorem as presented; the theoretical bound is too loose to be used for a priori error budgeting.
  4. [Section 6.2, Tables 1–2] The numerical validation of intrinsic low-ε-Tucker-rank is circular with respect to the stated a priori claim. The observed ranks are computed by ST-HOSVD on explicitly assembled full tensors, not by the formula in Theorem 4.1, and they cannot confirm a rank bound that is larger than the mode dimension. Moreover, Table 1 shows observed ranks (21,8,8) for f₂ at ε=5×10⁻³, with the mode-1 rank equal to the full mode dimension 21; this is not a low-rank outcome. The experiments therefore do not validate the central claim that hyperinterpolation coefficient tensors have intrinsic low-ε-Tucker-rank with the specific logarithmic bound asserted in Theorem 4.1.
minor comments (4)
  1. [Section 1.1] There is a typo: 'Section 3 fformalizes' should be 'formalizes'. Also, the cross-reference 'Section tensor-hyperinterpolation:sect4-main' is a placeholder-style citation and should be replaced with a proper reference.
  2. [Tables 1–2 and Table 9] The column headers use f₁(x₁,x₂), f₂(x₁,x₂), f₃(x₁,x₂) even though the functions are three-dimensional; this is confusing. In Table 9, the text refers to 'the peak function f₃', but f₃ is the oscillatory cosine sum; the peak function is f₁.
  3. [General notation] The symbol σ_min(C_n) is used in Algorithm 5.1 with 'smallest nonzero singular value', but Definition 2.1 and the text elsewhere use σ_min without this clarification. This should be defined consistently.
  4. [Section 4.4, equation (4.10)] The reference to 'Corollary 4.3 in [31]' is not included in the bibliography entry for [31]; please check the citation numbering and ensure cross-references are accurate.

Circularity Check

0 steps flagged

No significant circularity: central existence theorem derives from an external matrix epsilon-rank theorem; the flagged greedy near-optimality gap and vacuous rank regime are correctness concerns, not circularity.

full rationale

I traced the paper's derivation chain. Theorem 4.1 is proved by recursive application of Corollary 4.1, which itself follows from the external Udell--Townsend matrix epsilon-rank theorem [53]. The rank formula is an explicit function of dimensions and epsilon, not fitted to the target tensors, and the max-norm error bound is obtained by a telescoping triangle-inequality argument. The TCUR error bounds in Theorem 4.4 depend on external results from Hamm--Huang [31] and Osinsky--Zamarashkin [45]; the constants are a posteriori functions of the actual selected index sets and mode singular values, not parameters fit to the test data. The paper's self-citations ([13], [14], [16]--[20]) appear as background on randomized Tucker methods and two-dimensional hyperinterpolation; they are not load-bearing for the central existence or error-bound theorems. I also considered the Section 5 assertion that the greedy index selection 'approximates maximum-volume submatrices... satisfying the volume-based pseudoinverse norm bounds in Remark 4.10.' This is a genuine unproved correctness gap, because Remark 4.10 only states bounds for genuinely maximum-volume submatrices, and the algorithms' stopping criterion uses sigma_min(C_n)/||C_n||_F, not a proven maximum-volume certificate. It is not, however, a circular step: the claim is asserted rather than derived from itself or from a self-citation. Similarly, the observed vacuity of Theorem 4.1's rank bound in the tested regime (e.g., I=20, epsilon=1e-2 gives R_1 ~ 4.4e6 > 21) is a substantive weakness in the claimed a priori low-rank guarantee, but it does not make the derivation circular. No equation or fitted quantity was found in which the conclusion reduces by definition to the inputs. Hence the appropriate circularity score is 0.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 0 invented entities

The central existence result is built entirely on the Udell-Townsend matrix epsilon-rank theorem applied mode-wise; the TCUR bounds are inherited from Hamm-Huang and volume arguments. The greedy algorithms add an unproved max-volume identification and hand-chosen block/threshold parameters. No new physical or mathematical entities are introduced.

free parameters (2)
  • block sizes b_n and stopping thresholds tau_1, tau_2 in greedy algorithms = b in {2,3,4,5}, tau in {0.05,0.02,0.01}
    Hand-chosen knobs determine which index subsets are selected and when each greedy algorithm stops; the advertised convergence and stability claims depend on them, yet no theorem links them to the error bounds.
  • target Tucker ranks (R1,R2,R3) = (10,10,10)
    Theorem 4.4 assumes the target rank tuple is pre-specified, and all numerical validations use (10,10,10); the theory does not provide a self-contained way to choose these ranks in the tensor-free setting.
axioms (5)
  • standard math Udell-Townsend matrix epsilon-rank theorem: every I1 x I2 matrix has a rank-ceil(72 ln(I1+I2+1)/epsilon^2) approximation with entrywise error at most epsilon ||A||_F.
    The building block of Theorem 4.1; if this result were not usable recursively, the low-Tucker-rank existence theorem would collapse.
  • standard math Hamm-Huang CUR perturbation bound and Osinsky-Zamarashkin volume-based bounds controling ||W^dagger||, ||V^dagger||.
    Theorem 4.4 and Remark 4.10 rely on these published bounds; they are imported without re-derivation.
  • ad hoc to paper Greedy block-expanding index selection approximates maximum-volume submatrices of the SVD factors W_{n,R_n} and V_{n,R_n}.
    Stated in Section 5 as the source of near-optimality and stability, but no lemma or proof is given; this is load-bearing for the claim that Algorithm outputs satisfy Theorem 4.4's constants.
  • domain assumption The target function lies in Sobolev space H^alpha and the coefficient tensor is built with tensor-product positive cubature exact to degree 2 I_n.
    Theorems 3.2, 4.3 and 4.5 depend on this setting; experiments use Gauss-Chebyshev cubature.
  • ad hoc to paper R_n < I_n+1 holds in the relevant parameter regime, giving strict storage reduction.
    Remark 4.2 asserts this, but the formula with constant 72/epsilon^2 gives R_n >> I_n+1 for the tested I=20,30 and epsilon=0.01; the claim is unsupported in the evaluated regime.

pith-pipeline@v1.3.0-alltime-deepseek · 41512 in / 15894 out tokens · 163254 ms · 2026-08-01T11:50:33.632121+00:00 · methodology

0 comments
read the original abstract

High-dimensional hyperinterpolation is severely hampered by the curse of dimensionality, as its coefficient tensors grow exponentially with the ambient dimension. Existing research predominantly focuses on heuristic algorithmic optimizations, often overlooking the inherent structural properties of these tensors. This paper establishes a rigorous theory of intrinsic low-$\epsilon$-Tucker-rank for hyperinterpolation coefficient tensors, delivering near-optimal low-rank approximations with error bounds that are nearly independent of the dimension. We further construct a unified, Tucker-compatible theoretical framework that integrates both Chidori-type and Fiber-type tensor CUR (TCUR) decompositions, deriving tight and stable Frobenius-norm error estimates that depend exclusively on tensor spectral properties and index set geometry. We mathematically verify the convergence and numerical stability of greedy adaptive index selection schemes and prove their near-optimality, enabling a fully tensor-free hyperinterpolation workflow that avoids constructing the full coefficient array. Three practical greedy TCUR algorithms and a lightweight TCUR-to-Tucker recompression pipeline are proposed as direct corollaries of our structural theory. Numerical experiments across three distinct families of high-dimensional test functions validate all theoretical predictions and confirm the intrinsic low-rank compressibility of hyperinterpolation coefficients. In contrast to prior algorithm-centric studies, this work prioritizes rigorous theoretical characterization over implementation tricks, establishing a unified structural and mathematical foundation for high-dimensional hyperinterpolation.

Figures

Figures reproduced from arXiv: 2607.19741 by Chong Wu, Maolin Che, Yimin Wei.

Figure 1
Figure 1. Figure 1: Illustration of Theorem 4.1, with different values for the pair ( [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Observed and theoretical ϵ-Tucker rank for f2(x1, x2, x3) with ϵ = 0.01. ϵ, [PITH_FULL_IMAGE:figures/full_fig_p032_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Comparison of observed Tucker ranks across test functions [PITH_FULL_IMAGE:figures/full_fig_p033_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Decay of stopping criterion tol = max{σmin(G(n) )/∥G∥F : n = 1, 2, . . . , N} with iteration k for Algorithm 5.2 applied to f2(x1, x2, x3) with b = 2 and τ = 0.01. 6.4 Validation of unified TCUR error bounds We now validate the unified TCUR error bounds from Theorem 4.4, which provide computable upper bounds for the Frobenius-norm discrepancy ∥A−e AeTCUR∥F in terms of the mode-n unfolding singular values a… view at source ↗
Figure 5
Figure 5. Figure 5: Normalized singular value spectra of each mode unfolding for the three test functions. [PITH_FULL_IMAGE:figures/full_fig_p037_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of full hyperinterpolation (left-top) and Tucker-compressed approximation [PITH_FULL_IMAGE:figures/full_fig_p039_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Decomposition of recompression error into TCUR sampling residual and Tucker trunca [PITH_FULL_IMAGE:figures/full_fig_p045_7.png] view at source ↗

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

152 extracted references · 2 canonical work pages

  1. [1]

    , title =

    Battaglino, Casey and Ballard, Grey and Kolda, Tamara G. , title =. SIAM Journal on Matrix Analysis and Applications , volume =

  2. [2]

    arXiv preprint arXiv:2506.07729 , year=

    Minimal Subsampled Rank-1 Lattices for Multivariate Approximation with Optimal Convergence Rate , author=. arXiv preprint arXiv:2506.07729 , year=

    arXiv

  3. [3]

    SIAM Review , volume=

    Cubature, approximation, and isotropy in the hypercube , author=. SIAM Review , volume=. 2017 , publisher=

    2017

  4. [4]

    arXiv preprint arXiv:2510.13204 , year=

    How many integrals should be evaluated at least in two-dimensional hyperinterpolation? , author=. arXiv preprint arXiv:2510.13204 , year=

    Pith/arXiv arXiv

  5. [5]

    SIAM Journal on Mathematics of Data Science , volume=

    When big data actually are low-rank, or entrywise approximation of certain function-generated matrices , author=. SIAM Journal on Mathematics of Data Science , volume=. 2025 , publisher=

    2025

  6. [6]

    SIAM Journal on Scientific Computing , volume=

    A randomized algorithm for multivariate function approximation , author=. SIAM Journal on Scientific Computing , volume=. 2017 , publisher=

    2017

  7. [7]

    , title =

    Trefethen, Lloyd N. , title =. 2019 , address =

    2019

  8. [8]

    SIAM Journal on Scientific Computing , volume=

    A randomized tensor quadrature method for high dimensional polynomial approximation , author=. SIAM Journal on Scientific Computing , volume=. 2017 , publisher=

    2017

  9. [9]

    Journal of Approximation Theory , volume=

    Polynomial interpolation and hyperinterpolation over general regions , author=. Journal of Approximation Theory , volume=. 1995 , publisher=

    1995

  10. [10]

    Linear Algebra and its Applications , volume=

    Pseudo-skeleton approximations with better accuracy estimates , author=. Linear Algebra and its Applications , volume=. 2018 , publisher=

    2018

  11. [11]

    Accuracy and stability of

    Park, Taejun and Nakatsukasa, Yuji , journal=. Accuracy and stability of. 2025 , publisher=

    2025

  12. [12]

    Multivariate

    Reimer, Manfred , volume=. Multivariate. 2012 , publisher=

    2012

  13. [13]

    SIAM Journal on Mathematics of Data Science , volume=

    Why are big data matrices approximately low rank? , author=. SIAM Journal on Mathematics of Data Science , volume=. 2019 , publisher=

    2019

  14. [14]

    SIAM Review , volume=

    Bounds on the singular values of matrices with displacement structure , author=. SIAM Review , volume=. 2019 , publisher=

    2019

  15. [15]

    Proceedings of the American Mathematical Society , volume=

    Multivariate polynomial approximation in the hypercube , author=. Proceedings of the American Mathematical Society , volume=

  16. [16]

    Near-best multivariate approximation by

    Mason, John Charles , journal=. Near-best multivariate approximation by. 1980 , publisher=

    1980

  17. [17]

    Foundations of Computational Mathematics , volume=

    Analysis of tensor approximation schemes for continuous functions , author=. Foundations of Computational Mathematics , volume=. 2023 , publisher=

    2023

  18. [18]

    Advances in Computational Mathematics , volume=

    Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions , author=. Advances in Computational Mathematics , volume=. 2022 , publisher=

    2022

  19. [19]

    Functional

    Dolgov, Sergey and Kressner, Daniel and Str\". Functional. SIAM Journal on Scientific Computing , volume=. 2021 , publisher=

    2021

  20. [20]

    Low-rank approximation of continuous functions in

    Griebel, Michael and Harbrecht, Helmut and Schneider, Reinhold , journal=. Low-rank approximation of continuous functions in

  21. [21]

    SIAM Journal on Scientific Computing , volume=

    Chebfun in three dimensions , author=. SIAM Journal on Scientific Computing , volume=. 2017 , publisher=

    2017

  22. [22]

    Functional tensor-train

    Soley, Micheline B and Bergold, Paul and Gorodetsky, Alex A and Batista, Victor S , journal=. Functional tensor-train. 2021 , publisher=

    2021

  23. [23]

    GEM-International Journal on Geomathematics , volume=

    Filtered hyperinterpolation: a constructive polynomial approximation on the sphere , author=. GEM-International Journal on Geomathematics , volume=

  24. [24]

    SIAM Journal on Scientific Computing , volume=

    Lasso hyperinterpolation over general regions , author=. SIAM Journal on Scientific Computing , volume=

  25. [25]

    SIAM Journal on numerical analysis , volume=

    Regularized least squares approximations on the sphere using spherical designs , author=. SIAM Journal on numerical analysis , volume=. 2012 , publisher=

    2012

  26. [26]

    biometrika , volume=

    Ideal spatial adaptation by wavelet shrinkage , author=. biometrika , volume=. 1994 , publisher=

    1994

  27. [27]

    Perturbations of

    Hamm, Keaton and Huang, Longxiu , journal=. Perturbations of. 2021 , publisher=

    2021

  28. [28]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Efficient Randomized Algorithms for Fixed Precision Problem of Approximate Tucker Decomposition , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2025 , publisher=

    2025

  29. [29]

    SIAM Journal on Matrix Analysis and Applications , volume=

    A block bidiagonalization method for fixed-accuracy low-rank matrix approximation , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2022 , publisher=

    2022

  30. [30]

    Randomized algorithms for the approximations of

    Che, Maolin and Wei, Yimin , journal=. Randomized algorithms for the approximations of

  31. [31]

    SIAM Review , volume=

    Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions , author=. SIAM Review , volume=. 2011 , publisher=

    2011

  32. [32]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Efficient randomized algorithms for the fixed-precision low-rank matrix approximation , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2018 , publisher=

    2018

  33. [33]

    SIAM Journal on Scientific computing , volume=

    An algorithm for the principal component analysis of large data sets , author=. SIAM Journal on Scientific computing , volume=. 2011 , publisher=

    2011

  34. [34]

    The fast

    Ailon, Nir and Chazelle, Bernard , journal=. The fast. 2009 , publisher=

    2009

  35. [35]

    Journal of the ACM (JACM) , volume=

    Low-rank approximation and regression in input sparsity time , author=. Journal of the ACM (JACM) , volume=. 2017 , publisher=

    2017

  36. [36]

    2022 , publisher=

    Bamberger, Stefan and Krahmer, Felix and Ward, Rachel , journal=. 2022 , publisher=

    2022

  37. [37]

    Jin, Ruhui and Kolda, Tamara G and Ward, Rachel , journal=. Faster. 2021 , publisher=

    2021

  38. [38]

    Structured random sketching for

    Chen, Ke and Li, Qin and Newton, Kit and Wright, Stephen J , journal=. Structured random sketching for. 2020 , publisher=

    2020

  39. [39]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Tensor-structured sketching for constrained least squares , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2021 , publisher=

    2021

  40. [40]

    Sketching for

    Diao, Huaian and Song, Zhao and Sun, Wen and Woodruff, David , booktitle=. Sketching for. 2018 , organization=

    2018

  41. [41]

    Foundations and Trends

    Sketching as a tool for numerical linear algebra , author=. Foundations and Trends. 2014 , publisher=

    2014

  42. [42]

    2022 , publisher=

    Sobczyk, Aleksandros and Gallopoulos, Efstratios , journal=. 2022 , publisher=

    2022

  43. [43]

    ACM Transactions on Computation Theory (TOCT) , volume=

    Compressed matrix multiplication , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2013 , publisher=

    2013

  44. [44]

    Improved matrix algorithms via the subsampled randomized

    Boutsidis, Christos and Gittens, Alex , journal=. Improved matrix algorithms via the subsampled randomized. 2013 , publisher=

    2013

  45. [45]

    Applied and Computational Harmonic Analysis , volume=

    A fast randomized algorithm for the approximation of matrices , author=. Applied and Computational Harmonic Analysis , volume=. 2008 , publisher=

    2008

  46. [46]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Practical sketching algorithms for low-rank matrix approximation , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2017 , publisher=

    2017

  47. [47]

    arXiv preprint arXiv:2306.12418 , year=

    Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications , author=. arXiv preprint arXiv:2306.12418 , year=

    Pith/arXiv arXiv

  48. [48]

    Randomized block

    Musco, Cameron and Musco, Christopher , journal=. Randomized block

  49. [49]

    SIAM Journal on Matrix Analysis and Applications , volume=

    A randomized algorithm for principal component analysis , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2010 , publisher=

    2010

  50. [50]

    SIAM Journal on Scientific Computing , volume=

    Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views , author=. SIAM Journal on Scientific Computing , volume=. 2019 , publisher=

    2019

  51. [51]

    Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

    Numerical linear algebra in the streaming model , author=. Proceedings of the forty-first annual ACM symposium on Theory of computing , pages=

  52. [52]

    Linear Algebra and its Applications , volume=

    Fast randomized numerical rank estimation for numerically low-rank matrices , author=. Linear Algebra and its Applications , volume=. 2024 , publisher=

    2024

  53. [53]

    SIAM Journal on Scientific Computing , volume=

    A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices , author=. SIAM Journal on Scientific Computing , volume=. 2016 , publisher=

    2016

  54. [54]

    SIAM Journal on Scientific Computing , volume=

    On the compression of low rank matrices , author=. SIAM Journal on Scientific Computing , volume=

  55. [55]

    Psychometrika , volume=

    The approximation of one matrix by another of lower rank , author=. Psychometrika , volume=

  56. [56]

    The quarterly journal of mathematics , volume=

    Symmetric gauge functions and unitarily invariant norms , author=. The quarterly journal of mathematics , volume=

  57. [57]

    and Hussaini, M

    Canuto, C. and Hussaini, M. and Quarteroni, A. and Zang, T. , year=

  58. [58]

    Applied and Computational Harmonic Analysis , volume=

    A randomized algorithm for the decomposition of matrices , author=. Applied and Computational Harmonic Analysis , volume=

  59. [59]

    Ghahremani, Behzad and Babaee, Hessam , journal=. A

  60. [60]

    Cross interpolation for solving high-dimensional dynamical systems on low-rank

    Ghahremani, Behzad and Babaee, Hessam , journal=. Cross interpolation for solving high-dimensional dynamical systems on low-rank

  61. [61]

    SIAM Review , volume=

    On the early history of the singular value decomposition , author=. SIAM Review , volume=. 1993 , publisher=

    1993

  62. [62]

    SIAM Journal on Scientific Computing , volume=

    Spectral tensor-train decomposition , author=. SIAM Journal on Scientific Computing , volume=. 2016 , publisher=

    2016

  63. [63]

    Boutsidis, Christos and Woodruff, David P , journal=. Optimal. 2017 , publisher=

    2017

  64. [64]

    2009 , publisher=

    Mahoney, Michael W and Drineas, Petros , journal=. 2009 , publisher=

    2009

  65. [65]

    Sorensen, Danny C and Embree, Mark , journal=. A. 2016 , publisher=

    2016

  66. [66]

    and Van Loan, C

    Golub, G. and Van Loan, C. , TITLE =. 2013 , PAGES =

    2013

  67. [67]

    SIAM Journal on Scientific Computing , volume=

    Nonlinear model reduction via discrete empirical interpolation , author=. SIAM Journal on Scientific Computing , volume=. 2010 , publisher=

    2010

  68. [68]

    SIAM Review , volume=

    Randomized projection for rank-revealing matrix factorizations and low-rank approximations , author=. SIAM Review , volume=. 2020 , publisher=

    2020

  69. [69]

    Efficient algorithms for

    Voronin, Sergey and Martinsson, Per-Gunnar , journal=. Efficient algorithms for. 2017 , publisher=

    2017

  70. [70]

    Numerische Mathematik , volume=

    Approximation of boundary element matrices , author=. Numerische Mathematik , volume=. 2000 , publisher=

    2000

  71. [71]

    On the low-rank approximation by the pivoted

    Harbrecht, Helmut and Peters, Michael and Schneider, Reinhold , journal=. On the low-rank approximation by the pivoted. 2012 , publisher=

    2012

  72. [72]

    Efficient algorithms for computing a strong rank-revealing

    Gu, Ming and Eisenstat, Stanley C , journal=. Efficient algorithms for computing a strong rank-revealing. 1996 , publisher=

    1996

  73. [73]

    Relative-error

    Drineas, Petros and Mahoney, Michael W and Muthukrishnan, Shan , journal=. Relative-error. 2008 , publisher=

    2008

  74. [74]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Sublinear randomized algorithms for skeleton decompositions , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2013 , publisher=

    2013

  75. [75]

    Low-rank approximation in the

    Cortinovis, Alice and Kressner, Daniel , journal=. Low-rank approximation in the. 2020 , publisher=

    2020

  76. [76]

    Linear Algebra and its Applications , volume=

    A theory of pseudoskeleton approximations , author=. Linear Algebra and its Applications , volume=

  77. [77]

    Notices of the American Mathematical Society , volume=

    Determinantal point processes in randomized numerical linear algebra , author=. Notices of the American Mathematical Society , volume=

  78. [78]

    SIAM Journal on Computing , volume=

    Near-optimal column-based matrix reconstruction , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  79. [79]

    A hybrid

    Gidisu, Perfect Y and Hochstenbach, Michiel E , booktitle=. A hybrid. 2021 , publisher=

    2021

  80. [80]

    A volume associated with m n matrices , author=. Linear. 1992 , publisher=

    1992

Showing first 80 references.