An Interior-Point Method for Modified Total Variation Exploiting Transform-Domain Sparsity

The total variation (TV) minimization can be utilized in a compressive sensing framework to recover a signal from a small number of measurements by searching for a signal with a sparse gradient. However, many natural signals of interest, such as natural images, generally have sparse representations in known transforms. Hence, the performance of the signal reconstruction procedure can be improved by also taking into account this transform-domain sparsity of the signal. Thus, the TV minimization problem can be modified by introducing an $l_1$-norm penalty term. The $l_1$-regularized TV minimization problem searches for a signal with a sparse gradient and a sparse representation in the given transform. The main contribution of this paper is the derivation of a customized interior-point method for solving the $l_1$-regularized TV minimization problem that computes the search direction of the Newton method efficiently by exploiting the specific structure of the Hessian.