Pith. sign in

REVIEW 2 major objections 6 minor 2 cited by

Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices

T0 review · 2 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read CCEQR is a deterministic variant of column-pivoted QR that provably selects the same columns as the Golub-Businger algorithm while shifting most work to level-3 BLAS, giving order-of-magnitude speedups on very wide matrices with decaying…

desk verdict Genuinely new deterministic CPQR blocking with a solid equivalence proof; speedups are real in the intended regime, but the favorable-regime condition is under-specified. read the letter →

arxiv 2501.18035 v1 pith:4GVCFSXX submitted 2025-01-29 math.NA cs.NA

Robin Armstrong , Anil Damle This is my paper · ORCID
classification math.NAcs.NA MSC 65F2565F3062H3082-08
keywords columnsubsetselectioncolumn-pivotedQRGolub-BusingeralgorithmGEQP3compactWYformlevel-3BLASspectralclusteringWannierbasis
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

The paper proposes CCEQR, a column selection routine for matrices with far more columns than rows. Column subset selection asks for a small set of representative columns whose span approximates the whole matrix, and the standard workhorse for this is Golub-Businger column-pivoted QR. CCEQR provably returns the same column choice as Golub-Businger, but instead of applying every Householder reflector to every column it cycles through collect, commit, and expand steps, limiting slow matrix-vector (BLAS-2) work to a small candidate block and pushing most updates through fast matrix-matrix (BLAS-3) operations. On spectral clustering and Wannier-basis problems, where column norms decay rapidly, the authors report runtimes up to roughly 24 times faster than the LAPACK implementation, while on unstructured or equal-norm matrices CCEQR remains within about a factor of two. The equivalence proof is deterministic and needs no structural assumption, so the speed advantage is the only part that depends on the problem's column-norm profile.

What carries the argument

At the core is the collect-commit-expand cycle, which splits columns into three blocks: committed skeleton columns, tracked columns whose residual norms after projecting out the skeleton are maintained, and untracked columns for which only the original norm is stored. The collect step sorts tracked columns by residual norm, takes the top fraction $\rho$ as candidates, and runs GEQP3 on just that candidate block. The commit step promotes candidates using the threshold $c=\max\{i : |\hat R(i,i)|^2 \ge \max(\delta,\mu)\}$, where $\hat R$ is the candidate block's R-factor, $\delta$ is the largest non-candidate tracked residual, and $\mu$ is the largest untracked norm; this condition is exactly what prevents a non-candidate from overtaking the greedy order. New Householder reflectors are folded into the global unitary factor in compact WY form $Q = I - VTV^*$, so later applications are level-3 BLAS operations, and the expand step pulls in all untracked columns whose norms exceed the new tracked maximum, restoring invariant (3.1) that guarantees the next cycle commits at least one column. Together these pieces reproduce the Golub-Businger permutation without ever updating all $n$ columns at every pivot step.

What would settle it

Run Algorithm 3.5 and Algorithm 2.1 in exact arithmetic on a fixed rational matrix and compare the permutations; if CCEQR's $p$ cannot be completed to GB($k$) form by some unitary $Q$, Theorem 3.2 is false. For the speed claim, take a family of wide matrices with a fixed rate of column-norm decay and let $n$ grow; if the fraction of columns that ever become tracked does not shrink, or the runtime ratio of GEQP3 to CCEQR stops growing with $n$, the advertised speed advantage fails.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.2: on any matrix, in exact arithmetic, the permutation vector returned by CCEQR is equivalent to the one computed by the Golub-Businger algorithm, meaning there exists a unitary $Q$ such that $Q^*A(:,p)$ is in GB($k$) form. Equivalently, CCEQR selects exactly the same skeleton columns as GEQP3. It does this by maintaining an invariant: after each cycle, the largest residual norm among tracked columns is at least as large as any untracked column's original norm, and the commit step only accepts a candidate column when its diagonal R entry dominates both the best non-candidate residual and the best untracked norm. The efficiency comes from limiting BLAS-2 Householder application to the small candidate block and applying BLAS-3 operations only to the tracked set; a CSSP-only mode further avoids forming the full R. On structured test problems from spectral demixing and density functional theory, the reported speedups over GEQP3 reach roughly one to two orders of magnitude, while on Gaussian random and adversarial Hadamard matrices CCEQR remains within about a factor of two.

