Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings

T0 review · 4 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that sketching a wide matrix, selecting pivots from the sketch, and then selecting from the induced original columns yields a strong rank-revealing QR factorization whose bounds depend on the sketch size rather than the…

desk verdict New right-sketching CSSP idea with a real proof gap around the adaptivity of the sparse embedding; worth refereeing, but the n-independent theorem is not established as stated. read the letter →

arxiv 2509.03198 v3 pith:5GRIMGFN submitted 2025-09-03 math.NA cs.NA

Israa Fakih , Laura Grigori This is my paper · ORCID
classification math.NAcs.NA MSC 65F2565F5568W2065F30
keywords columnsubsetselectionstrongrank-revealingQRrandomizednumericallinearalgebrasparsesubspaceembeddingsCountSketchleveragescoresparsificationlow-rankapproximationLUwithpanelrankrevealingpivoting
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

This paper introduces SE-QRCS, a randomized column-selection method for wide matrices $d \times n$ with $d \ll n$. It claims that if strong rank-revealing QR is applied first to the sketched matrix $B = A\Omega^T$ and then to the induced set $\tilde{A}_1$ of original columns, the resulting QR factorization of $A$ is itself strong rank-revealing: its singular-value ratios are bounded by $\rho_1$ and $\rho_2$ that depend on the sketch dimensions $l$ and $p$ rather than on the matrix width $n$. The practical payoff is that selecting $k$ columns this way costs $O(d(lk'+pk)+sdn)$ instead of the $O(dnk)$ of deterministic strong RRQR, making spectrum-revealing column selection feasible for very wide matrices. The paper also shows that with leverage-score-based non-oblivious embeddings the bounds become independent of $n$, and demonstrates in experiments that the selected columns approximate the spectrum about as well as ordinary QRCP.

What carries the argument

The load-bearing object is the sparse embedding $\Omega \in \mathbb{R}^{l \times n}$ with $s$ nonzeros per column, together with the induced column set $\tilde{A}_1$. The sparsity makes each sketched column of $B=A\Omega^T$ a combination of at most $s$ original columns, so the pivots found by strong RRQR on $B$ map back to a small set of original columns of size $p \approx n[1-(1-k/l)^s]$ in expectation. The proof is carried by the block identity of Lemma 4.2, which expresses $\tilde{Q}^T \tilde{A}_2 \Omega_{22}$ in terms of $N=(R^B_{11})^{-1}R^B_{12}$ and a coupling term $C$, and by Lemma 4.4, which bounds $\alpha^2 + \|[I \; R_{11}^{-1}R_{12}]\|_2^2$ by a product of the two strong-RRQR bounds coming from $B$ and $\tilde{A}_1$; that product transfers the rank-revealing property of the two small factorizations to $A$ itself.

What would settle it

Run SE-QRCS with a CountSketch embedding on a $50 \times 10^6$ matrix with $k=30$ and $l=2d\log d$, and record $p$ over many trials. If $p \le l$ occurs with non-negligible frequency in this advertised regime, the $p>l$ premise of Remark 4.3 is violated: the stated $n$-independent $\rho_1,\rho_2$ bounds do not follow from the given proof, and the observed singular-value ratios become the quantity that would settle the method's practical guarantee.

Watch

Extended reading notes

Core claim

Let $\Omega$ be a sparse oblivious subspace embedding of $\mathrm{range}(A^T)$, set $B = A\Omega^T$, and apply strong RRQR to $B$ with rank $k' \ge k$. Because each sketched column is a combination of only $s$ original columns, the $k'$ pivots of $B$ expand to a set $\tilde{A}_1$ of $p$ original columns; strong RRQR on $\tilde{A}_1$ then produces $R_{11}$ and the permutation $\Pi$. The resulting factorization $A\Pi = Q \begin{bmatrix} R_{11} & R_{12} \\ 0 & R_{22} \end{bmatrix}$ satisfies $1 \le \sigma_i(A)/\sigma_i(R_{11})$ and $\sigma_j(R_{22})/\sigma_{j+k}(A) \le \rho_1$ with $\rho_1 = \sqrt{1 + \frac{4(1+\epsilon)}{1-\epsilon}(1+f^2 k(p-k))(1+f^2 k'(l-k'))}$, and $\|R_{11}^{-1}R_{12}\|_2 \le \rho_2$ with the analogous expression. The spectral-revealing quality therefore depends on the sketch dimension $l$ and the induced-set size $p$, not on $n$; with leverage-score-based LESS embeddings the bounds become $O\left( k \sqrt{k'} \log^4(d) (d/\epsilon^2 - k')^{1/2} / (\epsilon^4 (1-\epsilon)^{1/2}) \right)$, independent of $n$. The pivot-selection work is $O(d(lk'+pk)+sdn)$.

Load-bearing premise

The main theorem assumes $p>l$: the submatrix of the sparse embedding restricted to the selected columns must still be an oblivious subspace embedding for the row space of $\tilde{A}_1$; the paper controls only the expectation of $p$ and gives no high-probability bound ensuring $p>l$.

Editorial extensions

If this is right

  • For any wide matrix, SE-QRCS selects $k$ columns and returns a factorization whose singular-value ratios are bounded by quantities depending on $l$ and $p$, so the spectral approximation does not degrade as $n$ grows.
  • The pivot-selection cost $O(d(lk'+pk)+sdn)$ replaces the $O(dnk)$ of deterministic strong RRQR, with reported runtime reductions of factors around 7 to 10 in the experiments.
  • When leverage scores are known or can be approximated, using LESS embeddings makes the bound independent of $n$ entirely, at the cost of the extra leverage-score estimation step.
  • The selected columns give a low-rank approximation with $\|A-CC^+A\|_2 \le \rho_1 \sigma_{k+1}(A)$, matching the strong-RRQR guarantee but with $\rho_1$ tied to sketch sizes.
  • Plugging SE-QRCS into LU with panel rank-revealing pivoting produces stable growth factors on random and special matrices for block sizes $b \ge 16$.

Reading between the lines

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

  • The theorem's advertised $n$-independence rests on the unproven condition $p>l$; a high-probability lower bound on $p$, derived from the OSNAP/balls-and-bins distribution, would close the gap and make the guarantee unconditional for CountSketch with $l=O(d\log d)$.
  • The two-level selection can be iterated: sketching $\tilde{A}_1$ again and running sRRQR on the new induced set would shrink the dominant $dkp$ term at the cost of one extra sparse pass, though the block identities of Lemma 4.2 would need to be composed across levels.
  • A direct stress test is the Kahan matrix, where greedy QRCP is known to lose rank revelation; checking whether SE-QRCS stays as close to QRCP there as it does on Fiedler and Prolate matrices would show whether the method is a safe drop-in accelerator for rank-revealing factorizations.
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

4 major / 5 minor

Summary. The paper introduces SE-QRCS, a column subset selection algorithm for wide matrices A in R^{d x n}. The method sketches A from the right with a sparse embedding Omega, computes a strong rank-revealing QR factorization of the sketched matrix B = A Omega^T, maps the selected pivots back to columns of A to form a reduced matrix A1 of p columns, and then computes a strong RRQR factorization of A1 to select the final k columns. The main theoretical claim (Theorem 4.5) is that the resulting QR factorization of A satisfies strong rank-revealing inequalities with constants depending on p and l rather than n; a variant using non-oblivious leverage-score sparsified embeddings is claimed to give bounds independent of n. Numerical experiments compare the singular values and runtimes with QRCP, and an application to LU_PRRP is reported.

Significance. If the main theorem were fully justified, the paper would give a useful randomized strong-RRQR column selection method with reduced dependence on the large column dimension and with explicit algorithmic structure exploiting sparse embeddings; the application to LU_PRRP adds practical value. The paper is also careful to state the relevant embedding definitions and to situate the result relative to prior randomized QRCP and strong RRQR work. However, the central proof has load-bearing gaps: Theorem 4.5 omits the p > l condition on which its proof relies, p is only controlled in expectation, and the proof uses the same sketch both to select and to embed an Omega-dependent subspace. Because these gaps concern exactly the mechanism by which the n-independent bounds are derived, the advertised guarantee is not established as stated. The numerical evidence is suggestive but tests a QRCP-based variant rather than the analyzed strong RRQR algorithm.

major comments (4)
  1. [Section 4, Theorem 4.5 and Remark 4.3] The statement of Theorem 4.5 contains no assumption on p, yet the proof explicitly says 'For the remainder of this section, we assume that p > l' when bounding ||\tilde A1 [Omega11 Omega12]||_2 via (19). Since p is the random number of columns in \tilde A1 and Proposition 3.2 only provides E[p] = n(1 - (1 - k'/l)^s) with no high-probability concentration bound, the theorem is not a valid high-probability statement in general. In the Countsketch regime used in the experiments (l = O(d^2/epsilon^2), s = 1), E[p] = n k'/l can be well below l, so the advertised n-independent bound is not proven for the tested parameter regime. The theorem must either incorporate the event p > l with a tail bound or prove the bound under the second case of Remark 4.3 with its own high-probability estimate.
  2. [Section 4, Lemma 4.4 and Definition 2.10] The proof of Lemma 4.4 invokes 'using 4.3' to treat [Omega11 Omega12] as an oblivious subspace embedding for range(\tilde A1^T). However, \tilde A1 is the set of columns selected by the strong RRQR factorization of B = A Omega^T, so both the subspace range(\tilde A1^T) and the restricted sketch [Omega11 Omega12] are functions of the same Omega. Definition 2.10 guarantees the embedding property only for a fixed subspace chosen independently of the sketch, and Remark 4.1's claim that 'any subset of columns of Omega' is an OSE is a statement for a fixed subset, not a simultaneous guarantee over the Omega-dependent selection event. The condition p > l does not remove this dependence; what is needed is an independent fresh sketch of \tilde A1 or an explicit union-bound argument over candidate subsets. This gap is load-bearing because it produces the (1+epsilon)/(1-epsilon) factors in Lemma 4.4 and hence in Theorem 4.5.
  3. [Section 5.1 and Section 5.3] The numerical experiments do not test the algorithm as analyzed. The first paragraph of Section 5.1 states that the factorizations on B and \tilde A1 are 'performed using QR with column pivoting rather than strong RRQR', while Theorem 4.5 requires strong RRQR; similarly, the runtime speedups in Figures 22-23 compare SE-QRCS against QRCP, not against the deterministic strong RRQR algorithm to which the complexity claims refer. The paper should either implement strong RRQR in the experiments or explicitly present the numerical results as evidence for a heuristic variant, with the theoretical guarantees left as a separate statement.
  4. [Section 3.2 and Table 1] The complexity claims are inconsistent as stated. Section 3.2 gives O(d(lk' + pk + ns)) for pivot selection, Table 1 reports O(dpk + dn log(r)), and the introduction summarizes the bound as O(d(lk' + pk)); the relations among these expressions and the parameter regimes in which each holds are never stated. In particular, the sentence 'checking the worst case where k' = d, dpk' = nd^2/2' appears to replace p by n without justification. Please provide one precise complexity statement with all parameter assumptions.
minor comments (5)
  1. [Corollary 2.9, Eq. (13)] Equation (13) has a sign error: the lower bound should use sqrt(1 - epsilon), not sqrt(1 + epsilon), in analogy with (12).
  2. [Section 4, notation] The matrices Omega11, Omega12, Omega22 are used in Section 4 without restating the block definitions of \barOmega from Section 3.1; please use \barOmega11, \barOmega12, \barOmega22 consistently or redefine them at the start of Section 4.
  3. [Remark 4.3] The first bullet states 'If p >= l' but the subsequent paragraph assumes 'p > l'; please reconcile the boundary case, and note that the second bullet's 'balls and pins' analogy is a typo for 'balls and bins'.
  4. [Algorithm 1, line 10] The pseudocode line 'R = [R(1:k,:) Q^T A2]' is ambiguous because R is both being assigned and read; it should refer explicitly to the entries of \tilde R from line 8 and to the product with \tilde A2.
  5. [Throughout] There are several typographical slips: 'presened' in Lemma 4.4, 'permuatation' in Theorem 4.6, and 'Wilkison' in Section 5.4; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SE-QRCS's strong-RRQR bound follows from external RRQR and embedding theorems; the conditioning and p>l issues are proof gaps, not circular reductions.

full rationale

The claimed derivation is not circular. Theorem 4.5 is proved from Lemma 4.4, which in turn uses the strong-RRQR lemmas of Gu-Eisenstat and of Demmel-Grigori-Gu-Xiang (Corollary 2.5 and Theorem 2.6) together with the oblivious-subspace-embedding property of Omega. Those cited results are external theorems whose assumptions do not include the SE-QRCS conclusion; the fact that one author of [11] is also an author here does not make the use circular, because the cited theorems are proved independently and are not the target result. The self-references [17] and [25] appear in the introduction and in the LU_PRRP application section, not as premises of the main rank-revealing proof. The proof's use of Remark 4.3 to treat the sketch restricted to the selected columns as an embedding for range(tilde A1^T) is a conditioning subtlety, since the selected subspace depends on the same Omega, and Theorem 4.5 omits the p > l assumption stated in Remark 4.3; these are correctness and proof gaps, not a reduction of the conclusion to the input. No fitted parameter is renamed as a prediction, and the p- and l-dependent rho bounds are genuinely derived quantities. Accordingly, no circular step is identified.

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

The central claim is a new algorithm, so no new physical or mathematical entities are introduced. The main load-bearing choices are the embedding distortion epsilon, the sRRQR constant f, the intermediate rank k', and the embedding sparsity s; none are fitted to the singular values of A. The most fragile mathematical premise is the p > l assumption used in the proof of Lemma 4.4, which is absent from the theorem statement and can fail for Countsketch in tested regimes.

free parameters (4)
  • epsilon
    Subspace embedding distortion, user-specified in (0,1); appears in all bounds and complexity trade-offs. It is not fitted to data.
  • f
    Strong RRQR constant greater than 1 inherited from Gu-Eisenstat; controls rho1 and rho2, user-chosen.
  • k'
    Rank used in sRRQR on the sketched matrix B; chosen at least k and large enough so p >= d (Remark 3.1); affects p and the final bounds.
  • sparsity s = 1 for Countsketch, 6 in experiments
    Number of nonzeros per column of Omega; chosen to satisfy oblivious subspace embedding theorems and to trade off sketch dimension l against the size p of the induced column set.
assumptions (4)
  • standard math Weyl's inequality and singular value interlacing give the conversion from Lemma 4.4 to the ratio bounds in Theorem 4.5.
    Invoked in the proof of Theorem 4.5 to bound sigma_i(A) by sigma_i(R11) times the norm of the mixing matrix.
  • domain assumption Omega in R^{l x n} is an (epsilon, delta, r)-oblivious sparse subspace embedding for range(A^T), with OSNAP requirements on l and s and hash independence from Nelson and Nguyen.
    The proof relies on singular value preservation of the sketch (Corollary 2.9 and Definition 2.10) as a black box.
  • ad hoc to paper p > l is assumed so that the restricted embedding [Omega11 Omega12] is an oblivious subspace embedding for range(A1^T) (Remark 4.3); this condition is not included in the statement of Theorem 4.5.
    The main bound in Lemma 4.4 uses the (1+epsilon) embedding factor for A1, which requires p >= l. For Countsketch, l = O(d^2/epsilon^2) and p can be below l in experiments.
  • domain assumption The number of original columns p in A1 is modeled by the balls-and-bins random variable n[1-(1-k'/l)^s], and only its expectation is used for complexity; the proof does not use a high-probability tail bound.
    Proposition 3.2 gives E(X) only; Lemma 4.4 and Theorem 4.5 treat p as a realized value. This leaves a gap between the probabilistic statement and the deterministic theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings." pith.science (2026). https://pith.science/paper/5GRIMGFN

@misc{pith2026250903198,
  author       = {Pith},
  title        = {Pith review of: Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5GRIMGFN}},
  note         = {Machine review of arXiv:2509.03198}
}
abstract

In this paper, we introduce an efficient algorithm for column subset selection that combines the column-pivoted QR factorization with sparse subspace embeddings. The proposed method, SE-QRCS, is particularly effective for wide matrices with significantly more columns than rows. Starting from a matrix $A$, the algorithm selects $k$ columns from the sketched matrix $B = A \Omega^T$, where $\Omega$ is a sparse oblivious subspace embedding for a subspace of dimension $rank(A)$. The sparsity structure of $\Omega$ is then exploited to map the selected pivots back to the corresponding columns of $A$, which are then used to produce the final subset of selected columns. We prove that this procedure yields a factorization with strong rank-revealing properties, thus revealing the spectrum of $A$. The resulting bounds exhibit a reduced dependence on the number of columns of $A$ compared to those obtained from the strong rank-revealing QR factorization of $A$. For general matrices, the algorithm can be extended by first applying an additional subspace embedding of $range(A)$.

Figures

Figures reproduced from arXiv: 2509.03198 by the authors.

Figure 1
Figure 1. Steps of the SE-QRCS algorithm sRRQR is applied to A˜ 1 yielding the factors Π˜ , Q, ˜ R˜ be for the chosen rank k, that is A˜ 1Π =˜ Q˜  R˜ 11 R˜ 12 0 R˜ 22 , (16) 9 [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Ratio of the first k sin￾gular values [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 6
Figure 6. Ratio of the first k sin￾gular values [PITH_FULL_IMAGE:figures/full_fig_p018_6.png] view at source ↗
Figures from the paper (8 more)
Figure 10
Figure 10. Figure 10: Matrix with exponential spectral decay [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]
Figure 12
Figure 12. Figure 12: Fiedler Matrix [PITH_FULL_IMAGE:figures/full_fig_p019_12.png]
Figure 14
Figure 14. Figure 14: Chebvand matrix. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_14.png]
Figure 15
Figure 15. Figure 15: Summary results of ratio for SE￾QRCS [PITH_FULL_IMAGE:figures/full_fig_p020_15.png]
Figure 17
Figure 17. Figure 17: Random outlier matrix [PITH_FULL_IMAGE:figures/full_fig_p021_17.png]
Figure 19
Figure 19. Figure 19: Fiedler Matrix [PITH_FULL_IMAGE:figures/full_fig_p021_19.png]
Figure 20
Figure 20. Figure 20: Summary results of ratio for SE￾QRCS Factorization [PITH_FULL_IMAGE:figures/full_fig_p021_20.png]
Figure 22
Figure 22. Figure 22: Random Matrix [PITH_FULL_IMAGE:figures/full_fig_p022_22.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. Accelerating the Canonical Polyadic Alternating Least Squares Optimization via a Randomized Interpolative Decomposition

    math.NA 2026-07 conditional novelty 6.0 of 10

    Randomized QR pivots of the target tensor supply a fixed leverage-score-like sampling for CPD-ALS, reducing tensor re-sampling and storage overhead.

Reference graph

Works this paper leans on

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

  1. [17]

    Randomized strong rank-revealing qr for column subset selection and low-rank matrix approximation.arXiv preprint arXiv:2503.18496, 2025

    Laura Grigori and Zhipeng Xue. Randomized strong rank-revealing qr for column subset selection and low-rank matrix approximation.arXiv preprint arXiv:2503.18496, 2025

    arXiv 2025

  2. [25]

    Lu factorization with panel rank revealing pivoting and its communication avoiding version.SIAM Journal on Matrix Analysis and Applications, 34(3):1401–1429, 2013

    Amal Khabou, James W Demmel, Laura Grigori, and Ming Gu. Lu factorization with panel rank revealing pivoting and its communication avoiding version.SIAM Journal on Matrix Analysis and Applications, 34(3):1401–1429, 2013

    work page 2013

  3. [1]

    Randomized gram–schmidt process with application to gmres

    Oleg Balabanov and Laura Grigori. Randomized gram–schmidt process with application to gmres. SIAM Journal on Scientific Computing, 44(3):A1450–A1474, 2022

    work page 2022

  4. [2]

    Communication avoiding low rank approximation based on qr with tournament pivoting

    Matthias Beaupère and Laura Grigori. Communication avoiding low rank approximation based on qr with tournament pivoting. 2021

    work page 2021

  5. [3]

    An improved approximation algorithm for the column subset selection problem

    Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. InProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 968–977. SIAM, 2009

    work page 2009

  6. [4]

    Linear least squares solutions by householder trans- formations

    Peter Businger and Gene H Golub. Linear least squares solutions by householder trans- formations. Numerische Mathematik, 7(3):269–276, 1965

    work page 1965

  7. [5]

    Rank revealing qr factorizations.Linear algebra and its applications, 88: 67–82, 1987

    Tony F Chan. Rank revealing qr factorizations.Linear algebra and its applications, 88: 67–82, 1987

    work page 1987

  8. [6]

    Some applications of the rank revealing qr factorization

    Tony F Chan and Per Christian Hansen. Some applications of the rank revealing qr factorization. SIAM Journal on Scientific and Statistical Computing, 13(3):727–741, 1992

    work page 1992

Show all 39 references
  1. [7]

    On rank-revealing factorisations.SIAM Journal on Matrix Analysis and Applications, 15(2):592–622, 1994

    Shivkumar Chandrasekaran and Ilse CF Ipsen. On rank-revealing factorisations.SIAM Journal on Matrix Analysis and Applications, 15(2):592–622, 1994

    1994

  2. [8]

    Optimal embedding dimension for sparse subspace embeddings

    Shabarish Chenakkod, Michał Dereziński, Xiaoyu Dong, and Mark Rudelson. Optimal embedding dimension for sparse subspace embeddings. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1106–1117, 2024

    2024

  3. [9]

    Nearly tight oblivious subspace embeddings by trace inequalities

    Michael B Cohen. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 278–287. SIAM, 2016

    2016

  4. [10]

    An elementary proof of a theorem of johnson and lindenstrauss

    Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of johnson and lindenstrauss. Random Structures & Algorithms, 22(1):60–65, 2003

    2003

  5. [11]

    Communication avoiding rank revealing qr factorization with column pivoting.SIAM Journal on Matrix Analysis and Applications, 36(1):55–89, 2015

    James W Demmel, Laura Grigori, Ming Gu, and Hua Xiang. Communication avoiding rank revealing qr factorization with column pivoting.SIAM Journal on Matrix Analysis and Applications, 36(1):55–89, 2015

    2015

  6. [12]

    Fast approximation of matrix coherence and statistical leverage

    Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff. Fast approximation of matrix coherence and statistical leverage. The Journal of Machine Learning Research, 13(1):3475–3506, 2012

    2012

  7. [13]

    Duersch and Ming Gu

    Jed A. Duersch and Ming Gu. Randomized qr with column pivoting.SIAM Journal on Scientific Computing, 39(4):C263–C291, January 2017. ISSN 1095-7197. doi: 10.1137/ 15m1044680. URL http://dx.doi.org/10.1137/15M1044680

    2017 doi

  8. [14]

    Fast and forward stable randomized algorithms for linear least-squares problems

    Ethan N Epperly. Fast and forward stable randomized algorithms for linear least-squares problems. SIAM Journal on Matrix Analysis and Applications, 45(4):1782–1804, 2024

    2024

  9. [15]

    Ethan N. Epperly. Iterative-sketching-is-stable, 2024. URL https://github.com/ eepperly/Iterative-Sketching-Is-Stable.git. 24

    2024

  10. [16]

    Numerical methods for solving linear least squares problems.Numerische Mathematik, 7:206–216, 1965

    Gene Golub. Numerical methods for solving linear least squares problems.Numerische Mathematik, 7:206–216, 1965

    1965

  11. [18]

    Efficient algorithms for computing a strong rank- revealing qr factorization.SIAM Journal on Scientific Computing, 17(4):848–869, 1996

    Ming Gu and Stanley C Eisenstat. Efficient algorithms for computing a strong rank- revealing qr factorization.SIAM Journal on Scientific Computing, 17(4):848–869, 1996

    1996

  12. [19]

    Rank-revealing qr factorizations and the singular value decomposition

    Yoo Pyo Hong and C-T Pan. Rank-revealing qr factorizations and the singular value decomposition. Mathematics of Computation, 58(197):213–232, 1992

    1992

  13. [20]

    Cambridge university press, 2012

    Roger A Horn and Charles R Johnson.Matrix analysis. Cambridge university press, 2012

    2012

  14. [21]

    Ipsen and S

    Ivar E. Ipsen and S. Chandrasekaran. On rank-revealing qr factorizations. Numerical Linear Algebra with Applications, 10(5):375–389, 2003

    2003

  15. [22]

    Extensions of lipschitz mappings into a hilbert space

    William B Johnson, Joram Lindenstrauss, et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984

    1984

  16. [23]

    Numerical linear algebra.Canadian Mathematical Bulletin, 9(5):757–801, 1966

    William Kahan. Numerical linear algebra.Canadian Mathematical Bulletin, 9(5):757–801, 1966

    1966

  17. [24]

    Sparser johnson-lindenstrauss transforms.Journal of the ACM (JACM), 61(1):1–23, 2014

    Daniel M Kane and Jelani Nelson. Sparser johnson-lindenstrauss transforms.Journal of the ACM (JACM), 61(1):1–23, 2014

    2014

  18. [26]

    Optimality of the johnson-lindenstrauss lemma

    Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pages 633–638. IEEE, 2017

    2017

  19. [27]

    Randomized numerical linear algebra: Foun- dations and algorithms.Acta Numerica, 29:403–572, 2020

    Per-Gunnar Martinsson and Joel A Tropp. Randomized numerical linear algebra: Foun- dations and algorithms.Acta Numerica, 29:403–572, 2020

    2020

  20. [28]

    Householder qr factorization with randomization for column pivoting (hqrrp)

    Per-Gunnar Martinsson, Gregorio Quintana OrtÍ, Nathan Heavner, and Robert Van De Geijn. Householder qr factorization with randomization for column pivoting (hqrrp). SIAM Journal on Scientific Computing, 39(2):C96–C115, 2017

    2017

  21. [29]

    Low-distortion subspace embeddings in input- sparsity time and applications to robust linear regression

    Xiangrui Meng and Michael W Mahoney. Low-distortion subspace embeddings in input- sparsity time and applications to robust linear regression. InProceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 91–100, 2013

    2013

  22. [30]

    Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings

    Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In2013 ieee 54th annual symposium on foundations of computer science, pages 117–126. IEEE, 2013

    2013

  23. [31]

    Lower bounds for oblivious subspace embeddings

    Jelani Nelson and Huy L Nguyên. Lower bounds for oblivious subspace embeddings. In International Colloquium on Automata, Languages, and Programming, pages 883–894. Springer, 2014

    2014

  24. [32]

    On the existence and computation of rank-revealing lu factorizations.Linear Algebra and its Applications, 316(1-3):199–222, 2000

    C-T Pan. On the existence and computation of rank-revealing lu factorizations.Linear Algebra and its Applications, 316(1-3):199–222, 2000

    2000

  25. [33]

    balls into bins

    Martin Raab and Angelika Steger. “balls into bins”—a simple and tight analysis. In International Workshop on Randomization and Approximation Techniques in Computer Science, pages 159–170. Springer, 1998. 25

    1998

  26. [34]

    Column subset selection is np-complete.Linear Algebra and its Applica- tions, 610:52–58, 2021

    Yaroslav Shitov. Column subset selection is np-complete.Linear Algebra and its Applica- tions, 610:52–58, 2021. ISSN 0024-3795. doi: https://doi.org/10.1016/j.laa.2020.09.015. URL https://www.sciencedirect.com/science/article/pii/S0024379520304377

    2021 doi

  27. [35]

    Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation.SIAM Journal on Computing, 41(2): 293–331, 2012

    Mikkel Thorup and Yin Zhang. Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation.SIAM Journal on Computing, 41(2): 293–331, 2012

    2012

  28. [36]

    Improved analysis of the subsampled randomized hadamard transform

    Joel A Tropp. Improved analysis of the subsampled randomized hadamard transform. Advances in Adaptive Data Analysis, 3(01n02):115–126, 2011

    2011

  29. [37]

    Error analysis of direct methods of matrix inversion.Journal of the ACM (JACM), 8(3):281–330, 1961

    James Hardy Wilkinson. Error analysis of direct methods of matrix inversion.Journal of the ACM (JACM), 8(3):281–330, 1961

    1961

  30. [38]

    Sketching as a tool for numerical linear algebra.Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014

    David P Woodruff et al. Sketching as a tool for numerical linear algebra.Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014

    2014

  31. [39]

    Fast parallel randomized qr with column pivoting algorithms for reliable low-rank matrix approximations

    Jianwei Xiao, Ming Gu, and Julien Langou. Fast parallel randomized qr with column pivoting algorithms for reliable low-rank matrix approximations. In 2017 IEEE 24th international conference on high performance computing (HiPC), pages 233–242. IEEE, 2017. 26

    2017

Pith tools

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