1st Edition

# Iterative Optimization in Inverse Problems

By Charles L. Byrne Copyright 2014
300 Pages 6 B/W Illustrations
by Chapman & Hall

300 Pages
by Chapman & Hall

Also available as eBook on:

Iterative Optimization in Inverse Problems brings together a number of important iterative algorithms for medical imaging, optimization, and statistical estimation. It incorporates recent work that has not appeared in other books and draws on the author’s considerable research in the field, including his recently developed class of SUMMA algorithms. Related to sequential unconstrained minimization methods, the SUMMA class includes a wide range of iterative algorithms well known to researchers in various areas, such as statistics and image processing.

Organizing the topics from general to more specific, the book first gives an overview of sequential optimization, the subclasses of auxiliary-function methods, and the SUMMA algorithms. The next three chapters present particular examples in more detail, including barrier- and penalty-function methods, proximal minimization, and forward-backward splitting. The author also focuses on fixed-point algorithms for operators on Euclidean space and then extends the discussion to include distance measures other than the usual Euclidean distance. In the final chapters, specific problems illustrate the use of iterative methods previously discussed. Most chapters contain exercises that introduce new ideas and make the book suitable for self-study.

Unifying a variety of seemingly disparate algorithms, the book shows how to derive new properties of algorithms by comparing known properties of other algorithms. This unifying approach also helps researchers—from statisticians working on parameter estimation to image scientists processing scanning data to mathematicians involved in theoretical and applied optimization—discover useful related algorithms in areas outside of their expertise.

Background
Overview
An Urns Model for Remote Sensing
Hidden Markov Models
Measuring the Fourier Transform
Transmission Tomography
Emission Tomography
A Unifying Framework

Sequential Optimization
Overview
Examples of SUM
Auxiliary-Function Methods
The SUMMA Class of AF Methods

Barrier-Function and Penalty-Function Methods
Barrier Functions
Examples of Barrier Functions
Penalty Functions
Examples of Penalty Functions
Basic Facts

Proximal Minimization
The Basic Problem
Proximal Minimization Algorithms
Some Obstacles
All PMA Are SUMMA
Convergence of the PMA
The Non-Differentiable Case
The IPA
The Projected Landweber Algorithm
The Simultaneous MART
A Convergence Theorem
Another Job for the PMA
The Goldstein-Osher Algorithm
A Question

The Forward-Backward Splitting Algorithm
Moreau’s Proximity Operators
The FBS Algorithm
Convergence of the FBS Algorithm
Some Examples
Minimizing f2 over a Linear Manifold
Feasible-Point Algorithms

Operators
Overview
Operators
Contraction Operators
Convex Sets in RJ
Orthogonal Projection Operators
Exercises

Averaged and Paracontractive Operators
Averaged Operators
Two Useful Identities
The Krasnosel’skii-Mann-Opial Theorem
Affine Linear Operators
Paracontractive Operators
Exercises

Convex Feasibility and Related Problems
Convex Constraint Sets
Using Orthogonal Projections
The ART
Regularization
Avoiding the Limit Cycle
Exercises

Eigenvalue Bounds
Introduction and Notation
Overview
Cimmino’s Algorithm
The Landweber Algorithms
Some Upper Bounds for L
Simultaneous Iterative Algorithms
Block-Iterative Algorithms
Exercises

Jacobi and Gauss-Seidel Methods
The Jacobi and Gauss-Seidel Methods: An Example
Splitting Methods
Some Examples of Splitting Methods
Jacobi’s Algorithm and JOR
The Gauss-Seidel Algorithm and SOR
Summary

The SMART and EMML Algorithms
The SMART Iteration
The EMML Iteration
The EMML and the SMART as AM
The SMART as SUMMA
The SMART as PMA
Using KL Projections
The MART and EMART Algorithms
Extensions of MART and EMART
Convergence of the SMART and EMML
Regularization
Modifying the KL Distance
The ABMART Algorithm
The ABEMML Algorithm

Alternating Minimization
Alternating Minimization
Exercises

The EM Algorithm
Overview
A Non-Stochastic Formulation of EM
The Stochastic EM Algorithm
The Discrete Case
Missing Data
The Continuous Case
EM and the KL Distance
Finite Mixture Problems

Geometric Programming and the MART
Overview
An Example of a GP Problem
The Generalized AGM Inequality
Posynomials and the GP Problem
The Dual GP Problem
Solving the GP Problem
Solving the DGP Problem
Constrained Geometric Programming
Exercises

Variational Inequality Problems and Algorithms
Monotone Functions
The Split-Feasibility Problem
The Variational Inequality Problem
Korpelevich’s Method for the VIP
On Some Algorithms of Noor
Split Variational Inequality Problems
Exercises

Set-Valued Functions in Optimization
Overview
Notation and Definitions
Basic Facts
Monotone Set-Valued Functions
Resolvents
Split Monotone Variational Inclusion
Solving the SMVIP
Special Cases of the SMVIP
The Split Common Null-Point Problem
Exercises

Fenchel Duality
The Legendre-Fenchel Transformation
Fenchel’s Duality Theorem
An Application to Game Theory
Exercises

Compressed Sensing
Compressed Sensing
Sparse Solutions
Minimum One-Norm Solutions
Why Sparseness?
Compressed Sampling

Appendix: Bregman-Legendre Functions
Essential Smoothness and Essential Strict Convexity
Bregman Projections onto Closed Convex Sets
Bregman-Legendre Functions

Bibliography

Index

### Biography

Charles Byrne