{"id":"c3903bc0-f1cd-4ab7-b11a-348218fc670c","arxiv_id":"2412.13992","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Adaptive Randomized Pivoting is a cheap adaptive leverage-score sampler that matches the optimal expected Frobenius error for column subset selection and yields new expected-error bounds for DEIM, cross, and Nyström approximations.","lead":"The paper introduces Adaptive Randomized Pivoting, a random index-selection method for column subset selection and related low-rank approximations, and proves it achieves the optimal approximation error in expectation. The method is simpler and cheaper than volume sampling and extends naturally to DEIM, cross approximation, and Nyström approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.4's equality is false: the proof cancels sampling probabilities against row norms even where row norms are zero; the correct statement is an inequality.","rationale":"The reader's ACCEPT rests on the strongest claim that Theorem 2.4 supplies the exact equality E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] = (r+1)||A - AVV^T||_F^2. That equality is false in general. The proof's step (2.17) implicitly assumes that every unselected column j has ||V_{k-1}(j,:)|| > 0, so that the probability p_j cancels cleanly against the reciprocal row norm. When some unselected row of V_{k-1} is zero, the corresponding term contributes zero to the conditional expectation, not ||~A_{k-1}(:,j)||^2/(r-k+1). Zero rows of V_{k-1} occur even when V initially has no zero rows, as soon as an unselected row is linearly dependent on the already selected rows of V. The elementary counterexample A=I_3, V=e_1, r=1 gives LHS 2 and RHS 4; a full-row example with V=[[1/√5,0],[0,1],[2/√5,0]] gives LHS 2 and RHS 3. The correct result is an upper bound, not an equality: E ≤ (r+1)||A-AVV^T||^2. All main upper-bound consequences—Corollaries 2.5, 2.6, 3.1, 4.1, 5.1—remain valid once every equality is weakened to ≤, so the paper is salvageable, but the central theorem as stated and the reader's verification of it are not correct. The verdict should be CONDITIONAL: accept only after Theorem 2.4 and the corresponding equations are corrected to inequalities, or after an additional assumption is imposed that prevents unselected zero rows at every step.","tokens_in":21508,"tokens_out":43071,"duration_ms":356403,"concrete_test":"Run Algorithm 2.1 on A = I_3, V = e_1, r = 1. Since the algorithm is deterministic, compute the left-hand side of (2.15) directly: ||I - e_1e_1^T||_F^2 = 2, while the right-hand side is (r+1)||I - e_1e_1^T||_F^2 = 4. The mismatch settles that (2.15) is not an equality. To exclude the objection that V has a zero row, repeat with A = I_3, r = 2, and V = [[1/√5,0],[0,1],[2/√5,0]] (orthonormal columns, all rows nonzero). Enumerating the four possible index sets with their exact probabilities gives E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] = 2, while the claimed right-hand side is (r+1)||I - VV^T||_F^2 = 3. This confirms the flaw is generic and not an artifact of initially zero rows.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 2.4 fails at the fourth equality of (2.17). It replaces E[||~A_{k-1}(:,j_k)||^2 / ||V_{k-1}(j_k,:)||^2] by (1/(r-k+1)) Σ_{j∉J_{k-1}} ||~A_{k-1}(:,j)||^2, formally canceling p_j = ||V_{k-1}(j,:)||^2/(r-k+1) against the denominator. This cancellation is only valid when ||V_{k-1}(j,:)|| > 0. If any unselected row of V_{k-1} is zero, that column contributes 0, not ||~A_{k-1}(:,j)||^2/(r-k+1). Such zero rows arise as soon as an unselected row lies in the span of the previously selected rows of V, even when every initial row of V is nonzero. For example, take A = I_3, r = 1, V = e_1. The algorithm deterministically returns J = {1}, so E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] = ||I - e_1e_1^T||_F^2 = 2, but the right-hand side of (2.15) is (r+1)||A - AVV^T||_F^2 = 2·2 = 4. Thus the claimed equality is false. Restricting the sum in (2.17) to the support of V_{k-1} and dropping nonnegative terms gives the valid inequality E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] ≤ (r+1)||A - AVV^T||_F^2. The upper-bound corollaries survive, but the paper's strongest claim—the exact equality in Theorem 2.4 and in equations (1.5) and (2.15)—does not.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21934,"tokens_out":9757,"duration_ms":78125,"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":[{"comment":"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.","section":"Section 2.3, Theorem 2.4 / Eq. (2.15)"},{"comment":"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).","section":"Section 3, Corollary 3.1"}],"minor_comments":[{"comment":"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].","section":"Section 2.3, proof of Theorem 2.4"},{"comment":"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.","section":"Section 6.1, Figures 2a and 2b"},{"comment":"The phrase 'orthonogonal transformations' is a typo for 'orthogonal transformations'.","section":"Section 2.2"},{"comment":"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}.","section":"Sections 2.3 and 2.4"}],"recommendation":"major_revision","confidential_remarks":"The skeptical counterexample is correct and directly invalidates the equality in Theorem 2.4. This is a load-bearing issue because the paper's stated main result is an equality, not merely an upper bound. However, the corrected inequality suffices for all the algorithmic applications, so this is fixable within the manuscript's scope. I recommend asking the authors to replace every exact-equality statement that relies on (2.17) with the corresponding inequality and to update the surrounding text and corollaries accordingly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea is good: an adaptive leverage-score sampler that avoids touching A once V is known, with clean extensions to DEIM, cross approximation, and Nyström. The derandomization that recovers Osinsky's method and the new deterministic Nyström algorithm are nice. The paper is well written and the numerical work is honest.\n\nNow the soft spot. Theorem 2.4 claims an exact equality, E[||A - A(:,J)V(J,:)^{-T}V^T||_F^2] = (r+1)||A - AVV^T||_F^2. That is false. The proof's fourth equality in (2.17) cancels the sampling probability ||V_{k-1}(j,:)||^2/(r-k+1) against the norm in the denominator, but if some unselected row of V_{k-1} is zero, that index has zero sampling probability and should contribute zero, not its full column norm. Example: A=I_3, r=1, V=e_1. The algorithm deterministically returns J={1}, so the left side is 2, while the right side is 2·2=4. The same issue appears in equations (1.5) and (2.15).\n\nThe fix is trivial: cancel only over the support of V_{k-1}, which yields E[·] ≤ (r+1)||A-AVV^T||_F^2. Every upper-bound corollary (2.5, 2.6, 3.1, 4.1, 5.1) still holds, and the claimed optimality in expectation remains as an upper bound. But the exact equality is a load-bearing part of the paper's presentation, and the current proof is invalid as written.\n\nOther concerns are minor: a few typos in the proof of Corollary 5.1, and the authors rightly caveat that the algorithm's equivalence to an r-DPP is known. The comparison with RPCholesky in Section 5.1 is fair.\n\nWho should read this: anyone working on randomized column selection, DEIM, or Nyström approximation. The sampling scheme is simpler and cheaper than volume sampling and the bounds are strong enough to matter. After the equality is corrected to an inequality, the paper is a solid contribution. I would send it to a serious referee, asking for that revision rather than rejection.","headline":"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.","tokens_in":22465,"tokens_out":2715,"would_cite":true,"duration_ms":25120,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F55","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["randomized algorithms","column subset selection","adaptive sampling","leverage scores","low-rank approximation","DEIM","cross approximation","Nyström approximation"],"falsifier":"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.","tokens_in":21313,"feed_emoji":"🎲","tokens_out":14393,"duration_ms":110693,"temperature":0.7,"pith_summary":"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.","feed_headline":"A cheap sampler achieves optimal column selection in expectation","feed_subtitle":"Adaptive randomized pivoting matches the best possible rank-r error bound with a far simpler rule","key_machinery":"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$.","core_discovery":"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).","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Establishes the $(r+1)$ existence bound via volume sampling and the matching tightness example that ARP's guarantee matches.","marker":"[12]"},{"why":"Supplies the deterministic column-selection algorithm whose randomized version ARP is, including the oblique-projector identity used in the analysis.","marker":"[25]"},{"why":"Provides the randomized SVD error bound used in Corollary 2.6 to turn a sketched $V$ into an end-to-end guarantee of $(r+3)(r+1)$ times the tail energy.","marker":"[21]"},{"why":"Gives the correspondence between Nyström approximation and column subset selection for a factor $B$ with $B^TB=A$, used for the Nyström error bounds and the deterministic variant.","marker":"[16]"},{"why":"Defines the DEIM approximation and the standard error bound through $\\|(E_I^TV)^{-1}\\|_2$ that motivates the index-selection objective.","marker":"[6]"},{"why":"Describes randomly pivoted Cholesky, the competing randomized Nyström method whose bound requires oversampling; the paper's bound is compared against it.","marker":"[7]"}],"fun_headline_variants":["Column selection hits optimal error with a simple random rule","Randomized pivoting matches deterministic low-rank guarantees","Adaptive sampling improves DEIM, cross, and Nyström bounds","Optimal column selection from a cheap adaptive rule","New deterministic Nyström algorithm from derandomized pivoting"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Column selection hits optimal error with a simple random rule","Randomized pivoting matches deterministic low-rank guarantees","Adaptive sampling improves DEIM, cross, and Nyström bounds","Optimal column selection from a cheap adaptive rule","New deterministic Nyström algorithm from derandomized pivoting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000733,"raw_usage":{"total_tokens":3328,"prompt_tokens":1047,"completion_tokens":2281,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":663,"completion_tokens_details":{"reasoning_tokens":2199}},"tokens_in":663,"tokens_out":2281,"duration_ms":15757,"temperature":1.0,"reasoning_tokens":2199,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:36:15.569801+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Deshpande, L","cited_arxiv_id":null,"evidence_quote":"Establishes the $(r+1)$ existence bound via volume sampling and the matching tightness example that ARP's guarantee matches."},{"cited_title":"Halko, P.-G","cited_arxiv_id":null,"evidence_quote":"Provides the randomized SVD error bound used in Corollary 2.6 to turn a sketched $V$ into an end-to-end guarantee of $(r+3)(r+1)$ times the tail energy."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the correspondence between Nyström approximation and column subset selection for a factor $B$ with $B^TB=A$, used for the Nyström error bounds and the deterministic variant."}],"review_version":1}