pith. sign in

arxiv: 2204.12349 · v4 · submitted 2022-04-26 · 🧮 math.CO

Error Correction for Discrete Tomography

M. Ceko , L. Hajdu , R. Tijdeman This is my paper

Pith reviewed 2026-05-24 12:13 UTC · model grok-4.3

classification 🧮 math.CO
keywords discrete tomographyerror correctionline sumsKatz conditionuniquenessprojectionsreconstructionfinite subsets
0
0 comments X

The pith

Discrete tomography can correct fewer than d/2 errors in line sums from d directions, and this bound is optimal.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper extends prior reconstruction algorithms for functions on finite subsets of the integer lattice from their line sums in d directions. It shows that these methods can be adapted so that the original function is recovered even when fewer than d/2 of the given line sums are wrong. The result applies both when the function is uniquely determined by the correct sums and in the general case. The authors also prove that the threshold cannot be improved, because with d/2 errors there exist configurations that prevent unique recovery. This matters for applications such as data storage or transmission where line sums may contain occasional inaccuracies.

Core claim

If a function f is defined on a finite set A subset of Z squared and its line sums are known in d directions, then when fewer than d/2 of those sums are erroneous the correct f can still be recovered by extending the existing reconstruction procedures; moreover, the bound d/2 is sharp because there are cases with exactly d/2 errors for which no unique correction is possible.

What carries the argument

An error-correcting extension of the Pagani-Tijdeman reconstruction procedure that identifies and repairs incorrect line sums while preserving the uniqueness properties guaranteed by Katz's condition.

If this is right

  • Unique recovery of f remains possible whenever the number of incorrect line sums is strictly less than d/2.
  • The same algorithms that reconstruct f from exact sums or from sums of a non-unique f can be modified to handle the error case.
  • The optimality proof shows that d/2 is the largest integer threshold for which error correction is always guaranteed.
  • The approach applies directly to the settings of data storage and transmission mentioned in the abstract.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In practice one would therefore choose at least 2k+1 directions to guarantee correction of up to k errors.
  • The same error-correction logic might be tested on reconstruction problems that use other discrete structures besides line sums in the plane.

Load-bearing premise

The existing reconstruction techniques can be extended to detect and correct errors in the line sums without losing the uniqueness properties from Katz's condition.

What would settle it

An explicit example with exactly d/2 erroneous line sums in which two distinct functions produce identical (erroneous) sums, so that unique correction fails.

read the original abstract

Discrete tomography focuses on the reconstruction of functions $f: A \to \mathbb{R}$ from their line sums in a finite number $d$ of directions, where $A$ is a finite subset of $\mathbb{Z}^2$. Consequently, the techniques of discrete tomography often find application in areas where only a small number of projections are available. In 1978 M.B. Katz gave a necessary and sufficient condition for the uniqueness of the solution. Since then, several reconstruction methods have been introduced. Recently Pagani and Tijdeman developed a fast method to reconstruct $f$ if it is uniquely determined. Subsequently Ceko, Pagani and Tijdeman extended the method to the reconstruction of a function with the same line sums of $f$ in the general case. Up to here we assumed that the line sums are exact. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than $d/2$ errors can be corrected and that this bound is the best possible.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript extends discrete tomography to the setting of erroneous line sums. Building on Katz's 1978 uniqueness criterion for d directions and the reconstruction algorithms of Pagani-Tijdeman (unique case) and Ceko-Pagani-Tijdeman (general case), it claims that any pattern of fewer than d/2 incorrect line sums can be corrected and that the bound is tight.

Significance. If the central claim is established, the work supplies a concrete error-correction guarantee for an application domain (data storage/transmission) where line sums are the only available measurements. The explicit optimality statement and the direct reuse of the existing reconstruction routines are strengths.

major comments (1)
  1. [Main theorem (§3)] Main theorem (likely §3): the correction procedure selects a large error-free subset of directions and invokes the Pagani-Tijdeman or Ceko-Pagani-Tijdeman routine on it. The argument therefore requires that, whenever the full set of d directions satisfies Katz's condition, at least one subset of size ⌈d/2⌉+1 that is also error-free satisfies the same condition. No explicit verification or counter-example analysis of this inheritance property is supplied; without it the location of the errors need not be unique.
