{"id":"4c1d8fa4-94bd-40fa-8a1a-85b58978e16a","arxiv_id":"1908.00887","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The ADRT can be exactly inverted from partial (single-quadrant) data in O(N log N) operations.","lead":"An exact formula to invert the approximate discrete Radon transform (ADRT) from a single quadrant of data runs in O(N log N) time for an N-pixel image. The result makes inversion as cheap as the forward transform, which could speed up tomography-style algorithms built on the ADRT.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central inversion lemma is unsupported: Definition 3's recursion is ill-posed, and under the natural correction Eq (2.6) fails in a small explicit case, so Theorem 1 is not established.","rationale":"The reader identified Definition 3's recursion as the weak point and gave a CONDITIONAL verdict, treating the issue as a fixable typo. My reading shows the problem is more severe: the recursion as written is not merely misprinted but undefined, because it calls D_{m-1} with a second argument outside its declared range. The most natural repair (the standard Brady recursion) is not a minor cosmetic fix: it removes the cancellation in the proof of (2.6), and an explicit small computation shows (2.6) is false. Since Lemma 6 supplies the entire recursive inversion, the central claim of an exact O(N log N) inverse is unsupported by the manuscript. This is a load-bearing correctness failure rather than a gap in presentation. The proposed test settles the issue decisively: reproducing the counterexample would confirm the lemma is false, while a successful match would invalidate my concern. Because the current proof contains a false identity, acceptance in the present form is not warranted; the appropriate disposition is REJECT, unless the author can supply a different proof of invertibility that does not depend on the failing cancellation.","tokens_in":3706,"tokens_out":25137,"duration_ms":211735,"concrete_test":"Write a short program implementing the ADRT with the standard repaired recursion D_m(h,2t)=D^1_{m-1}(h,t) union D^2_{m-1}(h+t,t), D_m(h,2t+1)=D^1_{m-1}(h,t) union D^2_{m-1}(h+t+1,t+1), with D_0(h,s)={(h,1)} and allowing t=0. Set image A(i,j)=i on an 8x8 pixel grid (n=m=3) and evaluate Eq (2.6) for h=0, s=1: the left side R_{3,2}(1,1)-R_{3,2}(0,1) equals 4, while the right side R_{3,3}(1,2)-R_{3,3}(0,3) equals 3. If reproduced, Lemma 6 and the claimed O(N log N) inversion formula fail for the only coherent reading of Definition 3.","verdict_should_be":"REJECT","load_bearing_attack":"The theorem rests entirely on Lemma 6, which asserts that R_{n,m-1} can be recovered from R_{n,m} via the difference identities (2.6)-(2.7). The proof of these identities is invalid at the point of definition. In Definition 3, Eq (2.2), D_m(h,2t) and D_m(h,2t+1) are defined in terms of D^2_{m-1}(h+t,s) and D^2_{m-1}(h+t+1,s), where s is the level-m parameter. Since D_{m-1} is declared only for second arguments 1..2^{m-1}, for most s these expressions are undefined; the recursion is therefore ill-posed. If one repairs the evident typo by replacing s with t or t+1 (the standard Brady recursion), the top-half terms in the displayed computation of (2.6) are no longer equal, so the cancellation used to obtain (2.6) disappears. The repair does not rescue the lemma: for an 8x8 image A(i,j)=i with n=m=3,s=1, direct computation gives R_{3,2}(h+1,1)-R_{3,2}(h,1)=4, whereas the right-hand side of (2.6), R_{3,3}(h+1,2)-R_{3,3}(h,3), equals 3. Thus (2.6) is false. Since Lemma 6 is the whole inversion algorithm, Theorem 1 is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims that the approximate discrete Radon transform (ADRT) of Brady can be inverted exactly from a single quadrant of transform data in O(N log N) operations for an N-pixel square image. The proposed inversion recursively recovers the ADRT of smaller sections of the image from the ADRT of larger sections, using difference identities (2.6) and (2.7). The main theorem is stated as Theorem 1 and is derived directly from Lemma 6, which asserts that each level-m ADRT can be reduced to the two level-(m-1) section transforms in linear time.","tokens_in":4013,"tokens_out":4745,"duration_ms":43395,"significance":"If the central claim were correct, it would be a notable result: an exact, fast inverse of the ADRT with the same asymptotic cost as the forward transform, and requiring only partial data. The paper is self-contained in its derivation and does not rely on fitted parameters or circular normalization choices, which is a strength. However, the validity of the main theorem hinges entirely on the recursive definition of digital lines and the difference identities of Lemma 6. As detailed below, the recursion as stated is ill-posed and the identities are false under a natural correction, so the claimed inversion formula is not established. The paper therefore does not, in its current form, support the advertised conclusion.","major_comments":[{"comment":"Definition 3 is ill-posed. In Eq. (2.2), D_m(h,2t+1) and D_m(h,2t) are defined in terms of D^2_{m-1}(h+t+1,s) and D^2_{m-1}(h+t,s), respectively, where s is the level-m argument (2t+1 or 2t). But D_{m-1} is only defined for second arguments in {1,...,2^{m-1}}. For s>2^{m-1}, the expressions D^2_{m-1}(...,s) are undefined, so the recursion does not define D_m for most of its domain. This renders the subsequent use of D_m in the ADRT definition and in Lemma 6 invalid as written.","section":"Definition 3, Eq. (2.2)"},{"comment":"The proof of Lemma 6 relies on an expansion that is inconsistent with Definition 3. For example, the term R_{\\ell;n,m}(h+1,2s) is expanded using D_m(h+1,2s) = D^1_{m-1}(h+1,s) \\cup D^2_{m-1}(h+s+1,s), but according to Definition 3 the second part should be D^2_{m-1}(h+s+1,2s) (or, with the natural correction of the recursion, D^2_{m-1}(h+s+1,t) with t related to s), not D^2_{m-1}(h+s+1,s). The cancellation that produces Eq. (2.6) depends on this incorrect substitution, so the identity is not proven.","section":"Lemma 6, proof display after Eq. (2.6)"},{"comment":"The claimed identity (2.6) is false under the standard corrected digital-line recursion. For the 8x8 image A(i,j)=i with n=m=3 and s=1, direct computation gives R_{3,2}(h+1,1)-R_{3,2}(h,1)=4, whereas the right-hand side of (2.6), R_{3,3}(h+1,2)-R_{3,3}(h,3), equals 3 for the same h. Thus the identity fails in a concrete case. Since Lemma 6 is the sole inversion step used to prove Theorem 1, the main theorem is not established.","section":"Lemma 6, Eq. (2.6)"},{"comment":"Lemma 5 is stated without proof, but its properties are load-bearing: property (iii) is used in Eq. (2.8) to truncate the prefix sum that reconstructs R_{\\ell;n,m-1} from the differences, and property (v) is used to justify the lower limit of summation. As written, the lemma is an unproved input to the central derivation. This would be a gap even if the recursion in Definition 3 were corrected and the identities (2.6)-(2.7) were valid.","section":"Lemma 5"}],"minor_comments":[{"comment":"The title and abstract contain spacing artifacts (e.g., \"F AST\") that should be corrected.","section":"Title and Abstract"},{"comment":"In Definition 2, the range of ℓ is stated as ℓ=1,...,2^{n-m}, but for m=n this range is just ℓ=1, which is consistent, yet the later use of ℓ in Lemma 6 for ℓ up to 2^{n-m+1} deserves an explicit clarification.","section":"Definition 2"},{"comment":"The range t=1,...,2^{m-1} in Definition 3 excludes the case s=1 when s is written as 2t+1 (there t=0), so the recursion does not cover all s=1,...,2^m; the indexing should be stated carefully.","section":"Notation for t in Definition 3"}],"recommendation":"reject","confidential_remarks":"The paper's central claim fails because the recursion in Definition 3 is ill-posed and the key difference identity (2.6) is false; a concrete counterexample is provided in the major comments. This is a load-bearing error in the main theorem, not a mere proof gap. The manuscript would require a substantially different inversion formula to be salvageable. Given the explicit counterexample, I do not see a path for a moderate revision to establish the claimed result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nQuick take: the advertised result—exact inverse of the ADRT from a single quadrant in O(N log N)—is a natural and potentially useful target, but the proof in the current manuscript has a load-bearing gap. The recursion in Definition 3 is not well-posed, and the key identity in Lemma 6, Eq (2.6), is not established. I would not accept Theorem 1 on the strength of this write-up.\n\nWhat is genuinely new: the partial-data framing. Press's 2006 note already claims an exact fast inverse for the full ADRT, so the incremental novelty here is the one-quadrant recovery, which is a real and interesting question. The paper is also commendably short and self-contained; the idea of recovering differences of the half-image transforms from the full transform is attractive.\n\nThe soft spots are in the core argument. Definition 3 writes D_m(h,2t+1) and D_m(h,2t) using D_{m-1}(·, s) on the right, where s is the level-m parameter (2t or 2t+1). For most s>2^{m-1} this is undefined, so the recursion is ill-posed. If one repairs the indexing in the standard way (using t or t+1 as the second argument), the cancellation in the proof of Lemma 6 collapses. A concrete check for an 8×8 image A(i,j)=i at n=m=3, s=1 gives LHS of (2.6) = 4 and RHS = 3, so (2.6) is false under the natural repair. That is exactly the identity that the whole inversion depends on. Lemma 5 is also stated without proof, and the unproved subset bound (iii) is used to justify the prefix-sum sweep in (2.8). These are fixable in principle—maybe there is a different difference relation that works—but the current text does not contain it.\n\nThere is a separate citation concern: reference [5] (Press) is described as an iterative/multigrid approximation, but its title claims an exact and fast inverse. The paper needs to position itself against Press more carefully.\n\nBottom line: the raw idea deserves referee time, and I would send it out. But the manuscript in its present form does not establish the theorem, and the author should be asked to supply a correct recursion, a proof of Lemma 5, and a worked small example.\n\nBest","headline":"The paper's advertised exact partial-data inverse for the ADRT rests on an ill-posed recursion, and the key identity in Lemma 6 does not survive a natural repair; the idea is promising but the proof needs real work.","tokens_in":4504,"tokens_out":11610,"would_cite":false,"duration_ms":103805,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65R10","44A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact inversion of the approximate discrete Radon transform is possible from a single quadrant of data, in $O(N \\log N)$ operations.","keywords":["approximate discrete Radon transform","digital lines","exact inversion","partial data","O(N log N) algorithm","recursive inversion","tomography"],"falsifier":"Take a small random image, say $16\\times16$ pixels, compute its single-quadrant ADRT, and run the inversion recurrence of Lemma 6 level by level; if the recovered pixels differ from the original by more than floating-point rounding, the claimed exactness is false. A more targeted check is to verify the two difference identities (2.6) and (2.7) on all $(h,s)$ pairs at one level and to enumerate $D_m(h,s)$ to confirm the Lemma 5 bound.","tokens_in":3507,"feed_emoji":"🖼️","tokens_out":8318,"duration_ms":76153,"temperature":0.7,"pith_summary":"The paper proves that the approximate discrete Radon transform (ADRT), a pixelated recursive replacement for the continuous Radon transform, can be inverted exactly without iterative refinement and using only one quadrant of the transform data. The inversion runs in $O(N \\log N)$ operations for a square image with $N$ pixels, matching the asymptotic cost of the forward transform. This matters because previous approaches to recovering an image from its ADRT relied on numerical iteration or multigrid approximation, and exact recovery from partial data had not been established. The proof is constructive: it reverses the recursive definition of the digital lines level by level.","feed_headline":"One quadrant of pixel-line Radon data recovers the image exactly","feed_subtitle":"A single quadrant of the pixel-line Radon data is enough to invert exactly, at the same cost as the forward pass.","key_machinery":"The central object is the digital line $D_m(h,s)$, a subset of $\\mathbb{Z}^2$ defined recursively in Definition 3 by splitting into two translated and reflected copies of $D_{m-1}$; it is what makes the ADRT fast and what makes exact inversion possible. The load-bearing identity is Lemma 6, which states that given the transform $R^\\ell_{n,m}$ of the $\\ell$-th section, the transforms $R^{2\\ell-1}_{n,m-1}$ and $R^{2\\ell}_{n,m-1}$ of its two child sections can be computed in $O(M)$ operations, where $M$ is the size of the parent data. The proof expresses the difference $\\Delta^\\ell_{n,m-1}(h,s) = R^\\ell_{n,m-1}(h+1,s) - R^\\ell_{n,m-1}(h,s)$ as a difference of two parent transform values; because the two digital lines in the recursive union share a child line, subtracting cancels the shared contribution. A single prefix-sum sweep over $h$, using the bounded support from Lemma 5, then turns the differences back into the child transforms. This mechanism carries the entire inversion.","core_discovery":"On the paper's own terms, the central discovery is Theorem 1: a $2^n \\times 2^n$ image with $N = 2^{2n}$ pixels is determined exactly by its single-quadrant ADRT, and the recovery can be done in $O(N \\log N)$ operations. The transform's digital lines $D_m(h,s)$ are defined recursively by splitting a line at scale $m$ into two child lines at scale $m-1$, one in each half of the image. The paper shows that this recursion is reversible in the transform domain: the differences of the child-section transform values satisfy simple identities, equations (2.6) and (2.7), that depend only on values of the parent transform at nearby parameters $(h,s)$. Once those differences are known, prefix sums reconstruct the child transforms, and repeating from $m=n$ down to $m=0$ recovers the image exactly. Only one quadrant, corresponding to digital lines with slopes in the continuous angular range $[0,\\pi/4]$, is needed.","pith_inferences":["The paper does not state this, but if the single-quadrant ADRT is exactly invertible, the full four-quadrant ADRT is information-theoretically redundant by a factor of four; that redundancy could be exploited for consistency checks or error correction in measured data.","The difference identities (2.6)-(2.7) are purely combinatorial, so the same inversion scheme should transplant to other recursive digital-line definitions, including non-power-of-two grids or higher-dimensional pixelated lines, provided an analogue of Lemma 5 holds.","One can turn the proof into a built-in self-test: running the inversion on a random image and comparing with the original would catch any implementation error, because exactness is a discrete identity rather than a limiting statement.","The exactness result suggests that the gap between the continuous Radon transform and its discrete pixelated approximation is narrower than the word 'approximate' implies; quantifying how inversion error behaves under line refinement is a natural next step."],"forward_implications":["Exact inversion from one quadrant costs the same as the forward transform, so any pipeline that applies ADRT and then needs the image back can do so without iterative solvers or multigrid.","Only a single quadrant of ADRT data is required for exact recovery, so storage and acquisition can be reduced by a factor of four in applications that currently compute the full transform.","The level-by-level reversal is naturally parallel: at each step, each section can be inverted independently, which the paper notes is useful for domain decomposition and parallelization.","Because the inversion is exact, reconstruction error is governed only by how well digital lines approximate continuous straight lines, not by inversion error, supporting the use of ADRT as a surrogate for the continuous Radon transform.","The formula provides a direct alternative to earlier multigrid and conjugate-gradient approaches, replacing numerical approximation with a finite exact recurrence."],"supporting_citations":[{"why":"Defines the ADRT and the recursive digital lines whose exact inversion is the subject of the paper.","marker":"[1]"},{"why":"Provides the fast digital-line evaluation of the Hough/Radon transform that motivates the recursive line construction being inverted.","marker":"[2]"},{"why":"Earlier demonstration that ADRT inversion can be computed to numerical precision by multigrid; the exact formula here replaces that approximate route.","marker":"[5]"}],"fun_headline_variants":["Exact image from a single quadrant of discrete Radon data","One quadrant of Radon data suffices for exact inversion","Partial Radon data: exact image recovery in O(N log N)","Quarter Radon data, full exact image: no extra cost","Pixel-line Radon: one quadrant inverts image exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the recursive definition of the digital line $D_m(h,s)$ in Definition 3 is exactly as written, particularly the placement of the index $s$ in equation (2.2), and that the unproved bounding property in Lemma 5, $D_m(h,s) \\subseteq \\{h \\le i \\le h+s,\\ 1 \\le j \\le 2^m\\}$, holds; if either fails, the difference identities (2.6)-(2.7) no longer hold and the inversion formula collapses.","fun_headline_variants_meta":{"raw":{"variants":["Exact image from a single quadrant of discrete Radon data","One quadrant of Radon data suffices for exact inversion","Partial Radon data: exact image recovery in O(N log N)","Quarter Radon data, full exact image: no extra cost","Pixel-line Radon: one quadrant inverts image exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000816,"raw_usage":{"total_tokens":3502,"prompt_tokens":801,"completion_tokens":2701,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":417,"completion_tokens_details":{"reasoning_tokens":2616}},"tokens_in":417,"tokens_out":2701,"duration_ms":18827,"temperature":1.0,"reasoning_tokens":2616,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:28:53.785372+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small random image, say $16\\times16$ pixels, compute its single-quadrant ADRT, and run the inversion recurrence of Lemma 6 level by level; if the recovered pixels differ from the original by more than floating-point rounding, the claimed exactness is false. A more targeted check is to verify the two difference identities (2.6) and (2.7) on all $(h,s)$ pairs at one level and to enumerate $D_m(h,s)$ to confirm the Lemma 5 bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the ADRT and the recursive digital lines whose exact inversion is the subject of the paper."},{"cited_title":"G ¨otz and H","cited_arxiv_id":null,"evidence_quote":"Provides the fast digital-line evaluation of the Hough/Radon transform that motivates the recursive line construction being inverted."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier demonstration that ADRT inversion can be computed to numerical precision by multigrid; the exact formula here replaces that approximate route."}],"review_version":1}