Pith. sign in

REVIEW 2 major objections 4 minor 2 cited by

Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation

T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read For any orthonormal row-space basis $V$, adaptive randomized pivoting returns $r$ indices whose expected squared approximation error is exactly $(r+1)\|A - A V V^T\|_F^2$; with $V$ equal to the top right singular vectors this matches the…

desk verdict The paper's sleek adaptive sampling scheme is genuinely useful, but the headline equality in Theorem 2.4 is false; the right statement is an inequality, and the upper-bound corollaries survive. read the letter →

arxiv 2412.13992 v2 pith:OD7RVKTU submitted 2024-12-18 math.NA cs.NA

Alice Cortinovis , Daniel Kressner This is my paper · ORCID
classification math.NAcs.NA MSC 65F5568W20
keywords randomizedalgorithmscolumnsubsetselectionadaptivesamplingleveragescoreslow-rankapproximationDEIMcrossNyström
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Column subset selection asks for a small set of columns that nearly reproduces the whole matrix, and the best possible guarantee is that the squared error is at most $(r+1)$ times the tail energy of the singular values. This paper gives a randomized algorithm that achieves that factor in expectation, with a sampling rule that is much cheaper than the previously known volume-sampling construction. The rule samples one index at a time, with probability proportional to the squared row norms of an orthonormal row-space basis $V$, then projects the selected row out and repeats. The central theorem is an exact identity: the expected squared error of the resulting interpolation-based projection equals $(r+1)\|A - A V V^T\|_F^2$. The same strategy applies to the discrete empirical interpolation method (DEIM), to cross or skeleton approximation, and to Nyström approximation, with error bounds that match or improve known deterministic results, and it derandomizes to deterministic algorithms including a new one for positive semi-definite matrices.

What carries the argument

The load-bearing object is the adaptive leverage-score sampling process run on an orthonormal basis $V$. At step $k$, the algorithm draws $j_k$ with probability $\|V_{k-1}(j_k,:)\|_2^2/(r-k+1)$, then replaces $V_{k-1}$ by $V_{k-1}(I - V_{k-1}(j_k,:)^\dagger V_{k-1}(j_k,:))$, an orthogonal projection that removes the selected row. The proof factors the resulting oblique projector (an interpolation operator that leaves the selected columns fixed) $\tilde{\Pi}_J = I - E_J(V^T E_J)^{-1}V^T$ into a product of $r$ one-step oblique projectors and uses the identity $A - A(:,J)V(J,:)^{-T}V^T = \tilde{A}\tilde{\Pi}_J$ with $\tilde{A}=A(I - V V^T)$. Conditioned on the previous choices, the squared Frobenius norm of the residual satisfies $\mathbb{E}[\|\tilde{A}_k\|_F^2] = \frac{r-k+2}{r-k+1}\|\tilde{A}_{k-1}\|_F^2$, and the product of these factors from $k=1$ to $r$ collapses to exactly $r+1$.

What would settle it

Take a small matrix with known singular values (for example, a diagonal matrix), fix $V$ to its top $r$ right singular vectors, run Algorithm 2.1 many times, and compare the empirical average of $\|A - A(:,J)V(J,:)^{-T}V^T\|_F^2$ with $(r+1)(\sigma_{r+1}^2+\cdots+\sigma_n^2)$; a systematic deviation beyond sampling noise would refute Theorem 2.4.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that adaptive leverage score sampling compresses a rank-$r$ subspace approximation into a genuine column selection without paying more than the optimal factor. Theorem 2.4 states that if $V\in\mathbb{R}^{n\times r}$ has orthonormal columns and $J=(j_1,\dots,j_r)$ is produced by Algorithm 2.1, then $\mathbb{E}[\|A - A(:,J)V(J,:)^{-T}V^T\|_F^2] = (r+1)\|A - A V V^T\|_F^2$. The index set is chosen from $V$ alone, so no entry of $A$ is inspected during selection; the matrix $A$ is only read at the chosen columns to form the approximation. Taking $V$ to be the right singular vectors belonging to the $r$ largest singular values makes the right-hand side $(r+1)(\sigma_{r+1}^2+\cdots+\sigma_n^2)$, which is the optimal existence result for column subset selection. The same mechanism gives, in expectation, a DEIM interpolation error of at most $(r+1)\|f - V V^T f\|_2^2$, a cross-approximation error of at most $(r+1)^2\|A - A V V^T\|_F^2$, and a Nyström error of at most $(r+1)\|(I - V V^T)A(I - V V^T)\|_*$, where the last norm is the nuclear norm (sum of singular values).

