On the finitary content of Dykstra’s cyclic projections algorithm

Abstract

We study the asymptotic behaviour of the well-known Dykstra’s algorithm. We provide an elementary proof for the convergence of Dykstra’s algorithm in which the standard argument is stripped to its central features and where the original compactness principles are circumvented, additionally providing highly uniform computable rates of metastability in a fully general setting. Moreover, under an additional assumption, we are even able to obtain effective general rates of convergence. We argue that such an additional condition is actually necessary for the existence of general uniform rates of convergence.