## DIMACS TR: 97-67

## Linear Programming in Tomography, Probability, and Finance

### Author: Larry Shepp

**
ABSTRACT
**

At the first conference (at DIMACS), it became
clear that linear, or convex, programming is going to play a key role in
the algorithmics of "discrete tomography", where one attempts to reconstruct
a finite subset, $S$, of the integer lattice, $Z^2$, or $Z^3$, from its line
sums in a few directions obtained via transmission electron microscopy. The
usual convolution-back-projection algorithms for continuous tomography are
useless for this new application to crystal microscopy because only very few
directions are available for which the line sums are measured.
Since the problem
of determining a subset $S$ with the given line sums is an integer programming
problem the standard convexification of the problem reduces it to linear
programming (Peter Fishburn, Peter Schwander, Robert Vanderbei, The Discrete
Radon Transform and its Approximate Inversion via Linear programming, Discrete
Applied Math., 1997, to appear). This showed that $S$ may be "effectively"
reconstructed in the sense that the method of finding a feasible interior
point in the convex hull of what is called "fuzzy sets", ie a function,
$0 \le f(z) \le 1$ for all $z \in Z^2$, or $Z^3$, "typically" produces a
reasonablly satisfactory reconstruction on simulated phantoms. Thus the
situation is more or less analogous to conventional medical CT scanning, where
even though one cannot hope to uniquely reconstruct a function, $f(x,y)$
from its line integrals in a finite number of fixed directions (even if the
line integrals are noiseless) the usual algoorithms are seen to work well,
as demonstrated via simulations.

In the above paper written over a year ago, available by request at
fish@research.att.com, the method is made clear. Here however I have a
different goal: several disparate problems in applied mathematics can be
solved via non-trivial use of infinite linear programming and I thought
that I would share these with the audience in order to illustrate the scope
and the power of linear programming and to bring the ideas to wider view,
after first trying to set into perspective the application of linear
programming to discrete tomography via a review.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-67.ps.gz

DIMACS Home Page