Optimal Experimental Design for Constrained Inverse Problems

Lars Ruthotto, Julianne Chung, Matthias Chung

Abstract

In this paper, we address the challenging problem of optimal experimental design (OED) of constrained inverse problems. We consider two OED formulations that allow reducing the experimental costs by minimizing the number of measurements. The first formulation assumes a fine discretization of the design parameter space and uses sparsity promoting regularization to obtain an efficient design. The second formulation parameterizes the design and seeks optimal placement for these measurements by solving a small-dimensional optimization problem. We consider both problems in a Bayes risk as well as an empirical Bayes risk minimization framework. For the unconstrained inverse state problem, we exploit the closed form solution for the inner problem to efficiently compute derivatives for the outer OED problem. The empirical formulation does not require an explicit solution of the inverse problem and therefore allows to integrate constraints efficiently. A key contribution is an efficient optimization method for solving the resulting, typically high-dimensional, bilevel optimization problem using derivative-based methods. To overcome the lack of non-differentiability in active set methods for inequality constraints problems, we use a relaxed interior point method. To address the growing computational complexity of empirical Bayes OED, we parallelize the computation over the training models. Numerical examples and illustrations from tomographic reconstruction, for various data sets and under different constraints, demonstrate the impact of constraints on the optimal design and highlight the importance of OED for constrained problems.

Introduction

In many fields—from medical imaging to geophysics—we face "inverse problems": trying to reconstruct an internal structure (like a brain or a mineral deposit) from external measurements (like X-rays or seismic waves). These problems are often "ill-posed," meaning small amounts of noise in the data can lead to massive errors in the reconstruction. Optimal Experimental Design (OED) is the art of choosing the best possible measurements to minimize these errors.

Most existing OED methods assume the reconstruction is unconstrained. In reality, we often have "prior knowledge" or "state constraints"—for example, we know that physical density cannot be negative. This paper introduces a unified framework for OED specifically tailored for constrained inverse problems. By incorporating physical constraints directly into the design process, the authors demonstrate that we can achieve higher-quality reconstructions with significantly fewer measurements, drastically reducing experimental costs and data acquisition time.

Methods and Formulations

The authors propose a bilevel optimization framework consisting of two nested loops. The Inner Problem (Reconstruction) finds the best image that satisfies physical constraints (e.g., non-negativity or box constraints) given a set of measurements. The Outer Problem (Design) finds the measurement parameters that minimize the expected error of the inner problem.

Illustration of a tomographic reconstruction setup where the design parameter $\theta$ represents the angle of the X-ray source and detector.

The paper explores two specific formulations:

  • Problem A (Sparsity-Promoting): Starts with a large number of possible measurement angles and uses $\ell_1$-regularization to select only the most essential ones.
  • Problem B (Parameter Optimization): Optimizes the specific locations or angles for a fixed, small number of measurements.

To make this computationally feasible, the authors use implicit differentiation of the Karush-Kuhn-Tucker (KKT) conditions and interior point methods to handle inequality constraints smoothly. The framework was evaluated using four simulated tomographic datasets: binary rectangles, pentagons, random smooth shapes, and the standard Modified Shepp-Logan Phantom.

Key Insights and Results

A primary finding is that constraints change the optimal design. A design that is optimal for an unconstrained problem is often sub-optimal once physical constraints are enforced. For example, knowing the upper and lower bounds of a target (box constraints) provides a massive boost, allowing for a much larger reduction in reconstruction error compared to unconstrained models.

In "Problem B" tests, the Mean Squared Error (MSE) for box-constrained reconstructions was significantly lower than for unconstrained ones across all datasets. In "Problem A," the framework successfully reduced the number of required projections while maintaining high accuracy. For the rectangle dataset, the algorithm correctly identified that only two measurements (0° and 90°) are needed for an exact reconstruction if binary constraints are known—a result that matches human intuition but is mathematically derived here.

Conclusion

This research highlights the importance of incorporating state constraints into experimental design. By doing so, it is possible to achieve superior reconstruction quality with fewer data points. While the current work focuses on linear inverse problems, future extensions could address non-linear physics and discrete design parameters. The use of parallelization makes this high-dimensional bilevel optimization approach practical for real-world training sets.

Reference: Ruthotto, L., Chung, J., & Chung, M. (2017). Optimal Experimental Design for Constrained Inverse Problems. arXiv:1708.04740v1 [math.NA].

Summary updated

Abstract

In this paper, we address the challenging problem of optimal experimental design (OED) of constrained inverse problems. We consider two OED formulations that allow reducing the experimental costs by minimizing the number of measurements. The first formulation assumes a fine discretization of the design parameter space and uses sparsity promoting regularization to obtain an efficient design. The second formulation parameterizes the design and seeks optimal placement for these measurements by solving a small-dimensional optimization problem. We consider both problems in a Bayes risk as well as an empirical Bayes risk minimization framework. For the unconstrained inverse state problem, we exploit the closed form solution for the inner problem to efficiently compute derivatives for the outer OED problem. The empirical formulation does not require an explicit solution of the inverse problem and therefore allows to integrate constraints efficiently. A key contribution is an efficient optimization method for solving the resulting, typically high-dimensional, bilevel optimization problem using derivative-based methods. To overcome the lack of non-differentiability in active set methods for inequality constraints problems, we use a relaxed interior point method. To address the growing computational complexity of empirical Bayes OED, we parallelize the computation over the training models. Numerical examples and illustrations from tomographic reconstruction, for various data sets and under different constraints, demonstrate the impact of constraints on the optimal design and highlight the importance of OED for constrained problems.
BibTeX
@misc{ruthotto2017optimal,
  author = {Lars Ruthotto and Julianne Chung and Matthias Chung},
  title = {{Optimal Experimental Design for Constrained Inverse Problems}},
  year = {2017},
  eprint = {1708.04740},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1708.04740},
}
Figure