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-orthogonal setting. The results 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, which, in particular, contain the case of polyhedra in Euclidean spaces. 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 suitable infinite-dimensional spaces.