{"id":"351d9dcb-6388-4529-b087-141f45d1329e","arxiv_id":"2509.03198","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SE-QRCS selects k representative columns of a wide matrix by applying strong rank-revealing QR to a sparse sketch and to the small induced column set, with spectral bounds that shrink the dependence on n.","lead":"This paper introduces SE-QRCS, an algorithm that selects informative columns of very wide matrices by applying QR with column pivoting to a sparse random sketch, then to the small set of original columns that the sketch touches. It proves rank-revealing spectral bounds and reports 7 to 10 times faster pivot selection than QRCP on tested 100 by 1,000,000 matrices.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main theorem unproven: Lemma 4.4 uses the selecting sketch to embed the selected subspace, a conditioning step that Definition 2.10 does not justify; Remark 4.3's p>l caveat is also omitted from Theorem 4.5.","rationale":"The reader correctly flags that Theorem 4.5 omits the p>l assumption used in the proof and that p is only controlled in expectation. My stress-test identifies a more load-bearing issue beneath that: the proof applies the subspace-embedding property to range(tilde A1^T), a subspace selected using the same Omega that is supposed to embed it. An OSE guarantee holds for a fixed subspace independent of the sketching matrix, not for a data-dependent subspace produced by running sRRQR on the sketch. Remark 4.1 does not supply a simultaneous guarantee over all subsets, and no decoupling argument is given. Thus even if p>l were stated and concentrated, Lemma 4.4 would still not follow from the definitions as written. I do not claim the algorithm is wrong in practice; the experiments and LU_PRRP application are useful evidence of empirical value, and the paper has no obvious internal inconsistency beyond this proof gap. But the central advertised guarantee, an n-independent strong rank-revealing bound, is currently unverified. I therefore move the verdict from CONDITIONAL to UNVERDICTED: the theorem may be repairable, but the missing conditional-embedding argument must be supplied before the claim can be accepted.","tokens_in":20793,"tokens_out":19616,"duration_ms":199958,"concrete_test":"Analytic check: fix a Countsketch or OSNAP Omega with p>l and take a p-column submatrix A_sub whose row space is the span of the all-ones vector. With positive probability all p nonzero entries of Omega_sub land in one row with matching signs, giving ||Omega_sub^T 1||^2 = p^2 while ||1||^2 = p; this violates the epsilon-embedding property for epsilon<1, so Remark 4.1 is false as a deterministic \"any subset\" statement. To test the conditioning gap directly, instrument SE-QRCS: for each trial record the selected S and evaluate ||tilde A1 [Omega11 Omega12]||_2 / ||tilde A1||_2, then compare with the distribution of the same ratio for a random S of the same size drawn independently of Omega.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"SE-QRCS chooses tilde A1 by running sRRQR on B = A Omega^T, so the selected column set S and the subspace range(tilde A1^T) are functions of Omega. Lemma 4.4 then invokes \"using 4.3\" to bound ||tilde A1 [Omega11 Omega12]|| as if [Omega11 Omega12] were an oblivious subspace embedding for range(tilde A1^T). Definition 2.10 is a guarantee for a fixed subspace chosen independently of the sketch; it does not permit conditioning on the Omega-dependent event that S was selected. 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, and no union bound or independence argument is supplied. This is not repaired by the p>l assumption in Remark 4.3: p>l controls collisions but not the dependence between Omega_S and the selection event. Additionally, Theorem 4.5 states no assumption on p, while the proof says \"for the remainder... assume p>l\"; p itself is random and only bounded in expectation (Prop. 3.2), with no high-probability concentration bound. In the Countsketch regime used in experiments, l = O(d^2/epsilon^2) and E(p) = n k'/l can be below l, so neither bullet of Remark 4.3 applies with the claimed constants. The central n-independent guarantee of Theorem 4.5 is therefore not established as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21175,"tokens_out":10778,"duration_ms":102159,"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":[{"comment":"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.","section":"Section 4, Theorem 4.5 and Remark 4.3"},{"comment":"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.","section":"Section 4, Lemma 4.4 and Definition 2.10"},{"comment":"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.","section":"Section 5.1 and Section 5.3"},{"comment":"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.","section":"Section 3.2 and Table 1"}],"minor_comments":[{"comment":"Equation (13) has a sign error: the lower bound should use sqrt(1 - epsilon), not sqrt(1 + epsilon), in analogy with (12).","section":"Corollary 2.9, Eq. (13)"},{"comment":"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.","section":"Section 4, notation"},{"comment":"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'.","section":"Remark 4.3"},{"comment":"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.","section":"Algorithm 1, line 10"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main proof gap is substantial but appears repairable within the manuscript's scope, for example by restructuring the second stage to use an independent sketch of \\tilde A1 and by adding a concentration bound for p. I would also ask the authors to clarify the novelty and difference from the randomized strong RRQR results in [17], since both papers target the same kind of guarantee; this is a presentation and positioning issue rather than a circularity concern. The paper fits the journal's scope and the empirical study is useful once aligned with the analyzed algorithm."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuinely different column subset selection algorithm—sketch range(A^T) from the right, recover original columns via the sparsity pattern of the embedding, then run strong RRQR on the reduced set. The runtime claims are plausible and the pivot-mapping trick is clever. But the main theorem as stated is not proven. The proof leans on Remark 4.3 to treat the submatrix of Omega restricted to the selected columns as an OSE for range(tilde A1^T). That step doesn't follow: the selected set S is a function of Omega, so Omega_S conditioned on S is not drawn from the original OSE distribution, and p>l does not repair the dependence. The paper also controls p only in expectation (Prop 3.2) with no concentration bound, and Theorem 4.5 never states the p>l assumption used in the proof. So the advertised n-independent guarantee is not established. This is a legitimate gap, not a nitpick.\n\nCredit where due: the right-sketching plus pivot-mapping mechanism is new relative to randomized QRCP and the left-sketching analysis in [17]; the complexity analysis O(d(lk'+pk)+sdn) is honest; the numerical experiments show 7–10x speedups over QRCP at n=1e6 and the LU_PRRP application is a nice validation. The paper also correctly notes the tension between sparsity s and reduced-set size p (Remark 3.3). Citation pattern looks fine; self-cites [17] and [25] are used for context and application, not as load-bearing inputs.\n\nMinor issues: Corollary 2.9 has an evident typo (both bounds written with sqrt(1+epsilon)); the experiments use QRCP rather than sRRQR, so the strong RRQR property is not directly validated; no code is provided. These are secondary.\n\nWho this is for: people working on randomized QRCP, column subset selection, and rank-revealing factorizations for wide matrices. If the adaptivity gap can be closed, this would be a useful tool. As it stands, the paper deserves a serious referee, not a desk reject. I'd send it to review and ask for: (1) a high-probability bound on p, (2) a clear statement of the p>l hypothesis in Theorem 4.5, (3) either a repair of the adaptivity step or an explicitly weaker theorem, and (4) release of code.","headline":"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.","tokens_in":21658,"tokens_out":9644,"would_cite":false,"duration_ms":83894,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F25","65F55","68W20","65F30"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["column subset selection","strong rank-revealing QR","randomized numerical linear algebra","sparse subspace embeddings","CountSketch","leverage score sparsification","low-rank approximation","LU with panel rank revealing pivoting"],"falsifier":"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.","tokens_in":20577,"feed_emoji":"🧮","tokens_out":8647,"duration_ms":74528,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sketch-first QR selects columns fast and keeps rank-revealing bounds","feed_subtitle":"On wide matrices, pivoting the sketch and its induced columns costs far less than full strong RRQR.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Supplies the strong rank-revealing QR factorization and the inequalities that SE-QRCS aims to satisfy.","marker":"[18]"},{"why":"Defines OSNAP sparse embeddings and gives the subspace-embedding theorems used to choose $l$ and $s$.","marker":"[30]"},{"why":"Provides the LESS non-oblivious sparse embeddings and the per-row sparsity bounds used for the $n$-independent result.","marker":"[8]"},{"why":"The prior randomized strong-RRQR result that SE-QRCS extends to the sketch-first, map-back setting.","marker":"[17]"},{"why":"Provides the proof template and relaxed strong-RRQR corollary used in Lemma 4.4.","marker":"[11]"},{"why":"The two-stage CSSP algorithm whose error bound is compared with SE-QRCS in Table 1.","marker":"[3]"},{"why":"The LU_PRRP algorithm used as the application demonstrating SE-QRCS in practice.","marker":"[25]"},{"why":"Balls-and-bins maximum-load bounds used to estimate $p$ and the embedding row-load $\\omega^*$.","marker":"[33]"}],"fun_headline_variants":["Sketch-first QR selects columns with n-free rank bounds","Sparse embeddings accelerate QR column subset selection","SE-QRCS: sketch, pivot, recover cheaper columns","Randomized sparse embeddings shrink QR column-sel cost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Sketch-first QR selects columns with n-free rank bounds","Sparse embeddings accelerate QR column subset selection","SE-QRCS: sketch, pivot, recover cheaper columns","Randomized sparse embeddings shrink QR column-sel cost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000596,"raw_usage":{"total_tokens":2864,"prompt_tokens":1091,"completion_tokens":1773,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":707,"completion_tokens_details":{"reasoning_tokens":1709}},"tokens_in":707,"tokens_out":1773,"duration_ms":14176,"temperature":1.0,"reasoning_tokens":1709,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:33:47.841928+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Optimal embedding dimension for sparse subspace embeddings","cited_arxiv_id":null,"evidence_quote":"Provides the LESS non-oblivious sparse embeddings and the per-row sparsity bounds used for the $n$-independent result."},{"cited_title":"Efficient algorithms for computing a strong rank- revealing qr factorization.SIAM Journal on Scientific Computing, 17(4):848–869, 1996","cited_arxiv_id":null,"evidence_quote":"Supplies the strong rank-revealing QR factorization and the inequalities that SE-QRCS aims to satisfy."},{"cited_title":"Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings","cited_arxiv_id":null,"evidence_quote":"Defines OSNAP sparse embeddings and gives the subspace-embedding theorems used to choose $l$ and $s$."},{"cited_title":"Communication avoiding rank revealing qr factorization with column pivoting.SIAM Journal on Matrix Analysis and Applications, 36(1):55–89, 2015","cited_arxiv_id":null,"evidence_quote":"Provides the proof template and relaxed strong-RRQR corollary used in Lemma 4.4."},{"cited_title":"An improved approximation algorithm for the column subset selection problem","cited_arxiv_id":null,"evidence_quote":"The two-stage CSSP algorithm whose error bound is compared with SE-QRCS in Table 1."},{"cited_title":"Lu factorization with panel rank revealing pivoting and its communication avoiding version.SIAM Journal on Matrix Analysis and Applications, 34(3):1401–1429, 2013","cited_arxiv_id":null,"evidence_quote":"The LU_PRRP algorithm used as the application demonstrating SE-QRCS in practice."},{"cited_title":"balls into bins","cited_arxiv_id":null,"evidence_quote":"Balls-and-bins maximum-load bounds used to estimate $p$ and the embedding row-load $\\omega^*$."}],"review_version":1}