Load-bearing premise

The speed advantage rests on the data having most column-norm mass concentrated in a small number of columns; when many columns have comparable norms, the expand step pulls almost all columns into the tracked set and CCEQR runs slower than GEQP3.

Editorial extensions

If this is right

  • Applications that currently call GEQP3 for column selection, such as spectral clustering and DEIM-based model reduction, can switch to CCEQR without changing the selected columns, as long as only the permutation is needed.
  • For matrices with rapidly decaying column norms, the speedup grows as the number of columns grows: in the spectral demixing tests, CCEQR beats GEQP3 once $n$ reaches about $10^4$ columns, with reported ratios up to roughly 15 in the CSSP-only setting.
  • A full CPQR factorization can still be produced by applying the final reflections to the untracked columns, and the authors report smaller but still positive speedups in this mode.
  • The user parameter $\rho$, which controls candidate block size, has a broad plateau of good values, but very small or very large values degrade performance by inflating tracked sets or candidate blocks.
  • On unstructured Gaussian matrices CCEQR retains the same $O(n)$ scaling as GEQP3 for fixed row count and is only modestly slower, so the method does not sacrifice asymptotic scaling in the worst case.

Reading between the lines

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

  • A natural extension the paper leaves implicit: the gap between the largest candidate residual and the largest non-candidate residual controls how many columns each cycle can commit, and a future implementation could measure this gap online and adapt $\rho$ or the expansion threshold accordingly.
  • Because untracked columns enter CCEQR only through their original norms, the algorithm is plausibly adaptable to streaming or out-of-core settings where columns are read once and then discarded; the paper does not discuss this extension.
  • The equivalence theorem holds in exact arithmetic; in floating point, nearly tied column norms such as the Hadamard construction with machine-epsilon tie-breaking are the boundary where CCEQR and GEQP3 could diverge, so downstream applications with ties should compare the two choices empirically.
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 / 6 minor

Summary. The paper introduces CCEQR, a deterministic variant of the Golub-Businger CPQR algorithm aimed at matrices with far more columns than rows. The algorithm proceeds in cycles: a "collect" step selects a small candidate block from the tracked columns by residual norm; a "commit" step uses a GEQP3 factorization of the candidates to extend the skeleton by a provably safe number of columns; an "expand" step restores the invariant that the maximum tracked residual dominates all untracked column norms by moving sufficiently large untracked columns into the tracked set. The main theoretical claim is Theorem 3.2: the permutation returned by CCEQR is equivalent to that of Algorithm 2.1 in the sense that Q* A(:,p) is in GB(k) form for some unitary Q. Experiments on spectral demixing and DFT/Wannier-basis problems report order-of-magnitude speedups over GEQP3 in favorable regimes, while Gaussian and adversarial Hadamard matrices show comparable or slower runtimes. A Julia implementation and reproduction code are provided.

Significance. If the correctness claim holds, this is a useful contribution to numerical linear algebra: it gives a deterministic, blocked CPQR-based column selection method for extremely wide matrices, with a self-contained proof in exact arithmetic and an honest experimental evaluation. The paper clearly identifies favorable and unfavorable regimes, and it provides open-source code. The central theorem is defensible, but the pseudocode and proof contain local inconsistencies that must be fixed. The efficiency benefit is heuristic and structure-dependent, not a worst-case guarantee, and the paper is appropriately transparent about this.

major comments (2)
  1. [Algorithm 3.3 / Theorem 3.2] The quantity c defined in Algorithm 3.3, line 2 as c = max{i>=1 : |bR(i,i)|^2 >= delta or mu} is not capped at k-s, even though the proof of Theorem 3.2 asserts c is in [1, k-s] and uses this to conclude that s_T = k for some T <= k. Since bR can have up to min(m-s,b) nonzero diagonals and b may exceed k-s, c can overshoot the remaining skeleton size; for example, with k=1 and two orthonormal candidate columns, c can equal 2. The returned prefix is still GB(k) when s_T > k, so the theorem is repairable, but the pseudocode and proof should be aligned, for instance by setting c <- min(c, k-s) after line 2 of Algorithm 3.3 or by explicitly allowing s_T >= k in the induction.
  2. [Algorithms 3.2 and 3.3] The pseudocode does not match the text and the proof in two places. First, Section 3.2 states that the first cycle sets t <- b+1, but Algorithm 3.2 line 5 sets t <- b; since delta is computed before line 5, the proof's characterization of delta as the maximum over non-candidate tracked columns no longer matches the described algorithm. Second, Algorithm 3.3 line 11 reads 'c <- c - t' and should read 't <- t - c'; as printed, the tracked-set size is never reduced after a commit, which would break the partition invariant used by Lemma 3.1 and the subsequent expand step. These are local fixes, but they are necessary for the printed pseudocode to implement the proven algorithm.
