{"id":"beb9260c-6397-4dc2-9cad-f519c4756cd5","arxiv_id":"2502.09823","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Toeplitz-like matrices, the paper proves explicit epsilon-rank bounds of order rho log(m) log(1/epsilon) for off-diagonal submatrices of the transformed matrix and uses them to build adaptive HODLR and HSS compressors with guaranteed error.","lead":"This paper derives explicit error bounds for how compressible a Fourier-transformed Toeplitz matrix is, showing that key off-diagonal submatrices have small numerical rank. The bounds justify and accelerate superfast hierarchical solvers for Toeplitz-like linear systems, and they lead to a deterministic alternative to randomized compression.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the disputed normalization in Theorem 2.2 is a standard scalar rotation of the coefficient spectra and achieves the claimed arc containment.","rationale":"The reader's weakest assumption focused on the normalization step in the proof of Theorem 2.2, claiming that multiplying by omega^{-2j-m+1} does not achieve the required arc containment. My re-derivation shows the opposite: scalar multiplication of a Sylvester equation rotates the spectra of the coefficient matrices by the angle of the scalar, and the specific scalar omega^{-2j-m+1} centers the column arc at 0 with half-width alpha, while the admissibility assumptions place the row arc in [beta, 2pi-beta] with beta = alpha + 2pi sep/n. This is a standard and correct application of the Zolotarev framework from [6]. I found no other flaw in the proof of Theorem 2.2 or its direct consequences for HODLR and HSS compression. The paper's secondary claim about HSS solver complexity relies on the external thesis [53] for detailed analysis, which is a caveat but does not undermine the central compression bounds. Therefore I do not see a load-bearing concern that would change the overall verdict.","tokens_in":20440,"tokens_out":30979,"duration_ms":261833,"concrete_test":"Independently re-derive the containment claim: take any (m,sep)-admissible J,K, choose s = omega^{-2j-m+1} where K subset of [j, j+m-1], and verify that Lambda(sD_K) subset of [-alpha, alpha] and Lambda(sD_J) subset of [beta, 2pi-beta] with alpha = pi(m-1)/n and beta = pi(m-1+2sep)/n. If these inclusions hold for representative admissible configurations, the proof of Theorem 2.2 is complete.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After careful re-derivation, the normalization step in the proof of Theorem 2.2 is valid. Multiplying the displacement equation D_J X - X D_K = Y by the unit-modulus scalar s = omega^{-2j-m+1} yields (sD_J) X - X (sD_K) = sY, which rotates both diagonal coefficient spectra by the same angle. For K subset of [j, j+m-1], the rotated spectrum of D_K is centered at angle 0 and lies in [-alpha, alpha] with alpha = pi(m-1)/n. The admissibility conditions min|j-k| >= sep and min|j-k-n| >= sep then force every element of J to have rotated angle in [beta, 2pi-beta] with beta = alpha + 2pi sep/n = pi(m-1+2sep)/n. Hence the hypotheses of the Zolotarev bound (2.3) are satisfied exactly as stated, and the central rank estimate (2.6) follows. The remaining concern, that the HSS construction's complexity analysis is deferred to [53], is real but does not bear on the correctness of Theorem 2.2, which is the load-bearing compression bound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes the numerical low-rank structure of the Cauchy-like matrix C obtained by applying a unitary Fourier transform to a Toeplitz-like matrix T with small displacement rank. The main result, Theorem 2.2, gives explicit ε-rank bounds for off-diagonal submatrices of C in terms of the displacement rank ρ, the block width m, and the separation parameter sep, covering both weak admissibility (sep = 1) and strong admissibility (sep ≥ m + 1). The bounds are derived from Zolotarev numbers and the authors use them to design fADI-based, deterministic HODLR and HSS compression algorithms, with numerical experiments illustrating the performance of a resulting Toeplitz solver.","tokens_in":20698,"tokens_out":26571,"duration_ms":273474,"significance":"If the results hold, the paper provides a substantial theoretical explanation for a compressibility phenomenon that is widely exploited in superfast Toeplitz solvers. The bounds have explicit constants, are parameter-free, and cover the weakly admissible case that earlier kernel-based analyses could not handle. The paper also offers a deterministic alternative to randomized HSS construction and gives explicit quasi-optimal fADI shift parameters via elliptic functions. These are concrete and checkable contributions, and the numerical experiments support the claims. The main derivation builds on the published, general Zolotarev bound of Beckermann and Townsend, so there is no circularity or fitted-parameter concern.","major_comments":[],"minor_comments":[{"comment":"The sentence 'By multiplying both sides of this equation with ω^{-2j-m+1}, we may assume without loss of generality...' is too terse for the central proof. The multiplication rotates both spectra by the same angle, and the subsequent arc containment for D_K and D_J follows from the two separation conditions in Definition 2.1, but this chain of reasoning should be written out explicitly. In particular, the phrase 'for some k ≥ 0' appears to be a typo and should read 'for some j'.","section":"§2.3, proof of Theorem 2.2"},{"comment":"Since rank_ϵ is integer-valued, the bound in (2.6) should include a ceiling (or an additive +1 absorbed into the constant) on the quantity (2/π²) log(4(m+sep-1)/sep) log(4/ε). As written, the step from the exponential bound (2.11) to (2.6) is not rigorously valid for non-integer values; the asymptotic statement is unaffected.","section":"Theorem 2.2, Eq. (2.6)"},{"comment":"Please specify the fADI shift parameters used for HSS rows and columns. For an HSS row X = C_row_v, the coefficient spectrum of D_J is the small arc while the spectrum of D_K is the large complementary arc, which is the reverse of the orientation in Theorem 2.2 and Corollary 3.1. The authors should state explicitly whether the roles of τ_j and ν_j from Lemma 2.4 are interchanged in this setting; as written, the 'straightforward extension of Corollary 3.1' leaves this ambiguity.","section":"§4.3.1 and Lemma 4.2"},{"comment":"The claim that the 2-norm of all errors committed on a fixed HODLR level ℓ remains bounded by ϵ∥C∥/log₂ n deserves a sentence of justification. It is true because the level-ℓ errors have a block-diagonal structure with 2×2 off-diagonal blocks, so the spectral norm is controlled by the maximum block norm, but this structural observation is not stated.","section":"Corollary 3.2 proof"},{"comment":"The caption refers to 'randomly chosen B,C' without defining these matrices; they should be identified as the generator matrices (or as eG, eH) used in the displacement equation (2.2).","section":"Figure 2 caption"},{"comment":"There is a typographical issue in the expression for ξ: 'ξ = exp(π²/(2 log(4m))' is missing a closing parenthesis. In addition, the parameter p in the lemma statement should be defined as p = kρ in the text before it is used in the error bound.","section":"Lemma 4.2, Eq. (4.7)"},{"comment":"The complexity bound O(n(ρ log n log 1/ε)²) for the HSS construction is stated to follow from [53, Ch. 4]. Since this is a PhD dissertation and may not be readily accessible, a short cost-accounting summary in the paper would improve self-containedness.","section":"§5, HSS complexity"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a serious contribution and the main Theorem 2.2 appears correct. The referee's main request is for the authors to make the normalization argument in the proof of Theorem 2.2 fully explicit and to clarify the shift-parameter choice in the HSS construction. The reliance on [53] for a complexity proof is acceptable but should be briefly summarized. Overall the manuscript is within scope for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Start with the punchline: the paper delivers something genuinely new—explicit epsilon-rank bounds for off-diagonal blocks of the transformed Toeplitz-like matrix C, including the weakly admissible (sep=1) case that previous circular-arc analyses could not handle. Theorem 2.2 gives O(ρ log m log(1/ε)) for generic blocks and O(ρ log(1/ε)) when sep ≥ m+1, and the bound matches observed singular value decay. The comparison with earlier results in Section 2.3.1 is honest and does not overstate novelty. The fADI-based interpolative decomposition in Sections 3–4 is a useful deterministic alternative to the randomized compression in [55], with explicit error bounds (Corollary 3.1, Lemma 4.2) and reasonable preliminary numerics.\n\nThe one concern raised in the review—the normalization step in the proof of Theorem 2.2—turns out to be fine on close reading. Multiplying (2.5) by ω^{-2j-m+1} rotates both diagonal spectra by the same angle. The admissibility conditions on J and K then put the K-spectrum in [-α, α] and the J-spectrum outside [β, 2π-β], exactly as needed to invoke the Zolotarev bound from [6]. I would call this an exposition issue rather than a gap: the phrase \"multiplying both sides by\" is doing a rotation, and the paper should say so explicitly. But the argument holds.\n\nReal soft spots are two. The complexity analysis of the HSS construction is deferred to Wilber's thesis [53]; the paper states O(n(ρ log n log(1/ε))^2) but does not prove it here. That is acceptable if the thesis is accessible, but self-containedness is a bit weak. The numerical experiments are also preliminary—random Toeplitz matrices only, no applications-driven examples—though for a theory paper that is a minor complaint. The citation pattern is clean: [6] is a published, general result, and the paper builds on it without circularity.\n\nWho is this for? Numerical linear algebraists working on superfast structured solvers, especially anyone who wants deterministic rather than randomized guarantees for HSS/HODLR compression of Toeplitz-like matrices. It should go to a serious referee: the proof of Theorem 2.2 and the elliptic function computations in Lemma 2.4 deserve careful checking, but the main result is likely correct and the weakly admissible bound is a real step forward. Send it to review.","headline":"New, correct epsilon-rank bounds for the weakly admissible case in Toeplitz-like compression; the disputed normalization in Theorem 2.2 is valid but terse, and the paper deserves a serious referee.","tokens_in":21194,"tokens_out":3563,"would_cite":true,"duration_ms":34259,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15B05","15A18","15A23","15A06","65F05","41A20"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves explicit ε-rank bounds for the off-diagonal blocks of a Cauchy-like transformed Toeplitz-like matrix: every (m, sep) block has ε-rank at most ρ (2/π²) log(4(m+sep−1)/sep) log(4/ε), which is O(ρ log m log 1/ε) in the…","keywords":["Toeplitz matrices","displacement structure","epsilon-rank","Zolotarev numbers","hierarchical low-rank approximation","HSS matrices","ADI method","superfast solver"],"falsifier":"Take n=8, m=2, sep=1, let J={2,...,7}, K={0,1}, and examine the normalized eigenvalue sets $ω^{{-2j-m+1}}$$ω^{{2j}}$ for j∈J and k∈K; if they do not lie in the arcs [β,2π−β] and [−α,α] with α=π(m−1)/n, β=π(m−1+2sep)/n, the proof's containment step is wrong, and the Zolotarev bound cannot be invoked.","tokens_in":20272,"feed_emoji":"🧮","tokens_out":6722,"duration_ms":56352,"temperature":0.7,"pith_summary":"This paper gives the first rigorous, explicit bounds on the numerical (ε-)rank of the off-diagonal submatrices that arise when a Toeplitz-like matrix is transformed into Cauchy-like form by a discrete Fourier transform. The bounds show that every (m,sep) off-diagonal block has ε-rank at most ρ (2/π²) log(4(m+sep−1)/sep) log(4/ε), which is O(ρ log m log 1/ε) in the weakly admissible setting and O(ρ log 1/ε) when the block is well separated from the diagonal. A sympathetic reader should care because these estimates provide the missing a priori justification for using HODLR, HSS, and other hierarchical low-rank formats inside superfast Toeplitz solvers, and they lead to a deterministic, adaptive compression algorithm whose cost and error are controlled by the same bounds.","feed_headline":"Toeplitz off-diagonal blocks have ε-rank O(log n log 1/ε)","feed_subtitle":"A displacement-structure proof supplies the missing theory for fast hierarchical Toeplitz solvers.","key_machinery":"The load-bearing object is the Zolotarev number Z_k(E1,E2), the infimum over rational functions of degree (k,k) of sup_{E1}|r| / inf_{E2}|r|, for two disjoint arcs E1,E2 of the unit circle. The paper proves that the submatrix's displacement equation can be reduced to this setting, and that the Möbius transform of the arcs turns the Zolotarev problem into one for real intervals where known bounds apply. The same Zolotarev rational functions supply the shift parameters for the fADI iteration used to construct the low-rank factors, so the theoretical bound directly becomes an algorithm.","core_discovery":"The central claim is Theorem 2.2: for any (m, sep) submatrix C_{JK} of the transformed Cauchy-like matrix C, rank_ε(C_{JK}) ≤ ρ (2/π²) log(4(m+sep−1)/sep) log(4/ε). The proof shows that C_{JK} satisfies a Sylvester equation with diagonal coefficients, that the spectra of these diagonals can be placed in disjoint arcs of the unit circle, and that the Zolotarev number for these arcs decays exponentially with rate given by (2.11). This yields the first effective rank bounds that cover both weakly admissible (sep=1) and strongly admissible (sep≥m+1) block partitions, and it explains why the practical randomized compression of Toeplitz matrices works as well as it does.","pith_inferences":["The same displacement-arc technique should extend to other unitary similarity transforms of Toeplitz-like matrices, not just the DFT, as long as the generator eigenvalues lie on a circle or a curve with controlled geometry.","The strong-admissibility bound suggests a hierarchical solver that switches from weak to strong admissibility at deeper levels could reach near-linear complexity, which the authors note but do not implement.","One could test the sharpness of the constant 2/π² by comparing the bound to numerically computed Zolotarev numbers for the arcs; the gap may reveal whether the factor 4 in the log is loose.","The deterministic fADI-based compression could be combined with randomized column subset selection to reduce the hidden constant in practice while preserving the theoretical guarantees."],"forward_implications":["Every off-diagonal block of C in a weakly admissible hierarchical partition has ε-rank O(ρ log m log 1/ε), so HODLR and HSS ranks remain small even for very large n.","In the strongly admissible case (sep≥m+1), the ε-rank is O(ρ log 1/ε), independent of n, suggesting that linear-complexity direct solvers using strong-admissibility formats are within reach.","The fADI-based interpolative decompositions give a deterministic counterpart to the randomized Toeplitz solver, with explicit a priori rank choices and guaranteed error bounds.","The bounds justify the use of weakly admissible formats such as HODLR and HSS, which prior analyses could not handle in the sep=1 case.","The overall HSS-based solver for T x=b runs in O(n(ρ log n log 1/ε)^2) operations, matching randomized methods in practice."],"supporting_citations":[{"why":"Supplies the Zolotarev bound σ_{kρ+1}(X) ≤ Z_k(E1,E2)||X||_2 and the invariance of Zolotarev numbers under Möbius transformations that Theorem 2.2 relies on.","marker":"[6]"},{"why":"Originated the observation that the transformed Cauchy-like matrix has compressible off-diagonal blocks and introduced a superfast Toeplitz solver; this paper completes the missing analysis.","marker":"[13]"},{"why":"Provides the randomized HSS construction via interpolative decompositions that the deterministic fADI scheme of this paper is designed to replace.","marker":"[37]"},{"why":"The randomized superfast Toeplitz solver that serves as the practical baseline; this paper's bounds make its rank choices a priori and propose a deterministic analogue.","marker":"[55]"},{"why":"Gives an earlier Chebyshev-based bound for circular arcs that works only in the strongly admissible case, motivating the weakly admissible result here.","marker":"[18]"},{"why":"Gives the 3^{-k} bound for strongly admissible Cauchy blocks, which also fails for sep=1; the present theorem subsumes it.","marker":"[34]"},{"why":"Introduces the factored ADI (fADI) algorithm whose convergence the Zolotarev shifts from Lemma 2.4 control.","marker":"[7]"},{"why":"Supplies the ULV-type solver used to solve the HSS linear system in Step 3 of Algorithm 1.1 after compression.","marker":"[12]"}],"fun_headline_variants":["Proof: Toeplitz-like blocks have ε-rank O(log n log 1/ε)","Zolotarev numbers pin down Toeplitz block ranks","Displacement structure explains Toeplitz compressibility","Tight ε-rank bounds proven for Toeplitz-like matrices","Why Toeplitz solvers are fast: proven rank bounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central bound assumes that the eigenvalue sets of the two diagonal matrices in the submatrix displacement equation can always be enclosed in two disjoint arcs of the unit circle with the required gap; the proof's normalization step for achieving this containment is not fully justified as written.","fun_headline_variants_meta":{"raw":{"variants":["Proof: Toeplitz-like blocks have ε-rank O(log n log 1/ε)","Zolotarev numbers pin down Toeplitz block ranks","Displacement structure explains Toeplitz compressibility","Tight ε-rank bounds proven for Toeplitz-like matrices","Why Toeplitz solvers are fast: proven rank bounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001329,"raw_usage":{"total_tokens":5362,"prompt_tokens":854,"completion_tokens":4508,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":470,"completion_tokens_details":{"reasoning_tokens":4413}},"tokens_in":470,"tokens_out":4508,"duration_ms":29402,"temperature":1.0,"reasoning_tokens":4413,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T20:25:44.823876+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take n=8, m=2, sep=1, let J={2,...,7}, K={0,1}, and examine the normalized eigenvalue sets $ω^{{-2j-m+1}}$$ω^{{2j}}$ for j∈J and k∈K; if they do not lie in the arcs [β,2π−β] and [−α,α] with α=π(m−1)/n, β=π(m−1+2sep)/n, the proof's containment step is wrong, and the Zolotarev bound cannot be invoked.","supporting_citations":[{"cited_title":"Beckermann and A","cited_arxiv_id":null,"evidence_quote":"Supplies the Zolotarev bound σ_{kρ+1}(X) ≤ Z_k(E1,E2)||X||_2 and the invariance of Zolotarev numbers under Möbius transformations that Theorem 2.2 relies on."},{"cited_title":"Chandrasekaran, M","cited_arxiv_id":null,"evidence_quote":"Originated the observation that the transformed Cauchy-like matrix has compressible off-diagonal blocks and introduced a superfast Toeplitz solver; this paper completes the missing analysis."},{"cited_title":"Martinsson, A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix , SIAM J","cited_arxiv_id":null,"evidence_quote":"Provides the randomized HSS construction via interpolative decompositions that the deterministic fADI scheme of this paper is designed to replace."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The randomized superfast Toeplitz solver that serves as the practical baseline; this paper's bounds make its rank choices a priori and propose a deterministic analogue."},{"cited_title":"Dutt and V","cited_arxiv_id":null,"evidence_quote":"Gives an earlier Chebyshev-based bound for circular arcs that works only in the strongly admissible case, motivating the weakly admissible result here."},{"cited_title":"Lepilov and J","cited_arxiv_id":null,"evidence_quote":"Gives the 3^{-k} bound for strongly admissible Cauchy blocks, which also fails for sep=1; the present theorem subsumes it."},{"cited_title":"Benner, R.-C","cited_arxiv_id":null,"evidence_quote":"Introduces the factored ADI (fADI) algorithm whose convergence the Zolotarev shifts from Lemma 2.4 control."},{"cited_title":"Chandrasekaran, M","cited_arxiv_id":null,"evidence_quote":"Supplies the ULV-type solver used to solve the HSS linear system in Step 3 of Algorithm 1.1 after compression."}],"review_version":1}