Source-linked AI summary
Perturbation Resilience and Superiorization of Iterative Algorithms
Y. Censor, R. Davidi, G. T. Herman
TL;DR
The paper addresses how to obtain optimized or otherwise superior feasible points without incurring the greater computational demands of full optimization algorithms. It develops superiorization by perturbing perturbation-resilient feasibility methods and demonstrates the approach in image reconstruction from projections, while noting that its mathematical theory remains incomplete.
Problem
Finding an objective-optimizing point within a convex-set intersection generally requires more memory and computation than finding any feasible point.
Method
The paper perturbs projection algorithms, including SAP and BIP schemes, to steer their iterates toward superior feasible points while leveraging bounded perturbation resilience.
Results
The method is illustrated in image reconstruction from projections, where TV-superiorized versions of two algorithms produce lower objective values than their nonsuperiorized counterparts.
Takeaways & Limitations
Perturbation resilience can be used proactively to extract benefits from computationally efficient feasibility algorithms in applications including image reconstruction.
Takeaways & Limitations
The superiorization theory remains a collection of heuristic ideas without a full mathematical theory or general proof of objective improvement.
Abstract
from arXiv · showhide
Iterative algorithms aimed at solving some problems are discussed. For certain problems, such as finding a common point in the intersection of a finite number of convex sets, there often exist iterative algorithms that impose very little demand on computer resources. For other problems, such as finding that point in the intersection at which the value of a given function is optimal, algorithms tend to need more computer memory and longer execution time. A methodology is presented whose aim is to produce automatically for an iterative algorithm of the first kind a "superiorized version" of it that retains its computational efficiency but nevertheless goes a long way towards solving an optimization problem. This is possible to do if the original algorithm is "perturbation resilient," which is shown to be the case for various projection algorithms for solving the consistent convex feasibility problem. The superiorized versions of such algorithms use perturbations that drive the process in the direction of the optimizer of the given function. After presenting these intuitive ideas in a precise mathematical form, they are illustrated in image reconstruction from projections for two different projection algorithms superiorized for the function whose value is the total variation of the image.
1. Introduction
The paper proposes using perturbation-resilient feasibility algorithms to steer iterates toward superior feasible points without adopting full optimization algorithms. This approach targets large real-world problems where projection methods retain computational advantages.
- 1. Introduction: Optimization over feasible points is generally more computationally demanding than finding any feasible point, motivating an intermediate superiorization methodology.
- 1. Introduction: Projection methods are effective for huge, sparse convex feasibility problems because projections onto individual sets are easier than projection onto their intersection.
- 1. Introduction: Their computational advantage allows projection methods to handle problem dimensions beyond which more sophisticated methods may become inefficient or unusable because of memory requirements.
- 1. Introduction: Superiorization uses bounded perturbations to steer projection-method iterates toward superior feasible points while retaining a feasibility algorithm’s computational framework.The approach relies on perturbation resilience in string-averaging and block-iterative projection schemes.
- 1. Introduction: The methodology is motivated by inverse problems in image reconstruction, IMRT/IMPT, and electron microscopy, with examples drawn from these applications.
2. Specification of the superiorization methodology
The methodology formalizes superiorization for problem structures and uses bounded perturbation resilience to preserve feasibility while steering iterative algorithms toward lower objective values.
- Problem structures: A problem structure pairs a problem set with a nonnegative proximity function whose zero value identifies solutions.For convex feasibility, the solution condition is equivalent to membership in the intersection of the closed convex sets.
- Bounded perturbation resilience: Bounded perturbation resilience means that an algorithm still converges to a problem solution when each iterate receives suitable bounded perturbations.This property is established for projection algorithms in the SAP and BIP families under the stated convex-feasibility assumptions.
- SAP methods: For SAP methods, amalgamators combine projections along fit index vectors using positive weights that sum to one.The resulting algorithmic operator is covered by a bounded perturbations resilience theorem and corollary.
- BIP methods: The same resilience pattern is established for BIP methods, whose blocks contain ordered subsets of the constraint indices.Under the nonempty-intersection and coverage assumptions, perturbed iterates converge to the intersection.
- Superiorization methodology: The superiorization framework augments a feasibility algorithm with objective-reducing perturbations while retaining a termination rule based on the proximity function.The output is the first iterate whose proximity value is at most ε, provided all earlier iterates exceed ε.
Assumptions
The superiorization construction assumes a continuous problem measure, a bounded-perturbation-resilient feasibility algorithm that decreases this measure, and a convex objective function. It also uses a summable sequence of positive step sizes to generate objective-directed perturbations.
- The construction assumes a continuous problem measure Pr_T, a bounded perturbation resilient algorithm P, and a convex objective function φ.
- The superiorized sequence is generated under these assumptions using the algorithmic operator P_T and the problem measure Pr_T.
- The perturbation step sizes form a summable sequence of positive real numbers, such as γ_l = a^l for 0 < a < 1.
Superiorized Version of Algorithm P
The Superiorized Version of Algorithm P inserts bounded, objective-reducing perturbations before each feasibility step while preserving convergence to a solution under the stated assumptions. However, the theory does not prove that the resulting feasible output always has a lower objective value than the unperturbed algorithm's output.
- Each iteration perturbs x_k by β_kv_k, then applies P_T to the perturbed point y before advancing the iteration.
- The sequence and output depend on the initial point, subgradient selection, summable sequence, problem, and stopping criterion.
- Under the assumptions, the generated sequence either contains a solution of T or is infinite and converges to a solution of T.
- The construction guarantees a feasible output with φ no greater than ε when the problem measure reaches the stopping threshold, but not a general comparison with the unperturbed output.
- The perturbation direction is chosen from a negative subgradient of φ, or set to zero, while summable step sizes make the perturbations eventually small.
3. Illustrations of the superiorization methodology
The methodology is illustrated on head-image reconstruction from consistent projection data using ART-like and block-iterative methods, each with and without TV-superiorization. In both algorithms, the superiorized reconstructions have lower TV than their nonsuperiorized counterparts, while the phantom itself has higher TV than either superiorized reconstruction.
- The experiment reconstructs a 243 × 243 head phantom from consistent data comprising 82 sets of parallel lines and 25,452 total hyperplanes.
- The two base methods are an ART-like string-averaging projection method and a block-iterative projection method with one block for each of the 82 projection views.
- Total variation is used as the superiorized objective for the reconstructed 243 × 243 images.
- Table 1 compares TV values for superiorized and original outputs of the two projection algorithms, and the reported comparison favors superiorization for both algorithms.
- Figure 1 uses the same initial point and stopping criterion to display the phantom, two original reconstructions, and their TV-superiorized versions.
- The phantom's TV is 450.53, higher than the TV of either superiorized reconstruction, supporting the paper's practical comparison with TV-optimization.
4. Discussion and conclusions
The paper presents superiorization as a proactive use of perturbation resilience to improve solutions while retaining efficient iterative algorithms. It reports potential image-reconstruction benefits but identifies mathematical, algorithmic, and computational validation as continuing needs.
- Perturbation resilience is used proactively to steer efficient iterative algorithms toward solutions superior under a chosen criterion.The premise combines an efficient bounded-perturbation-resilient algorithm with perturbations designed around the desired criterion.
- The paper reports potential benefits for image reconstruction from projections while framing superiorization as an initial step toward a broader field.
- Precise validation remains necessary to establish convergence, characterize limit points, and assess how perturbation choices affect superiorization.
- Future work includes expanding bounded perturbation resilience theory and studying common fixed-point and inconsistent problems.