Signal recovery in the polychromatic computed tomography model: Injectivity and complexity
En palabras de los autores
We consider a nonlinear model motivated by polychromatic computed tomography (CT). Here, distinct -dimensional signals must be recovered from measurements that obey the nonlinear model , where 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 (for any measurement ensemble ) must exceed the number of unknowns to guarantee that the underlying signals are identifiable. We construct a measurement ensemble that ensures perfect signal recovery almost surely provided , thereby isolating the injectivity threshold up to an additive factor . We also study computational complexity of signal recovery in this model with a general measurement ensemble . We show that if , 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.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 9 pages