A new step size rule for the superiorization method and its application in computerized tomography

Abstract

In this paper, we consider a regularized least squares problem subject to convex constraints. Our algorithm is based on the superiorization technique, equipped with a new step size rule which uses subgradient projections. The superiorization method is a two-step method where one step reduces the value of the penalty term and the other step reduces the residual of the underlying linear system (using an algorithmic operator T). For the new step size rule, we present a convergence analysis for the case when T belongs to a large subclass of strictly quasi-nonexpansive operators. To examine our algorithm numerically, we consider box constraints and use the total variation (TV) functional as a regularization term. The specific test cases are chosen from computed tomography using both noisy and noiseless data. We compare our algorithm with previously used parameters in superiorization. The T operator is based on sequential block iteration (for which our convergence analysis is valid), but we also use the conjugate gradient method (without theoretical support). Finally, we compare with the well-known “fast iterative shrinkage-thresholding algorithm” (FISTA). The numerical results demonstrate that our new step size rule improves previous step size rules for the superiorization methodology and is competitive with, and in several instances behaves better than, the other methods.

Appendix

In this appendix, we provide some reasons for picking subgradient projections rather than other non-ascent directions in Algorithm 2.

Let g and Ω be a convex function and a closed convex set, respectively. Furthermore, let

$$C=\text{argmin}_{x\in{{\varOmega}}} g(x),~z\in C,~x\not\in C,~x\in{{\varOmega}}$$

and ℓ denote a subgradient of g at x. Also, assume that there exists T > 0 such that x − Tℓ ∈Ω. We show that there exists t > 0 such that d(y, C) < d(x, C) where y = x − tℓ and d is a Euclidean metric on $\mathbb {R}^{n}.$ Based on the definition of ℓ, we get 〈z − x, ℓ〉≤ g(z) − g(x). Since z ∈ C and x ∈Ω, we get g(z) − g(x) < 0 which leads to 〈z − x, ℓ〉 < 0. Put 𝜃 = g(z) − g(x) < 0 and for t > 0 we have

$$ \begin{array}{@{}rcl@{}} \|z-y\|^{2}&=&\|z-x+t\ell\|^{2}=\langle z-x+t\ell, z-x+t\ell\rangle\\ &=&\|z-x\|^{2}+2t\langle z-x, \ell\rangle+t^{2}\|\ell\|^{2}\\ &\leq&\|z-x\|^{2}+2t\theta+t^{2}\|\ell\|^{2}\\ &=&\|z-x\|^{2}+t(2\theta+t\|\ell\|^{2}). \end{array} $$

Since 𝜃 < 0, we get that 2𝜃 + t∥ℓ∥² < 0 for small enough t > 0. Therefore, we get

$$ \|z-y\|<\|z-x\|. $$

(32)

Since g is a convex function, we conclude that C is a convex set and consequently P_C(x), the orthogonal projection of x onto C, exists. Replacing z by P_C(x) in (32) leads to

$$ \|P_{C}(x)-y\|<\|P_{C}(x)-x\|=d(x,C). $$

(33)

Combining (33) and the fact that d(y, C) = ∥P_C(y) − y∥≤∥P_C(x) − y∥, we get d(y, C) < d(x, C). Note: for 0 < t ≤ T and x − Tℓ, x ∈Ω, we get y = x − tℓ = (t/T)(x − Tℓ) + (1 − t/T)x ∈Ω.