Signal recovery in the polychromatic computed tomography model: Injectivity and complexity
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.