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, β¦, x*W β βd must be recovered from n measurements (ai, yi)i = 1n that obey the nonlinear model πΌ[yi|ai] = h(β¨ ai, x*1 β©, β¦, β¨ ai, x*W β©), where h: βW β β 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 {ai}i = 1n) 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 β₯ 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 {ai}. We show that if W β₯ 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.
Related
- On the Injectivity of Elementary Symmetric Partitions and the Multiset Recovery Problem
- Enhanced attenuation modelling for multispectral computed tomography
- Torus computed tomography for experimental data
- Quantized Low-Rank Quantum State Tomography: Hyperbolic Quantization and Riemannian Least-Squares Recovery
- A Factorization Method for Support Recovery in Magnetic Induction Tomography
BibTeX
@misc{chen2026signal,
title = {{Signal recovery in the polychromatic computed tomography model: Injectivity and complexity}},
author = {Xuanzhou Chen and Ashwin Pananjady},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23040},
eprint = {2609.23040},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23040},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Signal recovery in the polychromatic computed tomography model: Injectivity and complexity
AU - Xuanzhou Chen
AU - Ashwin Pananjady
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.23040
UR - https://arxiv.org/abs/2609.23040
AB - We consider a nonlinear model motivated by polychromatic computed tomography (CT). Here, W distinct d-dimensional signals x^*_1, β¦, x^*_W β β^d must be recovered from n measurements (a_i, y_i)_i = 1^n that obey the nonlinear model πΌ[y_i|a_i] = h(β¨ a_i, x^*_1 β©, β¦, β¨ a_i, x^*_W β©), where h: β^W β β 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 β₯ 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 β₯ 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.
ER -