{"id":"e536a9fe-25c4-4181-940f-9e654a98f107","arxiv_id":"1908.08101","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Perturbation analysis shows CUR approximation error under noise is controlled by pseudoinverse norms of selected singular-vector submatrices, with improved bounds for rank-enforced variants.","lead":"This paper proves new error bounds for CUR matrix approximations when the observed matrix is corrupted by additive noise. The bounds cover a broad family of matrix norms and reveal how the choice of columns and rows controls the approximation error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"All main bounds require the clean submatrices C,U,R to have full rank k (Sec. 3.1); when this fails, the error is not O(||E||), and the paper gives no guidance to ensure the condition for index sets chosen from ~A.","rationale":"The reader's weakest assumption is exactly the Section 3.1 full-rank condition on the clean submatrices, and my stress-test agrees that this is the most load-bearing point in the paper. I verified the main perturbation proofs and found no algebraic errors in the lemmas used for Theorems 4.1, 4.6, and 4.9; the only genuine proof gap is the general-norm slip in Lemma 8.7, which is salvageable via the best-rank-k inequality and is already noted by the reader. The Remark 4.8 identity 'U† = W†_{k,I} Σ†_k V†_{k,J}' is dimensionally wrong and false in general (it holds only up to an inequality and with a factor ordering change), but it is not load-bearing because the main theorems are stated and proved in terms of ||U†||, and the replacement in Remark 4.8 yields a valid upper bound if read as an inequality. The full-rank condition, however, is used in every theorem, including the refined maximal-volume results; without it, the factorization identities central to the analysis fail, and the numerical counterexample above shows the error is then not governed by the noise norm. Because the paper explicitly states the assumption, this is not a hidden error, but it is the condition that determines whether the central claim has the scope its narrative suggests. The reader's CONDITIONAL verdict appropriately requires the authors to address this scope and to repair the Lemma 8.7 proof; my stress-test does not find a reason to move away from that verdict, so UNCHANGED is recommended.","tokens_in":22058,"tokens_out":30420,"duration_ms":259626,"concrete_test":"Build a rank-1 matrix A = u v^T of size, say, 3×3, with a chosen column index j such that v_j = 0 and a chosen row index set I with u_I ≠ 0, so rank(U)=0<1. For fixed noise direction H, set E = ε H and ~A = A + E. Compute the CUR error ||A - ~C~U†~R|| for ε = 10^{-1}, 10^{-2}, 10^{-4} (using the same I,J) and compare it to ε. If the error does not decay as O(ε) but instead stays bounded away from zero, the full-rank assumption is confirmed as load-bearing. Repeat with a 'good' index set (v_j ≠ 0) to show the contrast where the error does scale as O(ε). This check isolates whether the paper's central claim survives without the Section 3.1 rank condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central perturbation estimates are conditional on the Section 3.1 assumption rank(C)=rank(U)=rank(R)=k for the unobserved clean matrix A. Every theorem in Section 4 expands an exact CUR identity from Theorem 2.2 (A=CU†R or A=CC†AR†R), and those identities are equivalent to the full-rank condition. The paper's motivating setup is that I and J are selected from the noisy matrix ~A, but no result, remark, or algorithm in the paper ensures that the same index sets yield full-rank submatrices of the clean A. When the condition fails, the bounds simply do not apply, and the error can be uncontrolled independently of the noise level. Example: take a rank-1 matrix A = u v^T with some v_j = 0, and choose J containing that column j; then U = A(I,J) = 0 for any I, so rank(U)=0<k. With E = εH, the noisy submatrix ~U = εH_{I,J}, so ~U† has norm O(1/ε) while ~C = E_{*,J} has norm O(ε); the product ~C~U†~R does not converge to A as ε→0. Thus the advertised guarantee—CUR error bounded by a constant times the noise norm—holds only for 'good' index sets, which is exactly the case that column-selection algorithms are trying to identify. The maximal-volume results in Section 5 also presuppose this rank condition (Proposition 5.2), so they do not rescue the general case. The paper is explicit about the assumption, but it is still the load-bearing hinge of the central claim: if the assumption is violated, none of the main theorems apply and no graceful degradation is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes how CUR decompositions behave under additive noise, for a low-rank matrix A observed as A~=A+E. It derives perturbation bounds for five CUR approximation variants: the projection-based approximation C~C~†A~R~†R~, the non-projection approximation C~U~†R~ (with and without thresholding), rank enforcement on the middle matrix U, and a new projection-based rank-enforced variant. The bounds are expressed through the norms of pseudoinverses of submatrices of the truncated singular vectors W_k and V_k, hold for a broad class of unitarily invariant norms including all Schatten p-norms, and are linear in the noise norm with higher-order terms. The paper also refines the bounds under maximal-volume index selection, compares with prior work by Osinsky and Zamarashkin, gives a counterexample to rank-enforcement claims for non-SPSD matrices, and reports numerical experiments.","tokens_in":22321,"tokens_out":10294,"duration_ms":98230,"significance":"If the main theorems are taken together with their standing assumptions, the paper gives a systematic and largely self-contained perturbation theory for CUR decompositions. The proof structure is sound: the exact identities of Theorem 2.2, the norm identities of Proposition 6.4, and the Stewart-type pseudoinverse perturbation bounds are used carefully, and the new projection-based rank-enforced variant in Theorem 4.9 is a natural and useful contribution. The bounds are qualitative rather than probabilistic, which is appropriate for the goal of showing how the choice of rows and columns affects the error. The maximal-volume corollaries and the comparison with [31] are also informative. The main caveat is that every result is conditional on a full-rank assumption on the clean submatrices; the applicability of this assumption to index sets chosen from the noisy matrix is not addressed.","major_comments":[{"comment":"All main bounds are conditional on the standing assumption rank(C)=rank(U)=rank(R)=k for the clean matrix A. This is stated explicitly in Section 3.1, but it is the load-bearing hinge of the paper's central claim. In the motivating scenario, the index sets I and J are selected from the noisy matrix A~, yet no result or remark in the paper guarantees that those same sets produce full-rank submatrices of the unperturbed A. When the assumption fails, the bounds do not apply and the error need not be O(||E||) at all. For example, for a rank-1 matrix A=u v^T with v_j=0, choosing J to contain j gives U=0 for any I, while ~U=ε H_{I,J} is invertible with ||~U^†||≈1/ε; the product ~C~U^†~R does not converge to A as ε→0. The paper should either prove a transfer result showing that, for small noise, full rank of the selected submatrix of A~ implies (with high probability or under a mild condition) full rank of the corresponding submatrix of A, or it should explicitly restrict the claims in the abstract and introduction to index sets that make the clean submatrices full rank. Without such a clarification, the advertised noise-level guarantee is only valid for the very index sets that column-selection algorithms are trying to find.","section":"Section 3.1, Theorems 4.1, 4.2, 4.6, 4.9"}],"minor_comments":[{"comment":"In the statement of Proposition 5.2, the definition of R should be A(I,:), not A(:,J); the current text contains a typo.","section":"Proposition 5.2"},{"comment":"In the numerical illustration, the phrase \"the spectrum of A−CU^†_1R is approximately (100.9806, 1.9806, 0)\" should refer to singular values rather than eigenvalues. The matrix A−CU^†_1R is not symmetric, and the actual eigenvalues include a negative value; the quantity relevant to Schatten p-norms is the singular values.","section":"Section 9"},{"comment":"The comparison with Osinsky and Zamarashkin is made only for the square case |I|=|J|=k with the spectral norm. The paper should state more clearly that the claimed improvement over [31, Theorem 2] is restricted to that setting and does not address rectangular or oversampled cases.","section":"Section 5.2, comparison with Theorem 5.5"},{"comment":"The table is a useful summary, but the row for ~C~U~†~R uses w+v+3wv while Corollary 4.3 states w+v+3wv; the two should be checked for consistency. In the displayed Corollary 4.3 the coefficient is 3||W^†_{k,I}||||V^†_{k,J}||, which matches the table, so this is only a potential notation issue in the table header.","section":"Appendix B, Table B.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically sound within its explicitly stated assumptions, and the proofs appear correct. The central concern is whether the full-rank assumption in Section 3.1 can be guaranteed or at least meaningfully discussed for index sets obtained from the noisy matrix. This is not a reason to reject, but it is a load-bearing point that needs to be fixed or sharply qualified. I would not require a full theory for rank-deficient selected submatrices, but the authors should either prove a small-noise transfer result or clearly reposition the claims as conditional on the clean submatrix full-rank condition. The empirical section is illustrative rather than exhaustive, which is acceptable for this venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The algebra is sound and the contribution is real. Hamm and Huang give perturbation bounds for several CUR variants that hold in every Schatten p-norm (and beyond), with explicit dependence on the selected index sets through norms of pseudoinverses of singular-vector submatrices. The projection-based rank-truncated variant is new and the experiments back it up. I checked the core proofs in Sections 8.1–8.3 and the Section 9 counterexample; they work. This is not a paper that hides its weaknesses.\n\nThe soft spots are real but manageable. The load-bearing assumption is rank(C)=rank(U)=rank(R)=k for the clean matrix A, stated in Section 3.1. Every bound expands an exact CUR identity and collapses if this fails. The paper is explicit about this, but the motivating scenario is index sets chosen from noisy data, and nothing there guarantees the clean submatrices have full rank. The stress-test example with a zero column in a rank-1 matrix is valid: with the wrong J, the bounds do not apply and the error need not vanish with the noise. This is not a fatal flaw—column selection methods aim precisely at good index sets—but it should be stated more prominently, and ideally the paper would add a remark on what happens when the assumption is violated. The maximal-volume results in Section 5 help only under the same rank condition.\n\nOne genuine exposition gap: in Lemma 8.7 the proof writes a general-norm quantity as sigma_{k+1}(~C), which is only literally true for the spectral norm. The claim is salvageable via the best-rank-k property, as the reader notes, but it needs a fix. Also, the boundary with the authors' own prior work [24] (Stability of sampling for CUR decompositions) is not clearly delineated; a paragraph saying which results are new here versus there would help.\n\nWho is this for? Anyone working on CUR or Nyström methods who wants norm-aware perturbation guarantees. The paper deserves a serious referee and will likely need minor revision rather than major rework. My recommendation: send it to review, ask the authors to fix Lemma 8.7, clarify the rank assumption's scope, and state the relation to [24]. I would cite it.","headline":"A solid, genuinely useful perturbation analysis for CUR decompositions, with honest bounds across all Schatten p-norms; the main caveat is that every theorem hinges on the clean submatrices having full rank, which the paper states but does not help the reader ensure.","tokens_in":22978,"tokens_out":1502,"would_cite":true,"duration_ms":17612,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A23","65F30","68P99","68W20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Noisy CUR decompositions have error controlled by a single index-set constant in every Schatten p-norm.","keywords":["CUR decomposition","low-rank matrix approximation","matrix perturbation theory","Schatten p-norm","Moore-Penrose pseudoinverse","maximal-volume submatrix","rank enforcement","unitarily invariant norm"],"falsifier":"A direct numerical test would settle it: fix a low-rank $A$ and index sets $I,J$ satisfying the full-rank assumption, then compute the maximum over noise matrices with $\\|E\\|=1$ of $\\|A-\\tilde C\\tilde C^\\dagger\\tilde A\\tilde R^\\dagger\\tilde R\\|/\\|E\\|$ and compare it with $\\|W_{k,I}^\\dagger\\|+\\|V_{k,J}^\\dagger\\|+3$. Any ratio above the bound refutes Theorem 4.1. In the rank-one case $A=\\mathrm{diag}(1,0)$ with $I=J=\\{1\\}$, this ratio can be computed in closed form from the four entries of $E$.","tokens_in":21733,"feed_emoji":"🧮","tokens_out":9336,"duration_ms":82536,"temperature":0.7,"pith_summary":"The paper asks what happens to a CUR decomposition when the low-rank matrix $A=W_k\\Sigma_k V_k^*$ is observed as $A+E$. It claims that every standard variant of the CUR approximation has error bounded by a small multiple of the noise norm $\\|E\\|$, with the multiplier built from the norms of the pseudoinverses of the selected submatrices of the singular-vector matrices $W_k$ and $V_k$. Since the bounds are stated for every normalized, uniformly generated, unitarily invariant norm, they cover the spectral, Frobenius, and nuclear norms in one statement. The practical upshot is that the analysis separates the effect of noise from the effect of row and column choice, and it improves known constants when maximal-volume submatrices are selected.","feed_headline":"CUR errors stay linear in noise, fixed by row and column choice","feed_subtitle":"New perturbation bounds cover every Schatten p-norm and five CUR variants at once.","key_machinery":"The argument rests on the exact CUR identities $A=CU^\\dagger R$ and $A=CC^\\dagger AR^\\dagger R$ (Theorem 2.2), which hold when the selected submatrices have rank $k$. Proposition 6.4 identifies the norms $\\|CU^\\dagger\\|$ and $\\|U^\\dagger R\\|$ with $\\|W_{k,I}^\\dagger\\|$ and $\\|V_{k,J}^\\dagger\\|$, converting every perturbation deviation into quantities involving only the selected singular-vector rows. The perturbation theorems for pseudoinverses and singular values (Theorems 7.1 and 7.2) then supply the linear-in-noise skeleton, while the maximal-volume estimates place explicit bounds on the pseudoinverse constants.","core_discovery":"The central claim is that for an exactly low-rank matrix $A=W_k\\Sigma_k V_k^*$ corrupted by noise $E$, every CUR approximation variant considered obeys an error bound of the form a constant (depending on $I,J$) times $\\|E\\|$, plus higher-order terms. Concretely, Theorem 4.1 states $\\|A-\\tilde C\\tilde C^\\dagger\\tilde A\\tilde R^\\dagger\\tilde R\\| \\le \\|E\\|(\\|W_{k,I}^\\dagger\\|+\\|V_{k,J}^\\dagger\\|+3)$, where $W_{k,I}$ and $V_{k,J}$ are the row submatrices of the singular vectors selected by the row and column index sets. Analogous bounds are proved for the thresholded middle matrix $\\tilde C[\\tilde U]_\\tau^\\dagger \\tilde R$, the rank-enforced middle matrix $\\tilde C\\tilde U_k^\\dagger\\tilde R$, and the projection-based rank-enforced approximation $\\tilde C_k\\tilde C_k^\\dagger\\tilde A\\tilde R_k^\\dagger\\tilde R_k$. The paper also claims that maximal-volume selection of rows and columns converts the pseudoinverse constants into explicit universal factors, and that for non-SPSD matrices there is no provably best way to enforce the rank in a CUR approximation.","pith_inferences":["A natural next step is to feed probabilistic bounds on $\\|W_{k,I}^\\dagger\\|$ and $\\|V_{k,J}^\\dagger\\|$ under leverage-score or other random sampling into these deterministic inequalities; the paper explicitly leaves that open.","The bounds suggest a concrete optimization objective for column and row selection: minimize $\\|W_{k,I}^\\dagger\\|+\\|V_{k,J}^\\dagger\\|$ over index sets, which quantifies selection quality even though exact maximal-volume selection is computationally hard.","The new projection-based rank-truncated variant $\\tilde C_k\\tilde C_k^\\dagger\\tilde A\\tilde R_k^\\dagger\\tilde R_k$ deserves practical attention when only a little more than $k$ columns and rows are sampled, since the projection argument explains its favorable small-sample behavior.","Read back-to-front, the bounds can certify when CUR is competitive with truncated SVD: the index-set constant must be small compared with the inverse noise level."],"forward_implications":["For the projection-based approximation, the error is at most $\\|E\\|(\\|W_{k,I}^\\dagger\\|+\\|V_{k,J}^\\dagger\\|+3)$, so accuracy is predictable from the noise size and the selected singular-vector submatrices alone.","Because the bounds hold for every Schatten $p$-norm simultaneously, one computation yields spectral, Frobenius, and nuclear error guarantees.","With maximal-volume selection, the pseudoinverse norms admit explicit universal upper bounds, turning the error estimate into constants that depend only on $k$ and the matrix dimensions.","For the rank-enforced variant on $\\tilde U$, the error stays first-order in $\\|E\\|$ whenever $\\sigma_k(U)>2\\mu\\|E_{I,J}\\|$; outside that spectral-gap condition the stated bound does not apply.","For non-SPSD matrices, enforcing the rank after forming the CUR product is not provably better than enforcing it on the middle matrix, in contrast to the symmetric positive semidefinite case."],"supporting_citations":[{"why":"supplies the exact CUR decomposition criteria and identities of Theorem 2.2 on which all perturbation bounds are built","marker":"[23]"},{"why":"supplies the pseudoinverse perturbation theorem with norm-dependent constant used in the rank-enforced bounds","marker":"[35]"},{"why":"supplies the maximal-volume pseudoinverse estimates and the previous perturbation results used for comparison","marker":"[31]"},{"why":"supplies the projection perturbation lemma used in the proof of the rank-enforced projection bound","marker":"[11]"},{"why":"supplies the singular-value stability inequality used to control rank-truncated submatrices","marker":"[17]"},{"why":"supplies the DEIM-based CUR perturbation bound against which the projection-based bound is compared","marker":"[34]"},{"why":"supplies the rank-enforcement comparison for symmetric positive semidefinite matrices that Section 9 contrasts with the generic case","marker":"[33]"}],"fun_headline_variants":["CUR errors linear in noise, row and column choice sets constant","Perturbation bounds for CUR: all p-norms, linear in noise","CUR noise error linear; selection fixes the constant","New CUR perturbation bounds cover every Schatten p-norm","Row and column choice governs CUR error under noise"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The bounds collapse unless the selected columns and rows of the clean matrix $A$ already have rank exactly $k$, so the exact identities $A=CU^\\dagger R$ and $A=CC^\\dagger AR^\\dagger R$ hold; the rank-enforced bound additionally assumes a spectral gap $\\sigma_k(U)>2\\mu\\|E_{I,J}\\|$.","fun_headline_variants_meta":{"raw":{"variants":["CUR errors linear in noise, row and column choice sets constant","Perturbation bounds for CUR: all p-norms, linear in noise","CUR noise error linear; selection fixes the constant","New CUR perturbation bounds cover every Schatten p-norm","Row and column choice governs CUR error under noise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001248,"raw_usage":{"total_tokens":5101,"prompt_tokens":914,"completion_tokens":4187,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":530,"completion_tokens_details":{"reasoning_tokens":4102}},"tokens_in":530,"tokens_out":4187,"duration_ms":27192,"temperature":1.0,"reasoning_tokens":4102,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:51:38.438139+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct numerical test would settle it: fix a low-rank $A$ and index sets $I,J$ satisfying the full-rank assumption, then compute the maximum over noise matrices with $\\|E\\|=1$ of $\\|A-\\tilde C\\tilde C^\\dagger\\tilde A\\tilde R^\\dagger\\tilde R\\|/\\|E\\|$ and compare it with $\\|W_{k,I}^\\dagger\\|+\\|V_{k,J}^\\dagger\\|+3$. Any ratio above the bound refutes Theorem 4.1. In the rank-one case $A=\\mathrm{diag}(1,0)$ with $I=J=\\{1\\}$, this ratio can be computed in closed form from the four entries of $E$.","supporting_citations":[{"cited_title":"Hamm and L.-X","cited_arxiv_id":null,"evidence_quote":"supplies the exact CUR decomposition criteria and identities of Theorem 2.2 on which all perturbation bounds are built"},{"cited_title":"Osinsky and N","cited_arxiv_id":null,"evidence_quote":"supplies the maximal-volume pseudoinverse estimates and the previous perturbation results used for comparison"},{"cited_title":"Drineas and I","cited_arxiv_id":null,"evidence_quote":"supplies the projection perturbation lemma used in the proof of the rank-enforced projection bound"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the singular-value stability inequality used to control rank-truncated submatrices"},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the DEIM-based CUR perturbation bound against which the projection-based bound is compared"},{"cited_title":"Pourkamali-Anaraki and S","cited_arxiv_id":null,"evidence_quote":"supplies the rank-enforcement comparison for symmetric positive semidefinite matrices that Section 9 contrasts with the generic case"}],"review_version":1}