{"id":"29c82348-5028-4ca3-8bd3-c60aba8ebc46","arxiv_id":"1908.06059","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A derandomized row/column selection algorithm computes a cross approximation whose Frobenius-norm error is at most k+1 times the best rank-k error, in deterministic polynomial time.","lead":"Two new deterministic algorithms improve how computers pick rows and columns of a matrix to build cheap low-rank approximations. The main result gives the first polynomial-time guarantee for the so-called cross approximation, staying within a factor k+1 of the best possible error.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The unproven O(m^2) bulge-chasing step in §3.2.2 is load-bearing: Algorithm 3's conditional-expectation ratios and complexity claim rest on an algorithm described only by a figure and a disclaimer.","rationale":"The paper's logic is mostly sound: Lemma 4 is a careful Cauchy–Binet computation; Theorem 5 is a standard conditional-expectation induction; Corollaries 2 and 6 follow from the projection argument; and the numerical experiments are consistent with the claimed bounds, modulo the stated instability of Algorithm 3 without early stopping at larger k. The stress-test therefore does not target the core derandomization idea, and I do not see circularity or hidden parameter fitting. The load-bearing weak point is precisely the unelaborated bulge-chasing step in §3.2.2, which the reader's verdict also identifies. It is load-bearing because it is the only place in the construction where a nontrivial O(m^2) matrix reduction is asserted without a complete algorithm or proof: both the correctness of the ratios (18) and the stated O(k m^3 n) running time depend on it. This leaves the reader's CONDITIONAL verdict unchanged: the mathematical framework is promising and likely correct, but the paper should supply a complete description or proof of the bulge chase, address zero-pivot handling, and ideally release code so the claim can be checked. I would not reject the paper: the missing piece is localized, and standard Givens bulge-chasing techniques suggest it can be supplied.","tokens_in":19781,"tokens_out":14802,"duration_ms":145542,"concrete_test":"Write a standalone implementation of Steps 1–3 in §3.2.2, supplying the missing bulge chase from the description in Figure 5. For m = 16, 32, ..., 256, random diagonal Σ and vectors x, y, compare the singular values of the final D3 with those of Σ − x y^T from a dense SVD; report the maximum relative error and count the number of Givens rotations as a function of m. Then insert this routine into Algorithm 3 and test it on the 3×3 SPD example in §3.2.3 and on random 20×20 matrices with known k, verifying in exact or high-precision arithmetic that the returned I, J satisfy (15). If the singular values agree to working precision and the rotation count grows as O(m^2), the concern is resolved; otherwise the algorithm description must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim — Theorem 5 with bound (15), delivered by Algorithm 3 — requires that for every candidate pair (i,j) the ratio in (18) can be computed reliably in O(m^2) work. That computation rests on the final ingredient in §3.2.2: reducing D1 (bidiagonal plus a dense first row) to a banded matrix D2 'by a bulge chasing algorithm'. The paper explicitly says 'We refrain from giving a detailed description of the algorithm and refer to Figure 5'; no pseudocode, invariant, or rotation count is given. Since Theorem 5 and the stated O(k m^3 n) complexity both assume this step, the absence of a verifiable algorithm is a real gap. If the bulge chase is invalid, the ratios fed to line 13 are wrong and Theorem 5 does not follow; if it merely needs more rotations, the stated complexity is not established (the polynomial-time headline would survive, but the algorithmic contribution would be weaker). A second, smaller gap: the pseudocode does not exclude pairs with B(i,j)=0, while Lemma 4 and formula (19) require a nonzero pivot; a correct implementation must skip zero-volume pivots, but this restriction is not stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops deterministic algorithms for column subset selection and cross approximation in the Frobenius norm. For column subset selection it replaces the characteristic-polynomial updates of Deshpande and Rademacher with singular-value updates, claims the same O(k m^2 n) complexity with better numerical robustness, and adds an early-stopping heuristic. For cross approximation, the main contribution is Algorithm 3, which derandomizes the existence result of Zamarashkin and Osinsky and is claimed to return row/column index sets I, J such that the cross approximation error is bounded by (k+1)^2 times the tail sum of squared singular values, in deterministic time O(k m^3 n). The paper also gives a CUR approximation bound from two column subset selections, a tensor extension with a quasi-optimal multilinear-rank bound, and numerical experiments on matrices and tensors.","tokens_in":19961,"tokens_out":4435,"duration_ms":46876,"significance":"If the algorithmic claims are fully established, the cross approximation result is significant: it would be the first deterministic polynomial-time algorithm with a polynomial-in-k error bound for cross approximation in the Frobenius norm, a gap the paper correctly identifies in the literature. The singular-value-based reformulation of the column subset selection algorithm is a genuinely useful practical improvement over characteristic-polynomial updates, and the experiments support the robustness and speed claims. The paper is also careful in its claims: it explicitly flags the absence of a numerical stability analysis, the small/medium-scale scope, and the heuristic nature of early stopping. The tensor extension is straightforward but gives a clean, explicit bound. However, the main cross approximation algorithm is not fully specified: its correctness and complexity rest on an unproven bulge-chasing step described only by a figure.","major_comments":[{"comment":"The bulge-chasing procedure that transforms D1 into the banded matrix D2 is load-bearing for both correctness and complexity, but it is not actually specified. The text says 'We refrain from giving a detailed description of the algorithm and refer to Figure 5'; no pseudocode, invariant, or count of Givens rotations is supplied. The ratios in equation (18) are computed from the singular values of this D2, and the claimed O(m^2) cost per pair (and therefore the total O(k m^3 n) complexity) depends on this step. As written, a reader cannot verify either the correctness of the computed singular values or the stated operation count. This is a major gap: supply a complete description of the bulge-chasing reduction, or a precise reference with a theorem proving that D1 can be reduced to upper banded form in O(m^2) Givens rotations, and state the fill-in pattern explicitly.","section":"§3.2.2, step 2 and Figure 5"},{"comment":"The pseudocode loops over all pairs (i,j) and defines y = (1/B(i,j)) Sigma U(i,:)^T, but it does not exclude pairs with B(i,j)=0. When B(i,j)=0, the rank-one update (19) is undefined, while Lemma 4 conditions on a pair with positive probability, which is precisely the condition that the pivot submatrix has nonzero volume and hence B(i,j) is nonzero. A correct implementation must skip zero pivots and restrict the search to pairs with B(i,j) != 0; this restriction is not stated in the algorithm or in Theorem 5. This is a well-definedness gap in the algorithm as written, though it is locally fixable.","section":"Algorithm 3, lines 6–14 and equation (19)"}],"minor_comments":[{"comment":"The sentence 'The cost of computing this bidiagonal matrix is O(m^2), which is identical with the cost of computing its singular values [20, Section 8.6]' is slightly ambiguous; it would be clearer to say that both the reduction and the subsequent bidiagonal SVD cost O(m^2) operations.","section":"§2.2, p. 6"},{"comment":"The caption should define the symbols × and ⊗ and state the matrix dimensions; in the current form, the figure is difficult to use for verifying the fill-in pattern or the number of rotations.","section":"Figure 5"},{"comment":"There is a typo: 'implemended' should be 'implemented'.","section":"§3.2.2"},{"comment":"References [31] and [32] are identical (both are Sorensen and Embree, 'A DEIM induced CUR factorization'); one of the two entries should be removed or replaced with a distinct citation.","section":"References"},{"comment":"The early-stopping variant is presented as a heuristic with empirical support, but the paper could note explicitly that the same induction as in Theorem 5 applies to any pair satisfying (21), which would make the theoretical guarantee for the early-stopping variant immediate.","section":"§2.4 and §3.2.2"}],"recommendation":"major_revision","confidential_remarks":"The missing bulge-chasing details are the main obstacle. I do not see circularity or novelty problems: the import from Zamarashkin and Osinsky is a legitimate black box, and the paper's own contribution is the derandomization and singular-value-based implementation. The paper is worth a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, the short version: this paper deserves a serious referee, and the referee should ask for one specific addition. The headline result is a deterministic polynomial-time algorithm for cross approximation with a guarantee that the Frobenius error stays within a factor k+1 of the best rank-k error. That is new relative to the literature they cite: Zamarashkin and Osinsky had an existence proof, Deshpande and Rademacher had a derandomized column subset selection, and the authors combine and extend both. Lemma 4 and Theorem 5 are coherent, and the SVD-based replacement for characteristic polynomial updates is a sensible fix for a known numerical instability. The tensor corollary is straightforward but useful.\n\nWhere it gets soft is the bulge-chasing procedure in Section 3.2.2. Algorithm 3's ratio (18) and the O(k m^3 n) complexity both rest on being able to update the SVD of a rank-one-modified bidiagonal-plus-row matrix in O(m^2). The paper gives a figure and says \"We refrain from giving a detailed description.\" That is load-bearing, not a detail. The stress test is right: if the bulge chase needs more than O(m^2) rotations, the complexity claim falls apart; if it is wrong, the ratios in line 13 are wrong and Theorem 5 does not follow. I do not think it is fatal, because the technique of reducing such a matrix to banded form is standard and likely works, but the burden is on the authors to provide pseudocode, rotation counts, or a reference that actually covers this exact matrix shape. That is a normal request for a numerical linear algebra paper claiming a complexity bound.\n\nA smaller issue: the pseudocode does not exclude pairs with B(i,j)=0, even though line 7 divides by it and Lemma 4 requires a nonzero pivot. That is easy to fix by skipping such pairs, but it should be stated. Also, the proof imports the existence bound from [38] as a black box; that is acceptable and not circular, though a statement of what exactly is imported would help.\n\nThe experiments are supportive, not a proof, and the authors are honest about the stability issues for larger k. The early stopping is heuristic but clearly shown to be effective on the test matrices. I would not require more than that for this result.\n\nWho is this for? Numerical linear algebra people working on cross approximation, CUR decompositions, and rank-revealing algorithms. The main theorem is the kind of gap-closing result the community has been asking for. My recommendation: send it to peer review, but make the review conditional on the authors supplying a complete, verifiable description of the bulge-chasing step. The paper is not there yet, but it is close, and the missing piece is substantial but repairable.","headline":"A genuinely new deterministic polynomial-time cross approximation algorithm with a (k+1)^2 guarantee—worth serious refereeing once the bulge-chasing step is actually described and proved.","tokens_in":20533,"tokens_out":1957,"would_cite":true,"duration_ms":18508,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F30","65F55"],"pacs":[],"model":"deepseek-v4-flash","headline":"A deterministic algorithm finds cross approximations within a factor k+1 of the best rank-k error.","keywords":["low-rank approximation","CUR decomposition","cross approximation","column subset selection","derandomization","conditional expectations","Frobenius norm","singular value update"],"falsifier":"For a random diagonal matrix Sigma with known singular values and random vectors x and y, compute the singular values of Sigma - x y^T using the bulge-chasing procedure as described in Section 3.2.2 and compare them against a direct high-precision SVD; a mismatch beyond roundoff would invalidate the O($m^{2}$) update that the polynomial-time claim depends on.","tokens_in":19520,"feed_emoji":"🧮","tokens_out":4014,"duration_ms":39036,"temperature":0.7,"pith_summary":"This paper describes a deterministic polynomial-time algorithm for cross approximation, a rank-k approximation built from selected rows and columns of a matrix. The authors claim the algorithm returns a cross approximation whose squared Frobenius-norm error is at most (k+1)^2 times the tail of the singular values, i.e., a factor k+1 over the best rank-k approximation error. They state this is the first such algorithm with a guaranteed polynomial error bound. The derivation derandomizes a recent existence result by Zamarashkin and Osinsky using the method of conditional expectations, and it avoids the numerical instability of earlier characteristic-polynomial updates by updating singular values directly.","feed_headline":"Cross approximation within a factor k+1 of optimal, deterministically","feed_subtitle":"A new algorithm finds rows and columns whose skeleton approximation is near the best rank-k error, in Frobenius norm.","key_machinery":"The central object is the conditional expectation of the cross-approximation error after t index pairs have been fixed. Lemma 4 shows this equals (k - t + 1)^2 times the ratio of characteristic polynomial coefficients c_{m-k+t-1}(BB^T) / c_{m-k+t}(BB^T) of the Schur-complement remainder B. The algorithm minimizes these ratios, and the paper evaluates them by forming a thin SVD B = U Sigma V^T, reducing each candidate update to a rank-one modification Sigma - x y^T of a diagonal matrix, and computing the singular values of that modification via O($m^{2}$) bulge-chasing and bidiagonalization steps. This replaces the cancellation-prone characteristic-polynomial updates of Deshpande and Rademacher with direct singular value computations, maintaining the same favorable complexity while improving numerical robustness.","core_discovery":"The paper's central claim is Theorem 5: Algorithm 3 returns row and column index sets I and J such that the cross approximation A(:,J)A(I,J)^{-1}A(I,:) satisfies the Frobenius-norm error bound ||A - A(:,J)A(I,J)^{-1}A(I,:)||$_F^{2}$ <= (k+1)^2 (sigma_{k+1}^2 + ... + $sigma_m^{2}$). This matches the best rank-k approximation error up to a factor k+1 in norm, and the paper asserts it is the first deterministic polynomial-time algorithm attaining a polynomial-in-k bound for cross approximation. The argument sequentially selects index pairs by minimizing conditional expectations of the approximation error under a volume-sampling distribution, and it computes the needed ratios from singular values of rank-one modifications of the current remainder matrix. Along with this, the paper contributes a numerically robust and faster variant of the Deshpande-Rademacher column subset selection algorithm, an early-stopping heuristic, and an extension to low multilinear rank tensor approximation.","pith_inferences":["The bulge-chasing step that the paper states without a full description is the most fragile link in the polynomial-time claim; if that step were replaced by a fully specified and verified O(m^2) SVD update, the deterministic complexity result would rest on firmer ground.","The conditional-expectation ratios depend on the volume-sampling distribution, so analogous derandomized algorithms could likely be designed for other distributions, such as those favoring max-volume submatrices, potentially yielding deterministic cross approximations with maximum-norm bounds.","The early-stopping heuristic introduces a data-dependent number of candidate pairs, so a rigorous average-case or expected complexity analysis might reveal that the practical running time is far below the worst-case O(k m^3 n).","The observed near-optimal performance on slowly decaying singular values suggests that the guaranteed (k+1) factor is loose for typical matrices, and a sharper analysis of the conditional-expectation chain might yield tighter constants."],"forward_implications":["If Theorem 5 is correct, cross approximation joins column subset selection as a low-rank tool with a certified polynomial error bound, closing a gap the paper identifies in the literature.","The algorithm's sequential index-pair selection can be stopped early once a candidate pair satisfies the sufficient condition (21), yielding large practical speedups in the experiments.","The same derandomization strategy applied to the Zamarashkin-Osinsky existence result suggests that other volume-sampling existence bounds could be converted into deterministic algorithms.","The tensor extension (Algorithm 4) gives a deterministic construction of a Tucker approximation from fibers of the tensor, with error within a factor sqrt(k1+k2+k3+3) of the best multilinear-rank approximation.","The early-stopping variant appears numerically more stable than the full search, as the experiments show that the full search can produce nearly singular intersection matrices A(I,J) for larger k."],"supporting_citations":[{"why":"Supplies the deterministic column subset selection algorithm and the method of conditional expectations that Algorithm 3 extends to cross approximation.","marker":"[14]"},{"why":"Supplies the volume-sampling distribution and the error bound (1) for column subset selection that the paper builds on and reuses in Corollary 2 and the tensor extension.","marker":"[15]"},{"why":"Supplies the existence bound (14) for cross approximation in the Frobenius norm, which the paper derandomizes into a deterministic algorithm.","marker":"[38]"},{"why":"Provides the bulge-chasing procedure cited for the SVD update step that transforms the rank-one modified matrix to bidiagonal form.","marker":"[37]"},{"why":"Provides the Summation Algorithm used to compute characteristic polynomial coefficients from squared singular values in a numerically forward stable manner.","marker":"[29]"},{"why":"Provides the Cauchy-Binet formula for pseudo-determinants that Lemma 4 uses to simplify the conditional-expectation ratio.","marker":"[26]"},{"why":"Supplies formula (19) for the rank-one remainder update in cross approximation, which underlies the derivation of the SVD updates in Algorithm 3.","marker":"[4]"},{"why":"Referenced for the contrasting observation that for symmetric positive definite matrices a symmetric index choice can attain the max-volume bound, which the Frobenius-norm setting does not inherit.","marker":"[12]"}],"fun_headline_variants":["Deterministic cross approximation within factor k+1 of optimal","First poly-time deterministic cross approximation with k+1 bound","No dice: deterministic cross approximation near-optimal","Cross approximation: deterministic, factor k+1 from optimal","Skeleton approximation without randomness: bound k+1"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The algorithm's claimed O(k $m^{3}$ n) running time and its deterministic guarantees rest on an unproven assertion that the bulge-chasing procedure computes the singular values of each rank-one modified diagonal matrix in O($m^{2}$) operations, since the paper says 'We refrain from giving a detailed description' and provides only a figure.","fun_headline_variants_meta":{"raw":{"variants":["Deterministic cross approximation within factor k+1 of optimal","First poly-time deterministic cross approximation with k+1 bound","No dice: deterministic cross approximation near-optimal","Cross approximation: deterministic, factor k+1 from optimal","Skeleton approximation without randomness: bound k+1"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000629,"raw_usage":{"total_tokens":2933,"prompt_tokens":996,"completion_tokens":1937,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":1858}},"tokens_in":612,"tokens_out":1937,"duration_ms":14572,"temperature":1.0,"reasoning_tokens":1858,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:56:56.245251+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a random diagonal matrix Sigma with known singular values and random vectors x and y, compute the singular values of Sigma - x y^T using the bulge-chasing procedure as described in Section 3.2.2 and compare them against a direct high-precision SVD; a mismatch beyond roundoff would invalidate the O($m^{2}$) update that the polynomial-time claim depends on.","supporting_citations":[{"cited_title":"Deshpande and L","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic column subset selection algorithm and the method of conditional expectations that Algorithm 3 extends to cross approximation."},{"cited_title":"Deshpande, L","cited_arxiv_id":null,"evidence_quote":"Supplies the volume-sampling distribution and the error bound (1) for column subset selection that the paper builds on and reuses in Corollary 2 and the tensor extension."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the existence bound (14) for cross approximation in the Frobenius norm, which the paper derandomizes into a deterministic algorithm."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the bulge-chasing procedure cited for the SVD update step that transforms the rank-one modified matrix to bidiagonal form."},{"cited_title":"Rehman and I","cited_arxiv_id":null,"evidence_quote":"Provides the Summation Algorithm used to compute characteristic polynomial coefficients from squared singular values in a numerically forward stable manner."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Cauchy-Binet formula for pseudo-determinants that Lemma 4 uses to simplify the conditional-expectation ratio."},{"cited_title":"Bebendorf","cited_arxiv_id":null,"evidence_quote":"Supplies formula (19) for the rank-one remainder update in cross approximation, which underlies the derivation of the SVD updates in Algorithm 3."},{"cited_title":"On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices","cited_arxiv_id":"1902.02283","evidence_quote":"Referenced for the contrasting observation that for symmetric positive definite matrices a symmetric index choice can attain the max-volume bound, which the Frobenius-norm setting does not inherit."}],"review_version":1}