The problem of reconstructing a binary function, f, de-0 or 1 with 0 °f (z) °1, and (b) using a linear programming fined on a finite subset of a lattice ,ޚ from an arbitrary collection of (LP) method to search for a feasible solution to Equation (1) its partial-sums is considered. The approach we present is based on subject to the constraint 0 °f °1. That is, solve for f the (a) relaxing the binary constraints f (z) Å 0 or 1 to interval constraints following LP problem: 0 °f (z) °1, z √ ,ޚ and (b) applying a minimum distance method (using Kullback-Leibler's information divergence index as our dis-
tance function) to find such an f -say, fO -for which the distance between the observed and the theoretical partial sums is as small as possible. (Turning this fO into a binary function can be done as a where x L denotes the indicator function of the set L. separate postprocessing step: for instance, through thresholding, or
Fishburn et al. [1] offered no advice or discussion on what to
through some additional Bayesian modeling.) To derive this minimumdistance solution, we develope a new EM algorithm. This algorithm do when the system of equations in ( ) is algebraically inconsisis different from the often-studied EM/maximum likelihood algorithm tent, and their method does not automatically extend to handle in emission tomography and other linear-inverse positively consuch cases. A natural extension would be to replace each equation strained problems because of the additional upper-bound constraint in (2), £(L) Å rrr, with a pair of inequalities, £(L) 0 e °rrr ( f °1) on the signal f. Properties of the algorithm, as well as similariand £(L) / e ¢ rrr, for L √ L, and vary e(ú0). This, however, ties with and differences from some other methods, such as the linearhas the problem that a single bad equation might turn an inconsisprogramming approach or the algebraic reconstruction technique, tent but almost uniquely reconstructible setup to a totally uninforare discussed. The methodology is demonstrated on three recently mative set of inequalities with many feasible solutions. (Trying studied phantoms, and the simulation results are very promising, sugdifferent e's for different L's would be computationally impractigesting that the method could also work well under field conditions cal without a smart way-perhaps using a Bayes prior on the which may include a small or moderate level of measurement noise in the observed partial sums. The methodology has important applicaimages-of choosing the e's.) An alternative approach that might tions in high-resolution electron microscopy for the reconstruction of do better in the inconsistent case, yet offer similar properties to the atomic structure of crystals from their projections. ᭧ 1998