Load-bearing premise

The whole guarantee rests on having an orthonormal matrix $V$ that already captures the row space of $A$; if $V$ is inaccurate the expected error bound can be large even though the equality itself holds, and the strongest corollary needs $V$ to be the exact top right singular vectors, which costs a full singular value decomposition.

Editorial extensions

If this is right

  • With $V$ equal to the top $r$ right singular vectors, the expected squared Frobenius error of the orthogonal projection onto the selected columns is at most $(r+1)$ times the tail squared singular values, and a simple tail bound gives the same guarantee up to a factor $10\sqrt{r+1}$ with probability at least 99%.
  • In DEIM, the index set can be chosen without evaluating the vector $f$ being interpolated, and the expected squared interpolation error is at most $(r+1)\|f - V V^T f\|_2^2$; the same selection also controls the expected norm of the inverse interpolation matrix.
  • For cross or skeleton approximation, selecting rows and columns independently by the same rule yields expected squared error at most $(r+1)^2\|A - A V V^T\|_F^2$ while reading only $r$ rows and $r$ columns of $A$.
  • For a symmetric positive semi-definite matrix, the same selection yields a Nyström approximation whose expected nuclear-norm error is at most $(r+1)(\sigma_{r+1}(A)+\cdots+\sigma_n(A))$ when $V$ is the exact top right singular subspace, and a deterministic variant achieves this bound without forming a square root of $A$.

Reading between the lines

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

  • A direct extension the authors leave implicit is to drive the method with a $V$ obtained from a structured sketch of $A^T$; the theorem then provides an end-to-end sublinear-cost column selection with the same $(r+1)$ factor plus the sketch error.
  • Because the proof is an exact telescoping product of conditional expectations, sharper large-deviation bounds than the crude tail bound should be available; if the multiplicative factors are nearly independent, standard concentration arguments could replace the constant $10$.
  • The equivalence with sampling from a determinantal point process, noted in the paper, suggests that any $r$-subset sampler for the DPP with kernel $VV^T$ inherits the same guarantee, opening the way to faster sampling or to formulas for marginal inclusion probabilities.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper introduces Adaptive Randomized Pivoting (ARP), an adaptive leverage-score sampling procedure for selecting r columns of a matrix A using only an orthonormal row-space basis V. The method updates V by orthogonal projection after each selected row and produces an index set J. The paper claims an exact expectation identity, E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] = (r+1)||A - A V V^T||_F^2 (Theorem 2.4), which would match the optimal volume-sampling factor in expectation. It then applies ARP to DEIM, cross/skeleton approximation, and Nyström approximation, and gives a derandomization that recovers Osinsky's deterministic algorithm, including a new deterministic Nyström algorithm. Numerical experiments on CSSP, DEIM, cross approximation, and SPSD matrices illustrate the method.

Significance. If the main theorem is read as an upper bound, the paper offers a genuinely simple, cheap, and data-oblivious sampling scheme that attains the optimal (r+1) factor in expectation for column subset selection, with clean extensions to DEIM and cross approximation and a new deterministic Nyström algorithm with a favorable error bound. The algorithms have concrete computational advantages over volume sampling and over Osinsky's deterministic method, and the numerical experiments are reproducible and supportive. However, the exact equality advertised in Theorem 2.4 is false as stated; the proof establishes only an inequality. Because all corollaries are upper bounds, the main algorithmic contributions survive a weakening of the theorem, but the paper's strongest theoretical claim must be corrected before publication.