minor comments (6)
  1. [Section 1 and Figure 4.1] The paper states that the favorable regime is characterized by column-norm concentration, but the quantity that actually controls the tracked-set size is the decay of residual norms after orthogonalization; Figure 4.1's own 'islands' show that strong initial concentration can still force nearly all columns into the tracked set. The paper discusses this honestly in Section 4.1, but it would help to state explicitly in Section 1 that the column-norm condition is a heuristic, and to mention a possible diagnostic such as monitoring M/t.
  2. [Algorithm 3.5] Line 7 of Algorithm 3.5 calls 'Exand' instead of 'Expand'; this typo should be corrected.
  3. [Theorem 3.2] The theorem states 'Let p in [n]^k be the permutation vector returned by Algorithm 3.5', but Algorithm 3.5 returns a permutation vector of length n, not k. Please clarify the notation so that p denotes the full permutation vector and A(:,p(1:k)) the selected columns.
  4. [Appendix B] In Appendix B, the text first says 'By construction, V2 is upper-triangular with unit diagonal' and then, in the proof of Lemma B.1, says 'Because V2 is a lower-triangular m x (s+c) matrix with unit diagonal'. The latter is correct for Householder vectors; the former statement should be fixed.
  5. [Section 4] The runtime plots report only medians and no measure of spread. Since CCEQR's runtime is highly variable in the island regime (Figure 4.1), reporting error bars or at least stating the variability would strengthen the experimental claims.
  6. [Section 4.2] The text says 'a system of m elections' where 'electrons' is meant; please correct this typo.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 3.2 is proved from the definition of GB(k) form and the external GEQP3 subroutine; self-citations are motivational only.

full rationale

The paper's central claim (Theorem 3.2) is that Algorithm 3.5 returns a permutation p for which there exists a unitary Q such that Q* A(:,p) has GB(k) form, i.e., is equivalent to the Golub-Businger permutation. This is proved inductively via Lemma 3.1, with the detailed proof in Appendix A. The proof uses only (i) the defining property of GEQP3 that its R-factor is in GB(d) form, (ii) the maintained invariant (3.1) that the maximum tracked residual dominates untracked norms, and (iii) the threshold definition of c in eq. (3.3), which compares candidate pivot values against non-candidate residual norms δ and untracked norms μ. None of these ingredients is the conclusion of Theorem 3.2; the theorem is not assumed in the construction of c, δ, or μ. The algorithm does use GEQP3 as a subroutine on the small candidate block, but GEQP3 is also the external LAPACK baseline against which runtime is compared; using a standard, independently implemented factorization routine as a building block is not circular. No parameter is fit to the data: ρ is user-set and swept in Figures 4.1-4.4, and no fitted model is later relabeled as a prediction. The self-citations [9] and [10] are cited only to motivate the spectral clustering and DFT test problems; they do not supply any load-bearing step in the correctness proof or in the runtime comparison. The paper is explicit that the efficiency gain depends on a structural condition (Section 1 and Figures 4.1-4.6) and is honest about the residual-norm 'islands' in Section 4.1 and the adversarial Hadamard case in Section 4.4; these are efficiency robustness limitations, not circular derivation. There is also a minor pseudocode/proof mismatch in Algorithm 3.3 regarding an upper bound on c, but that is a correctness nit, not a circularity. Accordingly, no step of the claimed derivation chain reduces to its own input.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The central correctness proof relies only on standard linear algebra facts about Householder reflections, compact WY forms, and the definition of GB(k) form. No new entities are introduced. The only free parameter is rho, which controls performance but not correctness.

free parameters (1)
  • rho (candidate block fraction) = user-set; swept from 1e-5 to 1e-1 in experiments
    Controls the candidate block size b = 1 + floor(rho (t-1)). It does not affect correctness but directly controls the amount of BLAS-2 work and the frequency of expand steps; the paper shows a broad range works but the best value depends on the matrix.
