  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.