major comments (2)
  1. [Section 2.3, Theorem 2.4 / Eq. (2.15)] The claimed equality is false. In the fourth equality of (2.17), the conditional expectation is evaluated as (1/(r-k+1)) * sum over all j not in J_{k-1} of ||~A_{k-1}(:,j)||^2, which cancels p_j = ||V_{k-1}(j,:)||^2/(r-k+1) against the denominator ||V_{k-1}(j,:)||^2. This cancellation is valid only on the support {j : ||V_{k-1}(j,:)|| > 0}. Zero rows of V_{k-1} can carry nonzero columns of ~A_{k-1}; they contribute 0 to the conditional expectation but are counted in the unrestricted sum. Counterexample: A = I_3, r = 1, V = e_1. Algorithm 2.1 deterministically returns J = {1}, so the left side of (2.15) equals ||I_3 - e_1 e_1^T||_F^2 = 2, while the right side equals (r+1) ||A - A V V^T||_F^2 = 2 * 2 = 4. Restricting the sum to the support yields the valid inequality E[||A - A(:,J) V(J,:)^{-T} V^T||_F^2] <= (r+1) ||A - A V V^T||_F^2. The upper-bound corollaries survive, but the exact equalities in (1.5), (2.15), and the proof of Corollary 3.1 need correction.
  2. [Section 3, Corollary 3.1] The displayed identity E[||(E_I^T V)^{-1}||_F^2] = r(n-r+1) is false. It follows from applying Theorem 2.4 to A = Id_n, which would give E[||~Pi_I||_F^2] = (r+1)(n-r). With V = e_1, n = 3, r = 1, the algorithm deterministically returns I = {1}, so ||~Pi_I||_F^2 = 2 while (r+1)(n-r) = 4. The correct statement is E[||~Pi_I||_F^2] <= (r+1)(n-r), and this still implies E[||(E_I^T V)^{-1}||_F^2] <= r(n-r+1) and the advertised spectral norm bound E[||(E_I^T V)^{-1}||_2^2] <= 1 + r(n-r).
minor comments (4)
  1. [Section 2.3, proof of Theorem 2.4] The displayed chain after (2.17) has index errors; it should read E[||~A_r||_F^2] = E[E[||~A_r||_F^2 | j1,...,j_{r-1}]] = 2 E[||~A_{r-1}||_F^2].
  2. [Section 6.1, Figures 2a and 2b] The legends label Osinsky's deterministic algorithm as 'Algorithm 2.2', but the text and Algorithm 2.3 refer to it as Algorithm 2.3; the legends should be corrected.
  3. [Section 2.2] The phrase 'orthonogonal transformations' is a typo for 'orthogonal transformations'.
  4. [Sections 2.3 and 2.4] After changing Theorem 2.4 to an inequality, the statements 'the fourth equality follows from the definition of the sampling probabilities' and the use of 'the inequality (2.17)' in the derandomization argument need to be reworded, since (2.17) is an equality only on the support of V_{k-1}.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central expectation bound is derived directly from the algorithm's sampling probabilities and oblique projections, with no fitted parameter renamed as a prediction and no load-bearing self-citation chain.

full rationale

The derivation of Theorem 2.4 is self-contained. The algorithm defines sampling probabilities explicitly from the row norms of the current V_{k-1}, and the proof computes the conditional expectation of ||~A_k||_F^2 using those probabilities together with an orthogonality/Pythagoras argument. The target quantity ||A - A(:,J)V(J,:)^{-T}V^T||_F^2 is not fed into the algorithm or into the statement; it is the quantity being bounded. No parameter is fitted to data and then called a prediction: V is an input approximation of the row space, and the theorem gives a bound in terms of that same V, which is a normal worst-case/input-dependent guarantee rather than circularity. The corollaries obtain the optimal-SVD and randomized-SVD variants by substituting V = V_opt or a sketched basis; these are standard uses of an input subspace, not renaming of the output. The paper explicitly recovers Osinsky's deterministic algorithm by derandomization, but that is an external result and a recovery, not a self-citation used to justify the main claim. The only self-citation, [9], supports the statement that Deshpande-Rademacher volume sampling is numerically challenging; this is not load-bearing for the paper's central derivation. Remark 2.2 honestly notes that the sampling process is equivalent to an r-DPP with kernel VV^T, which is an acknowledgement rather than a hidden renaming. Any concern about the validity of the equality in Theorem 2.4 (e.g., cancellation of zero row norms) is a mathematical correctness issue, not circularity, and is outside the circularity pass.

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

The central result requires only standard linear algebra and the algorithmic input V; no free parameters are fitted to data, and no entities are invented. The practical effectiveness depends on the quality of V, which is a domain assumption rather than a mathematical assumption.