assumptions (4)
  • standard math Householder reflection properties (Section 2.3)
    Used to construct Q and apply rotations; standard linear algebra fact.
  • standard math Compact WY representation exists and is computed by Schreiber-Van Loan (Appendix B)
    Relied on to apply Q with BLAS-3 in the commit and expand steps.
  • standard math Orthogonal projection does not increase vector norms
    Used in Lemma 3.1 cases 2b and 2c to bound residual norms of non-candidate and untracked columns by their pre-cycle norms.
  • standard math GEQP3 returns a factorization with R in GB(d) form (Definition 2.1)
    The collect step calls GEQP3 on the candidate block; the proof uses that its output has the greedy property.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices." pith.science (2026). https://pith.science/paper/4GVCFSXX

@misc{pith2026250118035,
  author       = {Pith},
  title        = {Pith review of: Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4GVCFSXX}},
  note         = {Machine review of arXiv:2501.18035}
}
read the original abstract

Column-pivoted QR (CPQR) factorization is a computational primitive used in numerous applications that require selecting a small set of ``representative'' columns from a much larger matrix. These include applications in spectral clustering, model-order reduction, low-rank approximation, and computational quantum chemistry, where the matrix being factorized has a moderate number of rows but an extremely large number of columns. We describe a modification of the Golub-Businger algorithm which, for many matrices of this type, can perform CPQR-based column selection much more efficiently. This algorithm, which we call CCEQR, is based on a three-step ``collect, commit, expand'' strategy that limits the number of columns being manipulated, while also transferring more computational effort from level-2 BLAS to level-3. Unlike most CPQR algorithms that exploit level-3 BLAS, CCEQR is deterministic, and provably recovers a column permutation equivalent to the one computed by the Golub-Businger algorithm. Tests on spectral clustering and Wannier basis localization problems demonstrate that on appropriately structured problems, CCEQR can significantly outperform GEQP3.

Figures

Figures reproduced from arXiv: 2501.18035 by the authors.

