Dykstras algorithm with bregman projections: A convergence proof

Abstract

Dykstra’s algorithm and the method of cyclic Bregman projections are often employed to solve best approximation and convex feasibility problems, which are fundamental in mathematics and the physical sciences. Censor and Reich very recently suggested a synthesis of these methods, Dykstra’s algorithm with Bregman projections, to tackle a non-orthogonal best approximation problem, They obtained convergence when each constraint is a halfspace. It is shown here that this new algorithm works for general closed convex constraints; this complements Censor and Reich’s result and relates to a framework by Tseng. The proof rests on Boyle and Dykstra’s original work and on strong properties of Bregman distances corresponding to Legendre functions. Special cases and observations simplifying the implementation of the algorithm are aiso discussed

Keywords:

• Best Approximation
• Bregman Distance
• Bregman Projection
• Convex Feasibility
• Cyclic Projections
• Dykstra’s Algorithm
• Han’s Algorithm
• Hildreth’s Method
• Legendre Function

^†Research partially supported by NSERC

^†Research partially supported by NSERC

Notes

^†Research partially supported by NSERC