minor comments (2)
  1. [Abstract] The abstract states the result for 'less than d/2 errors' but does not specify whether the bound is ⌊(d-1)/2⌋ or ⌈d/2⌉-1; a single clarifying sentence would remove ambiguity.
  2. [§2] Notation for the finite grid A and the direction set is introduced only informally; a short preliminary subsection collecting the standing assumptions would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and for highlighting a potential gap in the argument for the main theorem. We agree that the inheritance of Katz's condition to sufficiently large error-free subsets requires explicit verification, which is currently absent from the manuscript. We will add this verification in the revision.

read point-by-point responses

  1. Referee: [Main theorem (§3)] Main theorem (likely §3): the correction procedure selects a large error-free subset of directions and invokes the Pagani-Tijdeman or Ceko-Pagani-Tijdeman routine on it. The argument therefore requires that, whenever the full set of d directions satisfies Katz's condition, at least one subset of size ⌈d/2⌉+1 that is also error-free satisfies the same condition. No explicit verification or counter-example analysis of this inheritance property is supplied; without it the location of the errors need not be unique.

    Authors: We acknowledge the validity of this observation. The current manuscript does not contain an explicit argument or lemma showing that Katz's uniqueness condition is inherited by at least one error-free subset of size ⌈d/2⌉+1 whenever it holds for the full set of d directions. This step is necessary to guarantee that the error locations are uniquely determined before invoking the existing reconstruction routines. We will insert a new short subsection (or lemma) in §3 that proves the required inheritance property, using the combinatorial characterization of Katz's condition. The proof will also include a brief check that no counter-examples arise for the relevant range of d. This addition will make the argument complete. revision: yes

Circularity Check

0 steps flagged

No circularity: extension of prior independent reconstruction methods with external uniqueness condition

full rationale

The paper's central claim (correcting <d/2 errors, with the bound best possible) extends the Pagani-Tijdeman reconstruction algorithm and Ceko-Pagani-Tijdeman generalization, both cited as prior work, to the error case while invoking Katz's 1978 uniqueness condition. These references are external to the present derivation; the new error-correction procedure and the demonstration that the bound is tight (via explicit counter-example construction) do not reduce by definition or by self-citation chain to the input data or to a fitted parameter. No equation or step equates the claimed result to its own assumptions by construction. Self-citation to overlapping-author prior work exists but is not load-bearing for the uniqueness or bound arguments, which rest on Katz (1978) and explicit constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the prior literature for uniqueness and reconstruction algorithms; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • domain assumption Katz's necessary and sufficient condition for uniqueness of the solution
    Cited in the abstract as the foundation for reconstruction methods that are then extended to the error case.

