Splitting with Near-Circulant Linear Systems: Applications to Total Variation CT and PET

Autor:	Ryu, Ernest K., Ko, Seyoon, Won, Joong-Ho
Rok vydání:	2018
Předmět:	Mathematics - Optimization and Control
Druh dokumentu:	Working Paper
Popis:	Many imaging problems, such as total variation reconstruction of X-ray computed tomography (CT) and positron-emission tomography (PET), are solved via a convex optimization problem with near-circulant, but not actually circulant, linear systems. The popular methods to solve these problems, alternating direction method of multipliers (ADMM) and primal-dual hybrid gradient (PDHG), do not directly utilize this structure. Consequently, ADMM requires a costly matrix inversion as a subroutine, and PDHG takes too many iterations to converge. In this paper, we present near-circulant splitting (NCS), a novel splitting method that leverages the near-circulant structure. We show that NCS can converge with an iteration count close to that of ADMM, while paying a computational cost per iteration close to that of PDHG. Through experiments on a CUDA GPU, we empirically validate the theory and demonstrate that NCS can effectively utilize the parallel computing capabilities of CUDA. Comment: Published in SIAM Journal on Scientific Computing
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1810.13100 Zobrazit plný text záznamu View this record from Arxiv