Summary
Polychromatic computed tomography (CT) tries to see inside objects made of multiple materials by measuring how different signals pass through them. The authors study how many measurements you need to uniquely figure out these signals and show it must be at least the total number of unknown values. They also find that while it’s possible to design measurements that let you recover the signals perfectly, deciding if any set of signals matches the measurements in general is computationally very hard (NP-hard) when dealing with multiple materials. This is quite different from single-material CT, where there are efficient methods for recovery.
What this means in practice
- •For medical imaging software developers: Know that reconstructing images involving multiple materials in CT can be inherently computationally hard, guiding the design of reconstruction algorithms.
- •For industrial non-destructive testing engineers: Understand the theoretical limits on the number of measurements needed for unique recovery in multimaterial CT, aiding scan design decisions.
A theory result. No direct application yet.
Abstract
We consider a nonlinear model motivated by polychromatic computed tomography (CT). Here, $W$ distinct $d$-dimensional signals $x^*_1, \ldots, x^*_W \in \mathbb{R}^d$ must be recovered from $n$ measurements $(a_i, y_i)_{i = 1}^n$ that obey the nonlinear model $\mathbb{E}[y_i|a_i] = h(\langle a_i, x^*_1 \rangle, \ldots, \langle a_i, x^*_W \rangle)$, where $h: \mathbb{R}^W \to \mathbb{R}$ is a known nonlinearity that models a certain type of exponential attenuation law. Even when there is no noise in the measurements, the sample size $n$ (for any measurement ensemble $\{a_i\}_{i = 1}^n$) must exceed the number of unknowns $Wd$ to guarantee that the underlying signals are identifiable. We construct a measurement ensemble that ensures perfect signal recovery almost surely provided $n \geq Wd + W - 1$, thereby isolating the injectivity threshold up to an additive factor $W - 1$. We also study computational complexity of signal recovery in this model with a general measurement ensemble $\{a_i\}$. We show that if $W \geq 2$, then there is a measurement ensemble for which deciding whether there exist signals consistent with the measurements is NP-hard. In particular, this implies that polychromatic, multimaterial CT reconstruction is NP-hard in general. This finding stands in sharp contrast to the single-material setting, for which a polynomial-time algorithm can provably perform signal recovery for any measurement ensemble.