On Dykstra’s Algorithm with Bregman Projections

Abstract

We provide quantitative results on the asymptotic behavior of Dykstra’s algorithm with Bregman projections, a combination of the well-known Dykstra’s algorithm and the method of cyclic Bregman projections, designed to find best approximations and solve the convex feasibility problem in a non-Hilbertian setting. The result we provide arise through the lens of proof mining, a program in mathematical logic which extracts computational information from non-effective proofs. Concretely, we provide a highly uniform and computable rate of metastability of low complexity and, moreover, we also specify general circumstances in which one can obtain full and effective rates of convergence. As a byproduct of our quantitative analysis, we also for the first time establish the strong convergence of Dykstra’s method with Bregman projections in infinite dimensional (reflexive) Banach spaces.