Source-linked AI summary
On the Effectiveness of Projection Methods for Convex Feasibility Problems with Linear Inequality Constraints
Y. Censor, W. Chen, P. L. Combettes, R. Davidi, G. T. Herman
TL;DR
The paper asks whether projection methods are competitive for convex feasibility problems with linear inequality constraints. It evaluates their comparative performance and surveys real-world uses, finding that correctly implemented methods are especially efficient on large, sparse, real-life problems, although they can converge slowly and are not always the approach of choice.
Problem
The paper asks whether projection methods are competitive with available alternatives for finite convex feasibility problems defined by linear equality or inequality constraints.
Method
The paper compares projection-method variants across several problem types and examines their use in scientific applications and commercial patents.
Results
Projection methods are very competitive for linear inequality constraints, with EAPM averaging about 60 times faster than PPM and 30 times faster than POCS in one experiment.
Takeaways & Limitations
Correctly implemented projection methods are especially efficient for large, sparse convex feasibility problems originating from real-life applications.
Takeaways & Limitations
Projection methods may converge slowly and are not necessarily the approach of choice for every problem.
Abstract
from arXiv · showhide
The effectiveness of projection methods for solving systems of linear inequalities is investigated. It is shown that they have a computational advantage over some alternatives and that this makes them successful in real-world applications. This is supported by experimental evidence provided in this paper on problems of various sizes (up to tens of thousands of unknowns satisfying up to hundreds of thousands of constraints) and by a discussion of the demonstrated efficacy of projection methods in numerous scientific publications and commercial patents (dealing with problems that can have over a billion unknowns and a similar number of constraints).
1 Introduction
The paper examines whether projection methods are competitive for finite convex feasibility problems defined by linear equalities or inequalities. It argues that they are highly competitive and connects this question to broad mathematical, scientific, and real-world applications.
- Projection methods: Projection methods generalize from affine-subspace and half-space projections to convex feasibility problems over closed convex sets in Hilbert spaces.Modern variants include block-iterative and string-averaging methods with flexible parallel implementations.
- Applications: Convex feasibility modeling supports problems across mathematics and the physical sciences, including sensor networks, radiation therapy, tomography, and magnetic resonance imaging.The cited application areas also include denoising, antenna design, materials science, watermarking, data compression, and demosaicking.
- Problem: The paper focuses on convex feasibility problems with finitely many Euclidean sets specified by linear equalities or inequalities.These problems arise in important applications, while alternative solution methods are also available.
- Paper scope: The paper addresses the competitiveness question through comparative performance studies of four problem types and examples from scientific and patent literature.Its stated contribution is to show that projection methods are very competitive for linear inequality constraints.
2 Comparisons
The paper argues that projection methods are competitive for linear inequality feasibility problems, challenging broader negative conclusions drawn from limited and suboptimally implemented comparisons. Experiments and applications show that appropriate relaxations can substantially improve speed and support large-scale scientific and clinical problems.
- Motivation: Earlier negative conclusions are limited by experiments on geometrically simple 2-set problems and suboptimal projection implementations.The authors specifically question whether those results justify general conclusions about projection-method effectiveness.
- Comparative performance: 45 times faster than PPM and 22 times faster than POCS, EAPM reached full convergence in 5 iterations for problems with M × N = 3000 × 7000.The authors state that this performance pattern was consistently observed across problems of various sizes.
- Comparative performance: Appropriate relaxation and extrapolation schemes can make projection methods much faster than unrelaxed POCS and PPM.The paper reports that EAPM and EPPM improve convergence, while relaxation schemes in the earlier study did not significantly improve convergence profiles.
- Applications: In clinical radiation-treatment planning, ART3+ was repeatedly applied to seek feasible points optimized under different linear criteria.The application included one feasibility run and eight optimization tasks compared with MOSEK optimizers.
3 Published and patented results
Published studies and commercial patents document projection methods solving large-scale scientific and practical problems, including instances with over a billion unknowns. The paper also qualifies their applicability: they are not always the approach of choice, but work well in important biomedical and imaging applications.
- Scientific publications: 59,049 unknowns were used in problems from one study, while radiation-therapy examples had 128,688 constraint pairs for only 515 unknowns.
- Scientific publications: 1,372,000,000 unknowns and potentially infinitely many equations occurred in a crystal-lattice orientation estimation problem solved with a variant of ART.The reported result was obtained after 1,000,000,000 projection steps.
- Scope: Projection methods are not necessarily the approach of choice in all applications.
- Scientific publications: In biomedical and image-processing applications, projection methods have worked well and been used successfully for a long time.The paper gives electron microscopy as an example, where leading groups consider ART with blobs the method of choice.
- Commercial patents: Commercial devices also use projection methods, although proprietary implementations are usually not published.The paper cites commercial emission tomography scanners and iterative reconstruction patents as examples.
4 Conclusion
The paper concludes that correctly implemented projection methods are highly efficient for convex feasibility problems with linear inequality constraints. Their strongest setting is large, sparse problems originating from real-life applications.
- Correctly implemented projection methods are very efficient for convex feasibility problems with linear inequality constraints.
- Their effectiveness is especially pronounced for problems that are large, sparse, and derived from real-life applications.