assumptions (5)
  • standard math V is an n x r matrix with orthonormal columns
    Algorithm input; used in Lemma 2.1 and the proof of Theorem 2.4 to guarantee V^T V = I_r.
  • standard math Properties of orthogonal and oblique projections, pseudoinverses, and Frobenius norms
    The proof of Theorem 2.4 and the derivations in Sections 3-5 rely on standard linear algebra facts about projections and the Gram correspondence.
  • standard math For SPSD A, a matrix B with B^T B = A exists (Gram correspondence)
    Used in Section 5, equation (5.2), to convert Nyström error to a column-subset error for B.
  • standard math The selected row submatrix V(J,:) is invertible
    Proved in Section 2.2 via the lower triangular structure of W_r(J,:); the oblique projection (2.9) requires this invertibility.
  • domain assumption A row-space approximation V satisfying ||A - A V V^T||_F approximately 0 is available
    The practical value of the bound (2.15) depends on V being accurate; for the optimal bound, V must be the exact right singular vector matrix Vopt, which may be expensive to compute.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation." pith.science (2026). https://pith.science/paper/OD7RVKTU

@misc{pith2026241213992,
  author       = {Pith},
  title        = {Pith review of: Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OD7RVKTU}},
  note         = {Machine review of arXiv:2412.13992}
}
read the original abstract

We derive a new adaptive leverage score sampling strategy for solving the Column Subset Selection Problem (CSSP). The resulting algorithm, called Adaptive Randomized Pivoting, can be viewed as a randomization of Osinsky's recently proposed deterministic algorithm for CSSP. It guarantees, in expectation, an approximation error that matches the optimal existence result in the Frobenius norm. Although the same guarantee can be achieved with volume sampling, our sampling strategy is much simpler and less expensive. To show the versatility of Adaptive Randomized Pivoting, we apply it to select indices in the Discrete Empirical Interpolation Method, in cross/skeleton approximation of general matrices, and in the Nystroem approximation of symmetric positive semi-definite matrices. In all these cases, the resulting randomized algorithms are new and they enjoy bounds on the expected error that match -- or improve -- the best known deterministic results. A derandomization of the algorithm for the Nystroem approximation results in a new deterministic algorithm with a rather favorable error bound.

Figures

Figures reproduced from arXiv: 2412.13992 by the authors.

