Scaled projected-directions methods with application to transmission tomography
- PDF / 2,819,661 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 148 Views
Scaled projected‑directions methods with application to transmission tomography Guillaume Mestdagh1 · Yves Goussard2 · Dominique Orban3 Received: 12 August 2019 / Revised: 9 January 2020 / Accepted: 9 January 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Statistical image reconstruction in X-ray computed tomography yields large-scale regularized linear least-squares problems with nonnegativity bounds, where the memory footprint of the operator is a concern. Discretizing images in cylindrical coordinates results in significant memory savings, and allows parallel operator–vector products without on-the-fly computation of the operator, without necessarily decreasing image quality. However, it deteriorates the conditioning of the operator. We improve the Hessian conditioning by way of a block-circulant scaling operator and we propose a strategy to handle nondiagonal scaling in the context of projecteddirections methods for bound-constrained problems. We describe our implementation of the scaling strategy using two algorithms: TRON, a trust-region method with exact second derivatives, and L-BFGS-B, a linesearch method with a limitedmemory quasi-Newton Hessian approximation. We compare our approach with one where a change of variable is made in the problem. On two reconstruction problems, our approach converges faster than the change of variable approach, and achieves much tighter accuracy in terms of optimality residual than a first-order method. Keywords X-ray CT reconstruction · Projected-direction methods · Scaling
* Guillaume Mestdagh [email protected] Yves Goussard [email protected] Dominique Orban [email protected] 1
Institute of Biomedical Engineering, Polytechnique Montréal, Montréal, QC, Canada
2
Institute of Biomedical Engineering and Department of Electrical Engineering, Polytechnique Montréal, Montréal, QC, Canada
3
GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, QC, Canada
13
Vol.:(0123456789)
G. Mestdagh et al.
1 Introduction We consider the bound-constrained problem
min f (𝐱)
s.t. 𝐱 ⩾ 0,
(1)
where f ∶ ℝn → ℝ is convex and C2 . We assume that ∇2 f cannot be stored explicitly or in factorized form. We are particularly interested in the case where (1) is large and badly scaled. Our main motivation is to solve efficiently statistical image reconstruction problems arising from X-ray Computed Tomography (CT) (Herman 2009). Whereas cartesian coordinates are typical, discretizing such problems in cylindrical coordinates yields large savings in storage, but results in badly scaled problems and, without proper scaling, off-the-shelf solvers usually fail. In this paper we employ a scaling strategy that exploits the structure of f combined with the trust-region projected Newton method of Lin and Moré (1999) and with the line search limited-memory BFGS for bound-constrained problems of Byrd et al. (1995) to maintain satisfaction of the bound constraints at all times. 1.1 Motivation
Data Loading...
