THE DISCRETE RADON-TRANSFORM AND ITS APPROXIMATE INVERSION VIA LINEAR-PROGRAMMING

Let S be a finite subset of a lattice and let upsilon(s)(L), the numbe r of points of S boolean AND L for each line L, denote the discrete Ra don transform of S. The problem is to reconstruct S from a knowledge ( possibly noisy) of the restriction of upsilon(s) to a subset L of the set of all lines in any of a few given directions through the lattice. Reconstructing a density from its line integrals is a well-understood problem, but discreteness causes many difficulties and precludes use of continuous Radon inversion algorithms. Indeed it has been shown tha t when the directions are main directions of the lattice, the case for most applications, the problem is finite but is NP-hard, so that any reconstruction algorithm will surely have to consist of exponentially many steps in the size of S.