Proof Mining and the Convex Feasibility Problem : the Curious Case of Dykstra's Algorithm

Abstract

In a recent proof mining application, the proof-theoretical analysis of Dykstra's cyclic projections algorithm resulted in quantitative information expressed via primitive recursive functionals in the sense of Gödel. This was surprising as the proof relies on several compactness principles and its quantitative analysis would require the functional interpretation of arithmetical comprehension. Therefore, a priori one would expect the need of Spector’s bar-recursive functionals. In this paper, we explain how the use of bounded collection principles allows for a modified intermediate proof justifying the finitary results obtained, and discuss the approach in the context of previous eliminations of weak compactness arguments in proof mining.