Figure 3
Figure 3. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 3.1
Figure 3.1. A schematic representation of CCEQR. In the “collect” stage, a set of [PITH_FULL_IMAGE:figures/full_fig_p009_3_1.png] view at source ↗
Figure 4
Figure 4. [PITH_FULL_IMAGE:figures/full_fig_p015_4.png] view at source ↗
Figures from the paper (8 more)
Figure 4.1
Figure 4.1. Figure 4.1: Left-panel: cumulative distribution of column norm mass in [PITH_FULL_IMAGE:figures/full_fig_p016_4_1.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 4.2
Figure 4.2. Figure 4.2: The same experiment as [PITH_FULL_IMAGE:figures/full_fig_p017_4_2.png]
Figure 4.3
Figure 4.3. Figure 4.3: Left: median runtimes for CCEQR and GEQP3 over 10 trials on electronic [PITH_FULL_IMAGE:figures/full_fig_p018_4_3.png]
Figure 4
Figure 4. Figure 4 [PITH_FULL_IMAGE:figures/full_fig_p018_4.png]
Figure 4.4
Figure 4.4. Figure 4.4: The same experiment as in [PITH_FULL_IMAGE:figures/full_fig_p019_4_4.png]
Figure 4.5
Figure 4.5. Figure 4.5: Median runtimes for CCEQR and GEQP3 over 10 trials on test matrices [PITH_FULL_IMAGE:figures/full_fig_p020_4_5.png]
Figure 4.6
Figure 4.6. Figure 4.6: Median runtimes of CCEQR and GEQP3 over 10 trials on an “adversarial” [PITH_FULL_IMAGE:figures/full_fig_p021_4_6.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. Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows

    math.NA 2026-07 conditional novelty 7.0 of 10

    Bischof-Stewart pivoting on orthonormal-row matrices provably yields strong rank-revealing QR factorizations, and a randomized variant attains the same column-selection bounds with large practical speedups.

  2. Anatomy of High-Performance Column-Pivoted QR Decomposition

    cs.MS 2025-07 conditional novelty 6.0 of 10

    A randomized, modular QR-with-column-pivoting framework (BQRRP) is shown to run up to two orders of magnitude faster than LAPACK's GEQP3 on AMD CPUs and near unpivoted-QR speed on an H100 GPU, in the authors' open-sou...

Reference graph

Works this paper leans on

41 extracted references · 39 canonical work pages · cited by 2 Pith papers

  1. [1]

    Structure-Aware Analyses and Algorithms for Interpolative Decompositions

    R. Armstrong, A. Buzali, and A. Damle , Structure-aware analyses and algorithms for interpolative decompositions, 2023, https://arxiv.org/abs/2310.09452

    work page Pith review arXiv 2023

  2. [2]

    Benzi, P

    M. Benzi, P. Boito, and N. Razouk, Decay properties of spectral projectors with applications to electronic structure, SIAM Review, 55 (2013), pp. 3–64

    work page 2013

  3. [3]

    Bischof and C

    C. Bischof and C. V an Loan, The WY representation for products of Householder matrices , SIAM Journal on Scientific and Statistical Computing, 8 (1987), pp. s2–s13

    work page 1987

  4. [4]

    C. H. Bischof , A parallel QR factorization algorithm with controlled local pivoting , SIAM Journal on Scientific and Statistical Computing, 12 (1991), pp. 36–57

    work page 1991

  5. [5]

    Businger and G

    P. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numerische Mathematik, 7 (1965), pp. 269 – 276

    work page 1965

  6. [6]

    Chandrasekaran and I

    S. Chandrasekaran and I. C. F. Ipsen , On rank-revealing factorisations , SIAM Journal on Matrix Analysis and Applications, 15 (1994), pp. 592–622

    work page 1994

  7. [7]

    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

    work page 2010

  8. [8]

    Damle, S

    A. Damle, S. Glas, A. Townsend, and A. Yu , How to reveal the rank of a matrix? , 2024, https://arxiv.org/abs/2405.04330

    arXiv 2024

Show all 41 references
  1. [9]

    Damle, L

    A. Damle, L. Lin, and L. Ying, Compressed representation of Kohn-Sham orbitals via selected columns of the density matrix , J Chem Theory Comput, 14 (2015), pp. 1463–1469

    2015

  2. [10]

    Damle, V

    A. Damle, V. Minden, and L. Ying, Simple, direct and efficient multi-way spectral clustering, Information and Inference: A Journal of the IMA, 8 (2018), pp. 181–203

    2018

  3. [11]

    J. W. Demmel, L. Grigori, M. Gu, and H. Xiang , Communication avoiding rank revealing QR factorization with column pivoting , SIAM Journal on Matrix Analysis and Applica- tions, 36 (2015), pp. 55–89

    2015

  4. [12]

    Deshpande and L

    A. Deshpande and L. Rademacher , Efficient volume sampling for row/column subset selec- tion, in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 329–338

    2010

  5. [13]

    Deshpande, L

    A. Deshpande, L. Rademacher, S. Vempala, and G. W ang , Matrix approximation and projective clustering via volume sampling, in Proceedings of the Seventeenth Annual ACM- SIAM Symposium on Discrete Algorithm, SODA ’06, USA, 2006, Society for Industrial and Applied Mathematics, ...

    2006

  6. [14]

    Drineas, M

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

    2008

  7. [15]

    Drmaˇc and Z

    Z. Drmaˇc and Z. Bujanovi ´c, On the failure of rank-revealing QR factorization software – a case study, ACM Trans. Math. Softw., 35 (2008)

    2008

  8. [16]

    Drma ˇc and S

    Z. Drma ˇc and S. Gugercin , A new selection operator for the discrete empirical interpola- tion method—improved a priori error bound and extensions , SIAM Journal on Scientific Computing, 38 (2016), pp. A631–A648

    2016

  9. [17]

    J. A. Duersch and M. Gu, Randomized QR with column pivoting , SIAM Journal on Scientific Computing, 39 (2017), p. C263–C291

    2017

  10. [18]

    Frieze, R

    A. Frieze, R. Kannan, and S. Vempala , Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51 (2004), p. 1025–1041

    2004

  11. [19]

    G. H. Golub, V. Klema, and G. Stewart, Rank degeneracy and least squares problems, Tech. Report STAN-CS-76-559, Stanford University, 1976

    1976

  12. [20]

    G. H. Golub and C. F. V. Loan , Matrix Computations , Johns Hopkins University Press, fourth ed., 2013

    2013

  13. [21]

    Greengard and J

    L. Greengard and J. Strain , The fast Gauss transform , SIAM Journal on Scientific and Statistical Computing, 12 (1991), pp. 79–94

    1991

  14. [22]

    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

  15. [23]

    Halko, P

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

    2011

  16. [24]

    Hong and C.-T

    Y. Hong and C.-T. Pan, Rank-revealing QR factorizations and the singular value decomposi- tion, Mathematics of Computation, 58 (1992), pp. 213 – 232

    1992

  17. [25]

    Kahan, Numerical linear algebra, Canad

    W. Kahan, Numerical linear algebra, Canad. Math. Bull., 9 (1966), pp. 757–801

    1966

  18. [26]

    Liberty, F

    E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert, Randomized algo- rithms for the low-rank approximation of matrices , Proceedings of the National Academy 22 of Sciences, 104 (2007), pp. 20167–20172

    2007

  19. [27]

    Lin and J

    L. Lin and J. Lu , A Mathematical Introduction to Electronic Structure Theory , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019

    2019

  20. [28]

    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

  21. [29]

    Martinsson, G

    P.-G. Martinsson, G. Quintana Ort ´I, N. Heavner, and R. van de Geijn , Householder QR factorization with randomization for column pivoting (HQRRP) , SIAM Journal on Scientific Computing, 39 (2017), pp. C96–C115

    2017

  22. [30]

    Murray, J

    R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezi ´nski, M. E. Lopes, T. Liang, H. Luo, and J. Don- garra, Randomized numerical linear algebra : A perspective on the field with an eye to software, 2023, https:/...

    2023 arXiv

  23. [31]

    Quintana-Ort´ı, X

    G. Quintana-Ort´ı, X. Sun, and C. H. Bischof , A BLAS-3 version of the QR factorization with column pivoting , SIAM Journal on Scientific Computing, 19 (1998), pp. 1486–1494

    1998

  24. [32]

    A. K. Saibaba , Randomized discrete empirical interpolation method for nonlinear model re- duction, SIAM Journal on Scientific Computing, 42 (2020), pp. A1582–A1608

    2020

  25. [33]

    Schiebinger, M

    G. Schiebinger, M. J. W ainwright, and B. Yu, The geometry of kernelized spectral cluster- ing, The Annals of Statistics, 43 (2015), pp. 819 – 846

    2015

  26. [34]

    Schreiber and C

    R. Schreiber and C. V an Loan, A storage-efficient WY representation for products of House- holder transformations, SIAM Journal on Scientific and Statistical Computing, 10 (1989)

    1989

  27. [35]

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

    2016

  28. [36]

    Vershynin, Four lectures on probabilistic methods for data science , in The Mathematics of Data, American Mathematical Society, 2018, pp

    R. Vershynin, Four lectures on probabilistic methods for data science , in The Mathematics of Data, American Mathematical Society, 2018, pp. 231–271

    2018

  29. [37]

    von Luxburg , A tutorial on spectral clustering , Statistics and Computing, 17 (2007), pp

    U. von Luxburg , A tutorial on spectral clustering , Statistics and Computing, 17 (2007), pp. 395–416

    2007

  30. [38]

    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

  31. [39]

    C ¸ ivril and M

    A. C ¸ ivril and M. Magdon-Ismail, On selecting a maximum volume sub-matrix of a matrix and related problems, Theoretical Computer Science, 410 (2009), pp. 4801–4811. Appendix A. Proof of Lemma 3.1. Let Q, Π be the CPQR factors at the beginning of a given cycle of CCEQR, and d...

    2009

  32. [40]

    For i ≤ s we rely on the fact that R(1)(i, i) = R(0)(i, i), and we consider two sub-cases. 1a. If j ≤ s or j > s + t then ∥R(1)(i : m, j)∥2 = ∥R(0)(i : m, j)∥2, as R(1)(i : m, j) differs from R(0)(i : m, j) by a rotation in the lower m − s indices. This means that (A.1) follow...

  33. [41]

    For s < i≤ s + c, we again consider sub-cases based on j. 2a. If j ≤ s + b then R(1)(i, i) = bR(i − s, i− s) R(1)(i : m, j) = bR((i − s) : (m − s), j− s)). In this case, (A.1) holds because GEQP3 outputs bR in GB(d) form (with d = min{m − s, b}). 2b. If s + b < j≤ s + t then, ...

Pith tools

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