Abstract
Discrete tomography aims to reconstruct 3D objects from a limited number of X-ray projections. While Total Variation (TV) minimization is a powerful framework for this undersampled recovery, its application to high-resolution 3D volumes is often hindered by the computational limits of standard solvers. This paper introduces a scalable optimization strategy that applies an entropic perturbation to the TV-minimization objective. By transforming the constrained problem into a smooth, unconstrained dual problem, the authors enable the use of the memory-efficient L-BFGS algorithm, significantly outperforming commercial solvers in both scalability and noise robustness.
Introduction
In industrial and biological imaging, researchers often face the challenge of reconstructing a 3D object from a highly restricted set of projections. This "undersampled" data environment makes the reconstruction problem ill-posed, as infinitely many images could theoretically fit the observed data. To identify the most plausible reconstruction, Total Variation (TV) minimization is employed. This technique assumes the target object is "blocky" or cosparse—composed of a few homogeneous materials with sharp boundaries.
However, as imaging moves from 2D slices to high-resolution 3D volumes, the resulting optimization problems become massive. Standard interior-point solvers, such as MOSEK, frequently encounter memory bottlenecks or "stall" during convergence when faced with millions of variables. Furthermore, these solvers can be brittle when the input data is corrupted by noise, a common occurrence in real-world laboratory settings.
Methodology: Entropic Perturbation
The authors propose a "Perturbed Linear Programming" approach to overcome these computational hurdles. The method follows a four-step transformation process:
- Linear Programming Reformulation: The original TV-minimization problem is first cast as a standard Linear Program (LP).
- Entropic Perturbation: Rather than solving the rigid LP, the authors introduce a small nonlinear term—an entropy function $\epsilon \langle x, \log x - \mathbf{1} \rangle$—into the objective function.
- Fenchel Duality: By applying Fenchel Duality to this perturbed objective, the authors derive a dual problem that is both unconstrained and twice differentiable.
- L-BFGS Optimization: The resulting smooth, unconstrained landscape allows for the use of the Limited-Memory BFGS (L-BFGS) algorithm. L-BFGS is specifically designed for high-dimensional optimization, maintaining a very small memory footprint even with millions of variables.
This approach effectively "softens" the hard constraints of the original TV problem, creating a numerical landscape that is much easier for solvers to navigate quickly.
Experimental Setup
The effectiveness of the entropic approach was evaluated using several synthetic benchmarks designed to simulate difficult tomographic conditions:
- 2D Ellipsoids: Randomly generated images used to validate "phase transition" curves, which predict the minimum number of measurements required for perfect recovery.
- 3D Shepp-Logan Phantom: A standard medical imaging benchmark scaled to a $51 \times 51 \times 51$ volume to test 3D reconstruction capabilities.
- Noise Robustness: To simulate real-world conditions, projections were corrupted with Poisson noise at a Signal-to-Noise Ratio (SNR) of 50dB.
Key Insights and Results
Scalability and Efficiency
The proposed algorithm demonstrated superior scalability compared to commercial alternatives. In 3D reconstruction tasks where MOSEK reached its memory capacity or failed to converge, the entropic approach successfully produced high-quality results. Timing benchmarks indicated that while MOSEK’s computation time grew exponentially with image dimension, the entropic approach scaled gracefully, maintaining efficiency at higher resolutions.
Phase Transitions and Recovery
The authors validated theoretical phase transition curves, confirming the relationship between the number of measurements ($m$) and the object's complexity (cosparsity $\ell$). Notably, the choice of an entropic perturbation proved superior to standard quadratic (Tikhonov) regularization for these integer-valued reconstruction problems.
Robustness to Noise
In noisy scenarios, standard solvers often reported the problem as "infeasible" due to the strictness of the constraints. The entropic approach remained stable, producing reconstructions with an error margin ($||u - u^*||_\infty < 0.5$) low enough to allow for perfect recovery after simple rounding.
Conclusion and Future Work
By slightly modifying the TV-minimization objective with an entropic term, the authors have unlocked the ability to use fast, unconstrained optimization tools for 3D tomography. While the choice of the perturbation parameter $\epsilon$ currently remains fixed, future research may explore adaptive methods for selecting this value to further optimize performance. Additionally, the algorithm's structure is highly suitable for parallelization, suggesting even greater potential for processing massive industrial datasets in real-time.
Summary updated