pith-pipeline@v0.9.0 · 5719 in / 1135 out tokens · 19685 ms · 2026-05-24T12:13:24.002849+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    On the reconstruction of static an d dynamic discrete structures

    Alpers A, Gritzmann P . On the reconstruction of static an d dynamic discrete structures. In: The Radon Transform. De Gruyter; 2019. p. 297-342

    work page 2019

  2. [3]

    Boundary ghosts for discrete tomography

    Ceko M, Petersen T, Svalbe I, Tijdeman R. Boundary ghosts for discrete tomography. Journal of Mathe- matical Imaging and Vision. 2021;63(3):428-40. doi:10.10 07/s10851-020-01010-2

    work page 2021

  3. [4]

    Geometrical characteriza tion of the uniqueness regions under special sets of three directions in discrete tomography

    Dulio P , Frosini A, Pagani SM. Geometrical characteriza tion of the uniqueness regions under special sets of three directions in discrete tomography. In: Discre te Geometry for Computer Imagery. vol. 9647. Springer; 2016. p. 105-16. doi:10.1007/978-3-319-32360- 2 8

    work page doi:10.1007/978-3-319-32360- 2016

  4. [5]

    Discrete tomography: determina tion of finite sets by X-rays

    Gardner R, Gritzmann P . Discrete tomography: determina tion of finite sets by X-rays. Transactions of the American Mathematical Society. 1997;349(6):2271-95

    work page 1997

  5. [6]

    The Mojette transform: the first ten years

    Gu´ edon J, Normand N. The Mojette transform: the first ten years. In: Discrete Geometry for Computer Imagery. Springer; 2005. p. 79-91. doi:10.1007/978-3-540 -31965-8 8

    work page doi:10.1007/978-3-540 2005

  6. [7]

    Algebraic aspects of discrete tomog raphy

    Hajdu L, Tijdeman R. Algebraic aspects of discrete tomog raphy. J reine angew Math. 2001;534:119-28. doi:10.1515/crll.2001.037

    work page doi:10.1515/crll.2001.037 2001

  7. [8]

    Fundamentals of computerized tomography: Im age reconstruction from projections

    Herman GT. Fundamentals of computerized tomography: Im age reconstruction from projections. Springer Science & Business Media; 2009. doi:10.1007/978-1-84628- 723-7

    work page doi:10.1007/978-1-84628- 2009

  8. [9]

    Advances in discrete tomography and it s applications

    Herman GT, Kuba A. Advances in discrete tomography and it s applications. Springer Science & Business Media; 2008. doi:10.1007/978-0-8176-4543-4

    work page doi:10.1007/978-0-8176-4543-4 2008

  9. [10]

    An algebraic framework for discr ete tomography: Revealing the structure of dependencies

    Stolk A, Batenburg KJ. An algebraic framework for discr ete tomography: Revealing the structure of dependencies. SIAM Journal on Discrete Mathematics. 2010; 24(3):1056-79

    work page 2010

  10. [11]

    Sets uniqu ely determined by projections on axes II Discrete case

    Fishburn PC, Lagarias JC, Reeds JA, Shepp LA. Sets uniqu ely determined by projections on axes II Discrete case. Discrete Mathematics. 1991;91(2):149-59. doi:10.1016/0012-365X(91)90106-C

    work page doi:10.1016/0012-365x(91)90106-c 1991

  11. [13]

    Forward error correction for DNA data storage

    Blawat M, Gaedke K, Huetter I, Chen XM, Turczyk B, Invers o S, et al. Forward error correction for DNA data storage. Procedia Computer Science. 2016;80:1011-22 . doi:10.1016/j.procs.2016.05.398

    work page doi:10.1016/j.procs.2016.05.398 2016

  12. [14]

    Multimedia forward er ror correcting codes for wire- less LAN

    Parrein B, Normand N, Gu´ edon JP . Multimedia forward er ror correcting codes for wire- less LAN. Annals of Telecommunications-annales des t´ el´ e communications. 2003;58(3-4):448-63. doi:10.1007/BF03001024

    work page doi:10.1007/bf03001024 2003

  13. [15]

    A robust image watermarking t echnique based on quantization noise visibility thresholds

    Autrusseau F, Le Callet P . A robust image watermarking t echnique based on quantization noise visibility thresholds. Signal Processing. 2007;87(6):1363-83. doi: 10.1016/j.sigpro.2006.11.009

    work page doi:10.1016/j.sigpro.2006.11.009 2007

  14. [16]

    Perceptual DFT waterma rking with improved detection and robustness to geometrical distortions

    Urvoy M, Goudia D, Autrusseau F. Perceptual DFT waterma rking with improved detection and robustness to geometrical distortions. IEEE Transactions on Informat ion Forensics and Security. 2014;9(7):1108-19. doi:10.1109/TIFS.2014.2322497

    work page doi:10.1109/tifs.2014.2322497 2014

  15. [17]

    Lossless image compression v ia predictive coding of discrete Radon projec- tions

    Kingston A, Autrusseau F. Lossless image compression v ia predictive coding of discrete Radon projec- tions. Signal Processing: Image Communication. 2008;23(4 ):313-24. doi:10.1016/j.image.2008.03.001. M. Ceko and all. / Error Correction for Discrete Tomography 111

    work page doi:10.1016/j.image.2008.03.001 2008

  16. [18]

    IEEE Transactions on Image Processing 26(5), 2274–2285 (2017)

    Chandra SS, Svalbe ID, Gu´ edon J, Kingston AM, Normand N . Recovering missing slices of the dis- crete Fourier transform using ghosts. IEEE Transactions on Image Processing. 2012;21(10):4431-41. doi:10.1109/TIP .2012.2206033

    work page doi:10.1109/tip 2012

  17. [19]

    Erasure codi ng with the finite Radon trans- form

    Normand N, Svalbe I, Parrein B, Kingston A. Erasure codi ng with the finite Radon trans- form. In: 2010 IEEE Wireless Communication and Networking C onference. IEEE; 2010. p. 1-6. doi:10.1109/WCNC.2010.5506385

    work page doi:10.1109/wcnc.2010.5506385 2010

  18. [20]

    Spatial im plementation for erasure coding by Finite Radon Transform

    Pertin D, d’Ippolito G, Normand N, Parrein B. Spatial im plementation for erasure coding by Finite Radon Transform. In: International Symposium on signal, Image, V ideo and Communication 2012; 2012. p. 1-4

    work page 2012

  19. [21]

    Questions of uniqueness and resolution in reco nstruction from projections

    Katz MB. Questions of uniqueness and resolution in reco nstruction from projections. vol. 26. Springer Science & Business Media; 2013. doi:10.1007/978-3-642-45 507-0

    work page doi:10.1007/978-3-642-45 2013

  20. [22]

    Gr¨ obner bases and primal algorithms in d iscrete tomography

    Wiegelmann M. Gr¨ obner bases and primal algorithms in d iscrete tomography. TU M¨ unchen; 1999

    work page 1999

  21. [23]

    On the computat ional complexity of reconstructing lattice sets from their X-rays

    Gardner RJ, Gritzmann P , Prangenberg D. On the computat ional complexity of reconstructing lattice sets from their X-rays. Discrete Mathematics. 1999;202(1-3):4 5-71. doi:10.1016/S0012-365X(98)00347-1

    work page doi:10.1016/s0012-365x(98)00347-1 1999

  22. [24]

    On the computat ional complexity of determining poly- atomic structures by X-rays

    Gardner RJ, Gritzmann P , Prangenberg D. On the computat ional complexity of determining poly- atomic structures by X-rays. Theoretical computer science . 2000;233(1-2):91-106. doi:10.1016/S0304- 3975(97)00298-3

    work page doi:10.1016/s0304- 2000

  23. [25]

    A rounding theorem for unique binary tomographic reconstruction

    Dulio P , Pagani SM. A rounding theorem for unique binary tomographic reconstruction. Discrete Applied Mathematics. 2019;268:54-69. doi:10.1016/j.dam.2019.0 5.005

    work page doi:10.1016/j.dam.2019.0 2019

  24. [26]

    N., Abdrasheva, G

    Dulio P , Frosini A, Pagani SM. Uniqueness regions under sets of generic projections in discrete tomog- raphy. In: Discrete Geometry for Computer Imagery. Springe r; 2014. p. 285-96. doi:10.1007/978-3-319- 09955-2 24

    work page doi:10.1007/978-3-319- 2014

  25. [27]

    A geometrical characteri zation of regions of uniqueness and applications to discrete tomography

    Dulio P , Frosini A, Pagani SM. A geometrical characteri zation of regions of uniqueness and applications to discrete tomography. Inverse problems. 2015;31(125011): 285-96. doi:10.1088/0266-5611/31/12/125011

    work page doi:10.1088/0266-5611/31/12/125011 2015

  26. [28]

    Regions of uniqueness quic kly reconstructed by three directions in discrete tomography

    Dulio P , Pagani S, Frosini A. Regions of uniqueness quic kly reconstructed by three directions in discrete tomography. Fundamenta Informaticae. 2017;155(4):407-2 3. doi:10.3233/FI-2017-1592

    work page doi:10.3233/fi-2017-1592 2017

  27. [29]

    Algorithms for linear time recon struction by discrete tomography

    Pagani SM, Tijdeman R. Algorithms for linear time recon struction by discrete tomography. Discrete Applied Mathematics. 2019;271:152-70. doi:10.1016/j.da m.2019.07.012

    work page doi:10.1016/j.da 2019

  28. [30]

    Algorithms for linear tim e reconstruction by discrete tomography II

    Ceko M, Pagani SM, Tijdeman R. Algorithms for linear tim e reconstruction by discrete tomography II. Discrete Applied Mathematics. 2021;298:7-20. doi:10.101 6/j.dam.2021.03.008

    work page 2021

  29. [31]

    Discrete tomography: Foundations, a lgorithms, and applications

    Herman GT, Kuba A. Discrete tomography: Foundations, a lgorithms, and applications. Springer Science & Business Media; 2012. doi:10.1007/978-1-4612-1568-4

    work page doi:10.1007/978-1-4612-1568-4 2012

  30. [32]

    Matrix computations

    Golub GH, V an Loan CF. Matrix computations. JHU press; 2 013. ISBN-10:1421407949, 13:978- 1421407944

    work page

  31. [33]

    Bounds for approximate discrete to mography solutions

    Hajdu L, Tijdeman R. Bounds for approximate discrete to mography solutions. SIAM Journal on Discrete Mathematics. 2013;27(2):1055-66. doi:10.1137/12088326 8

    work page doi:10.1137/12088326 2013

  32. [34]

    On stability, error correction, and noise compensation in discrete tomography

    Alpers A, Gritzmann P . On stability, error correction, and noise compensation in discrete tomography. SIAM Journal on Discrete Mathematics. 2006;20(1):227-39. doi:10.1137/040617443

    work page doi:10.1137/040617443 2006

  33. [35]

    For most large underdetermined systems of li near equations the minimal ℓ1-norm solution is also the sparsest solution

    Donoho DL. For most large underdetermined systems of li near equations the minimal ℓ1-norm solution is also the sparsest solution. Communications on Pure and Ap plied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences. 2006;59(6):7 97-829. doi:10.1002/cpa.20132. 112 M. Ceko and all. / Error Correction for Discrete Tomography

    work page doi:10.1002/cpa.20132 2006

  34. [36]

    Dense Error Correction Via ℓ1-Minimization

    Wright J, Ma Y . Dense Error Correction Via ℓ1-Minimization. IEEE Transactions on Information Theory. 2010;56(7):3540-60. doi:10.1109/TIT.2010.2048473

    work page doi:10.1109/tit.2010.2048473 2010

  35. [37]

    Robust uncertainty princi ples: Exact signal reconstruction from highly incomplete frequency information

    Cand` es EJ, Romberg J, Tao T. Robust uncertainty princi ples: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on in formation theory. 2006;52(2):489-509. doi:10.1109/TIT.2005.862083

    work page doi:10.1109/tit.2005.862083 2006

  36. [38]

    Consistency conditions for discre te tomography

    Hajdu L, Tijdeman R. Consistency conditions for discre te tomography. Fundamenta Informaticae. 2017;155(4):425-47. doi10.3233/FI-2017-1593

    work page 2017

  37. [39]

    Dependencies between line sums

    van Dalen B. Dependencies between line sums. Leiden Uni versity; 2007

    work page 2007

  38. [40]

    The algorithm SELECT–for finding the i-th smallest of n elements (Algorithm 489)

    Floyd R, Rivest R. The algorithm SELECT–for finding the i-th smallest of n elements (Algorithm 489). Communications of the ACM, L. 1975;18:173

    work page 1975

  39. [41]

    A course in computational algebraic number the ory

    Cohen H. A course in computational algebraic number the ory. vol. 138. Springer Science & Business Media; 2013

    work page 2013

  40. [42]

    Algorithms for linear tim e reconstruction by discrete tomography in three dimensions

    Ceko M, Pagani SM, Tijdeman R. Algorithms for linear tim e reconstruction by discrete tomography in three dimensions. arXiv preprint arXiv:201005868. 2020

    work page 2020