{"id":"3c7ffa30-86e9-4a48-aa6d-88dbccad9dbb","arxiv_id":"1908.09376","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A two-step framework recovers multidimensional phase functions from indirect operator access and factorizes the kernel with a butterfly structure for O(N log N) matvecs.","lead":"This paper presents a way to rapidly evaluate oscillatory integral transforms, like wave propagation and imaging operators, even when the phase function is not explicitly known but can only be applied as a black-box operator. It recovers the phase from a few rows and columns, then compresses the matrix with a butterfly factorization for near-linear cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Phase recovery lacks any sampling condition ensuring MST edge phase increments stay below 1/2 (and below tau=1/4 for Lemma 2.5); on nonuniform 2D/3D grids smooth phases can be split into many false discontinuities or rounded to wrong integer lifts, so the O(N log N) recovery claim is unproved and…","rationale":"The reader's verdict was CONDITIONAL, with the weakest assumption being the unproved Lemma 2.5 and the absence of a sampling condition for Algorithm 4's rounding. My stress-test identifies the same load-bearing weakness and sharpens it: the missing condition is not merely a proof gap. For nonuniform grids, MST edges can have arbitrarily large spatial length, so a smooth phase with modest gradient can produce phase increments above 1/2 or even above 1/4. Algorithm 4 then either mis-rounds the lift or reports false discontinuities, and if this happens on many edges the recovered Psi is not a low-rank perturbation of the true phase, invalidating the randomized low-rank factorization that feeds MIDBF. The numerical experiments in Tables 2, 4, and 5 use grids whose nearest-neighbor spacing is small enough that phase increments stay far below 1/4; thus they do not test the advertised general nonuniform setting. The 3D Delaunay triangulation claim in Section 2.3.3 is also questionable -- in 3D, a Delaunay triangulation need not be planar and can have superlinear size -- but the phase sampling condition is more central because it concerns correctness, not just worst-case complexity. Since the paper presents a framework with plausible heuristics and encouraging numerics, a conditional acceptance with a required sampling condition and a proof of Lemma 2.5 remains the appropriate verdict; my concern does not change that assessment.","tokens_in":35066,"tokens_out":10238,"duration_ms":117096,"concrete_test":"Construct a smooth 2D phase with large gradient and a deliberately nonuniform grid containing many gaps, e.g., X1=X2 as 64 clusters of 16 points each, cluster centers separated by about 0.1, and Phi(x,xi)=10*x1+10*xi1 so gap-crossing MST edges have true phase increments exceeding 1/2. Run RecoveryMatrix2 with tau=1/4 on one row and one column. Check (1) the numbers NDr, NDc of detected discontinuities: for a smooth phase these should be O(1), but they will scale with the number of clusters if the missing sampling condition is needed; (2) whether the recovered row and column values agree at their intersection, testing Lemma 2.5; and (3) whether the recovered Psi admits a rank-r approximation with r=O(1) and e^{2*pi*i*Psi} approximating K. If NDr/NDc grow with the number of clusters or intersections disagree, the phase recovery claim fails without an additional sampling condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 4 (RecoveryVector2) reconstructs each lifted phase value by v(ed) = u(ed) - round(u(ed) - v(bg)) in Line 5. This rounding is correct only when the true unwrapped phase difference across the MST edge lies in (-1/2, 1/2]; otherwise the wrong integer is selected and the error propagates along the path. The discontinuity test in Line 6 then flags any lifted difference with magnitude at least tau=1/4, so every MST edge whose true phase increment exceeds 1/4 is declared a discontinuity. For nonuniform grids in d=2 or 3, MST edges can connect points separated by large gaps or across low-density regions, so a perfectly smooth phase can produce many false discontinuities, and increments larger than 1/2 cause incorrect integer lifts. Lemma 2.5, which is the only stated guarantee that independently recovered rows and columns agree at intersections, assumes the stronger condition that every row and column belongs to C_{tau,P} with tau<=1/4, and its proof is explicitly omitted ('leave the proof to the reader'). No sampling or smoothness condition on the phase or the point sets is stated that would ensure this hypothesis. The numerical examples are all well resolved, with nearest-neighbor phase increments far below 1/4, so they do not exercise the failure mode. Consequently, the recovered matrix Psi need not be a low-rank perturbation of the true phase, and the low-rank factorization feeding MIDBF can be invalid.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-stage framework for evaluating multidimensional oscillatory transforms g=Kf when only indirect access to the kernel K(x,ξ)=exp(2πiΦ(x,ξ)) is available. Stage one recovers a low-rank factorization of the phase matrix Φ from O(1) rows and columns obtained through black-box matvecs, using Delaunay triangulation and minimum spanning trees to build a recovery path and a first-order phase-unwrapping procedure. Stage two adapts the interpolative decomposition butterfly factorization (IDBF) to multidimensional and nonuniform settings, yielding an O(N log N) matvec once the phase is available. Numerical experiments for 2D Fourier integral operators, 3D nonuniform FFTs, and a Helmholtz Green's function example are reported, with complexity and accuracy tables.","tokens_in":35436,"tokens_out":2871,"duration_ms":32233,"significance":"If the claims hold, this is a substantial contribution: it would provide the first nearly linear framework for multidimensional oscillatory transforms with indirect kernel access and nonuniform grids, and the MIDBF generalization of IDBF is a natural and useful extension. The manuscript is also commendable for shipping reproducible code in ButterflyLab and for reporting wall-clock scaling against direct evaluation. The central weakness is that the phase-recovery step, which is the genuinely new component, rests on an unproved consistency lemma and an empirically chosen discontinuity threshold, with no stated sampling condition that would make the recovery provably correct.","major_comments":[{"comment":"The recovery of v(ed) = u(ed) - round(u(ed)-v(bg)) in Line 5 is correct only when the true unwrapped phase increment across the MST edge lies in (-1/2, 1/2]; otherwise the wrong integer lift is selected and the error propagates along the recovery path. The discontinuity test in Line 6 flags every edge with |v(ed)-v(bg)| >= τ, with τ = 1/4 in the reported experiments, so a perfectly smooth phase on a nonuniform grid can produce many false discontinuities whenever an MST edge connects points separated by a large gap. No sampling condition on the point sets or smoothness condition on Φ is stated that would ensure MST phase increments stay below 1/2, or below 1/4 for the consistency lemma. This missing hypothesis is load-bearing because false discontinuities can create many submatrices in Partition2 and invalidate the O(N log N) recovery complexity as well as the accuracy of the recovered phase.","section":"§2.3.2, Algorithm 4"},{"comment":"Lemma 2.5 is the only stated guarantee that rows and columns recovered independently in Algorithm 6 agree at their intersections, and it is left unproved with the sentence 'we leave the proof to the reader.' The lemma assumes all rows and columns belong to C_{τ,P} with τ ≤ 1/4, but no argument is given that this class condition is satisfied by the actual rows and columns of a piecewise smooth phase matrix on a nonuniform grid, nor that the MST-based recovery path respects the class. Without this lemma, the input rows and columns fed to randomizedSVD in Algorithm 7 need not be consistent at shared entries, so the recovered Ψ need not equal Φ plus a numerically low-rank integer-valued perturbation, and the subsequent low-rank factorization feeding MIDBF has no rigorous accuracy guarantee.","section":"§2.3.4, Lemma 2.5"},{"comment":"The numerical validation does not exercise the failure mode identified above: all reported examples are well resolved, with nearest-neighbor phase increments far below the threshold τ = 1/4, and Table 3 only varies τ on the 3D nonuniform FFT, showing that smaller thresholds create many detected discontinuities at small n. No experiment with deliberately coarse or highly nonuniform grids, large phase gradients, or constructed counterexamples is reported, so the statement that 'τ = 1/4 is good enough for all numerical examples' cannot support the general O(N log N) recovery claim. The authors should either prove a sampling condition under which the algorithm succeeds, or demonstrate numerically that the failure mode is benign for the target class of problems.","section":"§4.1, Tables 3-5 and parameter settings"}],"minor_comments":[{"comment":"The phrase 'O(N log(N)) time and memories complexity' should read 'memory complexity'.","section":"Abstract"},{"comment":"The column header 'N Dr NDc' appears to be a typographical corruption of 'NDr' and 'NDc'; this makes the table harder to read.","section":"Table 3"},{"comment":"The sentence 'When τ increases to 1/2, no more discontinuous point will be detected' is imprecise: with the test |v(ed)-v(bg)| ≥ τ, increments strictly exceeding 1/2 would still be flagged, though the rounding step would already be unreliable in that regime.","section":"§2.3.4"},{"comment":"The formulas for the middle-factor entries S^L_{ij} use unwieldy index arithmetic; a short definition of the skeleton index blocks would improve readability.","section":"§3.5, Eq. (22)"}],"recommendation":"major_revision","confidential_remarks":"The novelty of the paper is concentrated in the phase-recovery algorithm of Section 2, while the MIDBF of Section 3 is an extension of the authors' earlier IDBF work. The referee report focuses on the missing proof of Lemma 2.5 and the absence of a sampling condition for Algorithm 4; these are fixable in principle but currently block acceptance. The paper would also benefit from an explicit statement that the recovered phase error E is integer-valued and from a proof that E is numerically low-rank under the stated assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper splits into two halves with very different temperatures. The MIDBF part is exactly what it says: a careful multidimensional generalization of the interpolative decomposition butterfly factorization, with clean algorithms, complexity counts, and reproducible numerical scaling. That half deserves credit and will be useful to people working on FIOs and oscillatory integrals. The phase-recovery half is the real novelty—extending the 1D indirect-access recovery of Yang via Delaunay triangulation and MST is a natural idea, and the recovery-path construction is elegant—but it is also where the paper has a load-bearing gap, and the stress-test note is right about it. Algorithm 4's rounding only selects the correct integer lift when the true unwrapped phase increment along each MST edge lies in (-1/2, 1/2]. No sampling, smoothness, or density condition is stated that would guarantee this for nonuniform 2D/3D grids. In low-density regions an MST edge can connect points far apart, the phase increment exceeds 1/2, and the error propagates across the whole recovered row or column. The discontinuity test then compounds the problem: any increment at or above tau = 1/4 is declared a discontinuity, so a perfectly smooth phase can be chopped into false pieces. Lemma 2.5, which is the only stated consistency guarantee for the entire matrix recovery, assumes every row and column lies in C_{tau,P} with tau <= 1/4 and its proof is explicitly left to the reader. That is not a minor omission; the whole framework's O(N log N) phase recovery is unproved for the cases the paper advertises. The numerical examples are all well-resolved, with nearest-neighbor increments far below the threshold, so they don't exercise the failure mode. I agree with the conditional verdict. The MIDBF portion is sound and publishable on its own; the phase recovery needs either a rigorous sampling condition with a proof of Lemma 2.5, or an honest limitation section saying the method is heuristic for nonuniform grids. This deserves a serious referee and a request for major revision, not a desk reject. I'd bring it to reading group mainly to discuss the gap; I wouldn't cite it in my own work until the recovery claim is repaired.","headline":"The MIDBF half is a solid extension of existing butterfly machinery; the phase-recovery half is genuinely new but its main lemma is unproved and the O(N log N) claim needs a sampling condition that isn't there.","tokens_in":35929,"tokens_out":1446,"would_cite":false,"duration_ms":17073,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65F30","65T50","65R20"],"pacs":[],"model":"deepseek-v4-flash","headline":"When the matrix can be applied but not inspected, the phase function behind a 2D or 3D oscillatory transform can be recovered and factorized in O(N log N) work.","keywords":["phase recovery","butterfly factorization","interpolative decomposition","oscillatory integral transform","minimum spanning tree","Delaunay triangulation","low-rank matrix factorization","nonuniform grids"],"falsifier":"Take a 2D nonuniform grid and a smooth phase function with a steep gradient such that two MST-adjacent points have true phase difference 0.6; run the recovery with $\\tau=1/4$ and check whether the recovered row and column phases at their intersection agree: if the rounding picks a lift off by one, the intersection will fail and the kernel reconstruction error will jump to $O(1)$.","tokens_in":34858,"feed_emoji":"🦋","tokens_out":8292,"duration_ms":77358,"temperature":0.7,"pith_summary":"The paper claims that a multidimensional oscillatory integral transform $g(x)=\\int e^{2\\pi i\\Phi(x,\\xi)}f(\\xi)\\,d\\xi$ in dimensions two and three can be evaluated in $O(N\\log N)$ time and memory even when the phase function $\\Phi$ is accessible only through a black-box routine that applies the kernel matrix or its transpose to a vector. The proposed framework first recovers a low-rank representation of the phase matrix from $O(1)$ rows and columns obtained that way, using a Delaunay-triangulation/minimum-spanning-tree path to unwrap phase values on nonuniform grids, and then compresses the kernel with a multidimensional interpolative decomposition butterfly factorization (MIDBF). A sympathetic reader would care because this closes the gap between explicit-formula fast transforms and the many applications—wave propagation, generalized Radon transforms, Green's functions—where only indirect access to the phase is available.","feed_headline":"Recover hidden phase, then butterfly-factorize: O(N log N) for 2D/3D","feed_subtitle":"New framework recovers the phase from indirect access and applies the transform in near-linear time.","key_machinery":"The machinery has two load-bearing pieces. The first is the recovery path matrix $P$, built by computing the Delaunay triangulation of the grid points, extracting a minimum spanning tree, and ordering its nodes breadth-first; $P$ tells the unwrapping algorithm which phase values are physically adjacent and should be unwrapped together, replacing the one-dimensional ordering that fails on nonuniform multidimensional grids. The second is the MIDBF, a recursive factorization $K\\approx U_L U_{L-1}\\cdots U_h S_h V_h\\cdots V_L$ built from alternating leaf-root complementary skeletonization and matrix splitting with complementary skeletonization, which exploits the complementary low-rank property of oscillatory kernel blocks to keep every factor sparse.","core_discovery":"The central claim is that indirect access to the phase function is enough to build a nearly linear fast matvec for oscillatory kernels in $d=2,3$. Because only $e^{2\\pi i\\Phi}$ is observable, the phase is known modulo $1$; the paper shows that unwrapping along an MST-based recovery path, with threshold $\\tau=1/4$ separating genuine discontinuities from artificial ones, recovers smooth rows and columns of $\\Phi$ up to a numerically low-rank error. These recovered low-rank factors provide an $O(1)$-cost entry oracle for the kernel, which the MIDBF turns into a product of sparse interpolative-decomposition factors. The paper claims end-to-end $O(N\\log N)$ complexity for recovery, factorization, and application, and presents numerical experiments for a 2D generalized Radon transform, a 3D nonuniform Fourier transform, and the oscillatory Green's function of the Helmholtz equation.","pith_inferences":["Because the unwrapping only uses physical adjacency, the same MST path construction could serve other phase-unwrapping problems—interferometry, MRI, or wavefield reconstruction—on irregular sampling sets, a direction the paper does not explore.","The correctness of the recovery depends on the threshold $\\tau=1/4$ and on the MST path not crossing two discontinuities in one step; a testable extension would be an adaptive or higher-order finite-difference version that relaxes this requirement, which the paper flags as future work.","A natural next step is to characterize phase families where the numerical rank of recovered phase matrices provably stays constant, since the $O(N\\log N)$ complexity relies on that."],"forward_implications":["The framework removes the need for explicit phase formulas: any kernel matvec available in Scenario 2 becomes compressible in $O(N\\log N)$ time.","Phase recovery itself becomes a nearly linear precomputation, so the total cost of setting up and applying the butterfly factorization stays nearly linear rather than quadratic.","The recovery-path construction and MIDBF extend naturally from uniform to nonuniform grids and from 2D to 3D, covering problems like nonuniform Fourier transforms and surface Green's functions.","For PDE-driven phases (Scenario 3), the recovery step can be skipped, so the same factorization machinery applies directly to rows and columns obtained from PDE solves."],"supporting_citations":[{"why":"supplies the 1D TV3 phase-recovery algorithms that the multidimensional method generalizes.","marker":"[38]"},{"why":"introduces the 1D interpolative decomposition butterfly factorization that MIDBF extends.","marker":"[28]"},{"why":"defines the complementary low-rank property and butterfly factorization that MIDBF builds upon.","marker":"[21]"},{"why":"provides the randomized sampling procedure used for low-rank factorization of the recovered phase matrix.","marker":"[12]"},{"why":"states that the edges of a Delaunay triangulation contain a minimum spanning tree, the key geometric fact behind the recovery path.","marker":"[9]"},{"why":"gives an $O(N\\log N)$ Delaunay triangulation algorithm for the required dimensions.","marker":"[5]"},{"why":"provides the minimum spanning tree algorithm used to obtain the recovery path from the Delaunay graph.","marker":"[29]"},{"why":"breadth-first search traverses the MST to order the recovery path matrix.","marker":"[19]"}],"fun_headline_variants":["Phase from indirect access: O(N log N) butterfly factorization","Indirect phase? Recover it, then butterfly-factorize in near-linear time","2D/3D oscillatory transforms: near-linear via phase recovery + MIDBF","Hidden phase to fast matvec: O(N log N) for oscillatory kernels","Recover phase, factorize butterflies: O(N log N) in 2D/3D"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The recovery succeeds only when every pair of adjacent points on the minimum-spanning-tree path has true phase difference below the threshold $\\tau=1/4$ (except at genuine discontinuities), because only then does the rounding step in the unwrapping choose the correct integer lift; the paper states no sampling condition guaranteeing this for nonuniform 2D and 3D grids, and the lemma asserting consistency of recovered row/column intersections is left unproved.","fun_headline_variants_meta":{"raw":{"variants":["Phase from indirect access: O(N log N) butterfly factorization","Indirect phase? Recover it, then butterfly-factorize in near-linear time","2D/3D oscillatory transforms: near-linear via phase recovery + MIDBF","Hidden phase to fast matvec: O(N log N) for oscillatory kernels","Recover phase, factorize butterflies: O(N log N) in 2D/3D"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000571,"raw_usage":{"total_tokens":2709,"prompt_tokens":961,"completion_tokens":1748,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":577,"completion_tokens_details":{"reasoning_tokens":1641}},"tokens_in":577,"tokens_out":1748,"duration_ms":11457,"temperature":1.0,"reasoning_tokens":1641,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:13:20.148735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a 2D nonuniform grid and a smooth phase function with a steep gradient such that two MST-adjacent points have true phase difference 0.6; run the recovery with $\\tau=1/4$ and check whether the recovered row and column phases at their intersection agree: if the rounding picks a lift off by one, the intersection will fail and the kernel reconstruction error will jump to $O(1)$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the 1D TV3 phase-recovery algorithms that the multidimensional method generalizes."},{"cited_title":"Interpolative Decomposition Butterfly Factorization","cited_arxiv_id":"1809.10573","evidence_quote":"introduces the 1D interpolative decomposition butterfly factorization that MIDBF extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"defines the complementary low-rank property and butterfly factorization that MIDBF builds upon."},{"cited_title":"Engquist and L","cited_arxiv_id":null,"evidence_quote":"provides the randomized sampling procedure used for low-rank factorization of the recovered phase matrix."},{"cited_title":"de Berg, O","cited_arxiv_id":null,"evidence_quote":"states that the edges of a Delaunay triangulation contain a minimum spanning tree, the key geometric fact behind the recovery path."},{"cited_title":"Buchin and W","cited_arxiv_id":null,"evidence_quote":"gives an $O(N\\log N)$ Delaunay triangulation algorithm for the required dimensions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides the minimum spanning tree algorithm used to obtain the recovery path from the Delaunay graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"breadth-first search traverses the MST to order the recovery path matrix."}],"review_version":1}