Figure 1
Figure 1. Illustration of Algorithm 2.2 applied to a matrix V ∈ R 8×3 . kWk−1(:, k : r)k 2 F = r−k+ 1, which confirms that the quantities pj ≥ 0 computed in Line 3 indeed represent a probability distribution. The final, updated matrix Wr satisfies Wr = V Q, Q := Q1Q2 · · · Qr. In particular, we have that (2.8) Wr(J, :) = V (J, :)Q. By construction, Wr(J, :) is lower triangular. Its kth diagonal element contains the norm of th… view at source ↗
Figure 2
Figure 2. Comparison of different CSSP strategies; the error is [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Numerical results for DEIM (left) and cross approximation ( [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Selection of column indices for SPSD matrices: smile (left) and s [PITH_FULL_IMAGE:figures/full_fig_p020_4.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Compression Properties for large Toeplitz-like matrices

    math.NA 2025-02 conditional novelty 7.0 of 10

    For Toeplitz-like matrices, the paper proves explicit epsilon-rank bounds of order rho log(m) log(1/epsilon) for off-diagonal submatrices of the transformed matrix and uses them to build adaptive HODLR and HSS compres...

  2. Interpolatory dynamical low-rank approximation for the 3+3d Boltzmann-BGK equation

    math.NA 2024-11 conditional novelty 6.0 of 10

    New interpolatory dynamical low-rank methods, interpolatory projector-splitting and basis update and collocate (BUC), compute six-dimensional Boltzmann-BGK solutions with n^3 scaling, demonstrated on 3d3v shear flow a...

Reference graph

Works this paper leans on

32 extracted references · 16 canonical work pages · cited by 2 Pith papers

  1. [1]

    Barrault, Y

    M. Barrault, Y. Maday, N. C. Nguyen, and A. T. Patera , An ‘empirical interpolation ’ method: application to efficient reduced-basis discretization of partial differe ntial equations, C. R. Math. Acad. Sci. Paris, 339 (2004), pp. 667–672, https://doi.org/10.1016/j.crma.2004.08.006

    doi:10.1016/j.crma.2004.08.006 2004

  2. [2]

    Barthelme, N

    S. Barthelme, N. Tremblay, and P.-O. Amblard , A faster sampler for discrete determinantal point pro- cesses, in International Conference on Artificial Intelligence an d Statistics, PMLR, 2023, pp. 5582–5592

    work page 2023

  3. [3]

    Bebendorf , Approximation of boundary element matrices , Numer

    M. Bebendorf , Approximation of boundary element matrices , Numer. Math., 86 (2000), pp. 565–589, https:// doi.org/10.1007/PL00005410

    doi:10.1007/pl00005410 2000

  4. [4]

    Belhadji, R

    A. Belhadji, R. Bardenet, and P. Chainais , A determinantal point process for column subset selection , J. Mach. Learn. Res., 21 (2020), pp. Paper No. 197, 62

    work page 2020

  5. [5]

    Boutsidis, M

    C. Boutsidis, M. W. Mahoney, and P. Drineas , An improved approximation algorithm for the column subset selection problem , in Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2009, pp. 968–977

    work page 2009

  6. [6]

    Chaturantabut and D

    S. Chaturantabut and D. C. Sorensen , Nonlinear model reduction via discrete empirical interpol ation, SIAM J. Sci. Comput., 32 (2010), pp. 2737–2764, https://doi.org/10.1137/090766498

    doi:10.1137/090766498 2010

  7. [7]

    Y. Chen, E. N. Epperly, J. A. Tropp, and R. J. Webber , Randomly pivoted Cholesky: Practical approxi- mation of a kernel matrix with few entry evaluations , Comm. Pure Appl. Math., (2024), https://doi.org/ 10.1002/cpa.22234

    doi:10.1002/cpa.22234 2024

  8. [8]

    Chiu and L

    J. Chiu and L. Demanet , Sublinear randomized algorithms for skeleton decompositi ons, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1361–1383, https://doi.org/10.1137/110852310

    work page doi:10.1137/110852310 2013

Show all 32 references
  1. [9]

    Cortinovis and D

    A. Cortinovis and D. Kressner , Low-rank approximation in the Frobenius norm by column and r ow subset selection, SIAM J. Matrix Anal. Appl., 41 (2020), pp. 1651–1673, https://doi.org/10.1137/19M1281848

    2020 doi

  2. [10]

    T. A. Davis and Y. Hu , The University of Florida sparse matrix collection , ACM Trans. Math. Software, 38 (2011), pp. Art. 1, 25, https://doi.org/10.1145/2049662.2049663

    2011

  3. [11]

    Deshpande and L

    A. Deshpande and L. Rademacher , Efficient volume sampling for row/column subset selection , in 2010 IEEE 51st Annual Symposium on Foundations of Computer Scien ce—FOCS 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 329–338

    2010

  4. [12]

    Deshpande, L

    A. Deshpande, L. Rademacher, S. Vempala, and G. W ang , Matrix approximation and projective clustering via volume sampling , Theory Comput., 2 (2006), pp. 225–247, https://doi.org/10.4086/toc.2006.v002a012

    2006 doi

  5. [13]

    Dong and P.-G

    Y. Dong and P.-G. Martinsson , Simpler is better: a comparative study of randomized pivoti ng algorithms for CUR and interpolative decompositions , Adv. Comput. Math., 49 (2023), pp. Paper No. 66, 29, https:// doi.org/10.1007/s10444-023-10061-z

    2023 doi

  6. [14]

    Drineas, M

    P. Drineas, M. W. Mahoney, and S. Muthukrishnan , Subspace sampling and relative-error matrix ap- proximation: column-based methods , in Approximation, randomization and combinatorial optim ization, vol. 4110 of Lecture Notes in Comput. Sci., Springer, Berlin , 2006, pp. 316–3...

    2006

  7. [15]

    Drma ˇc and S

    Z. Drma ˇc and S. Gugercin , A new selection operator for the discrete empirical interpo lation method— improved a priori error bound and extensions , SIAM J. Sci. Comput., 38 (2016), pp. A631–A648, https:// doi.org/10.1137/15M1019271

    2016 doi

  8. [16]

    E. N. Epperly , Low-rank approximation toolbox: The Gram correspondence . https://www.ethanepperly.com/ index.php/2024/12/07/low-rank-approximation-toolbox-the-gram-correspondence/ . Accessed: 2024-12- 16

    2024

  9. [17]

    Fornace and M

    M. Fornace and M. Lindsey , Column and row subset selection using nuclear scores: algor ithms and the- ory for nystr \”{o} m approximation, cur decomposition, and graph laplacian re duction, arXiv preprint arXiv:2407.01698, (2024). 22 A. CORTINOVIS AND D. KRESSNER

    2024 arXiv

  10. [18]

    G. H. Golub and C. F. V an Loan , Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, fourth ed., 2013

    2013

  11. [19]

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

    1997

  12. [20]

    Gu and S

    M. Gu and S. C. Eisenstat , Efficient algorithms for computing a strong rank-revealing Q R factorization , SIAM J. Sci. Comput., 17 (1996), pp. 848–869, https://doi.org/10.1137/0917055

    1996 doi

  13. [21]

    Halko, P.-G

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

    2011

  14. [22]

    Harbrecht, M

    H. Harbrecht, M. Peters, and R. Schneider , On the low-rank approximation by the pivoted Cholesky decomposition, Appl. Numer. Math., 62 (2012), pp. 428–440, https://doi.org/10.1016/j.apnum.2011.10. 001

    2012 doi

  15. [23]

    M. W. Mahoney and P. Drineas , CUR matrix decompositions for improved data analysis , Proc. Natl. Acad. Sci. USA, 106 (2009), pp. 697–702, https://doi.org/10.1073/pnas.0803205106

    2009 doi

  16. [24]

    Massei , Some algorithms for maximum volume and cross approximation of symmetric semidefinite matri- ces, BIT, 62 (2022), pp

    S. Massei , Some algorithms for maximum volume and cross approximation of symmetric semidefinite matri- ces, BIT, 62 (2022), pp. 195–220, https://doi.org/10.1007/s10543-021-00872-1

    2022 doi

  17. [25]

    Osinsky , Close to optimal column approximations with a single SVD , arXiv preprint arXiv:2308.09068, (2023)

    A. Osinsky , Close to optimal column approximations with a single SVD , arXiv preprint arXiv:2308.09068, (2023)

    2023 arXiv

  18. [26]

    Peherstorfer, D

    B. Peherstorfer, D. Butnaru, K. Willcox, and H.-J. Bungartz , Localized discrete empirical interpolation method, SIAM J. Sci. Comput., 36 (2014), pp. A168–A192, https://doi.org/10.1137/130924408

    2014 doi

  19. [27]

    A. K. Saibaba , Randomized discrete empirical interpolation method for no nlinear model reduction , SIAM J. Sci. Comput., 42 (2020), pp. A1582–A1608, https://doi.org/10.1137/19M1243270

    2020 doi

  20. [28]

    Shitov , Column subset selection is NP-complete , Linear Algebra Appl., 610 (2021), pp

    Y. Shitov , Column subset selection is NP-complete , Linear Algebra Appl., 610 (2021), pp. 52–58, https:// doi.org/10.1016/j.laa.2020.09.015

    2021 doi

  21. [29]

    D. C. Sorensen and M. Embree , A DEIM induced CUR factorization , SIAM J. Sci. Comput., 38 (2016), pp. A1454–A1482, https://doi.org/10.1137/140978430

    2016 doi

  22. [30]

    Townsend and L

    A. Townsend and L. N. Trefethen , An extension of Chebfun to two dimensions , SIAM J. Sci. Comput., 35 (2013), pp. C495–C518, https://doi.org/10.1137/130908002

    2013 doi

  23. [31]

    Voronin and P.-G

    S. Voronin and P.-G. Martinsson , Efficient algorithms for cur and interpolative matrix decomp ositions, Adv. Comput. Math., 43 (2017), pp. 495–516, https://doi.org/10.1007/s10444-016-9494-8

    2017 doi

  24. [32]

    C. K. I. Williams and M. Seeger , Using the Nystr¨ om method to speed up kernel machines , in Annual Ad- vances in Neural Information Processing Systems 13: Procee dings of the 2000 Conference, 2001, pp. 682– 688

    2000

Pith tools

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