1st Edition

Iterative Optimization in Inverse Problems

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

    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.

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

    Sequential Optimization
    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
    Projected Gradient Descent
    Relaxed Gradient Descent
    Regularized Gradient Descent
    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

    Contraction Operators
    Convex Sets in RJ
    Orthogonal Projection Operators
    Firmly Nonexpansive Gradients

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

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

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

    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

    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
    Modifying the KL Distance
    The ABMART Algorithm
    The ABEMML Algorithm

    Alternating Minimization
    Alternating Minimization

    The EM Algorithm
    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
    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

    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
    Saddle Points

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

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

    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




    Charles Byrne