On the finitary content of Dykstra's cyclic projections algorithm

2023/06/16 by Pedro Pinto, Pinto, Pedro · 1 citation
Computer Science · Mathematics · #03F10 #41A65 #47H09 #90C25 #Advanced Optimization Algorithms Research #Computability, Logic, AI Algorithms #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2306.09791

openalex publication_date 2023/06/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the asymptotic behaviour of the well-known Dykstra's algorithm through the lens of proof-theoretical techniques. 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 primitive recursive rates of metastability in a full general setting. Moreover, under an additional assumption, we are even able to obtain effective general rates of convergence. We argue that such additional condition is actually necessary for the existence of general uniform rates of convergence.

Cited by

• The Uniform Functional Interpretation with Informative Types

Related

• On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
• A rate of metastability for the Halpern type Proximal Point Algorithm
• Fast-Forwarding Stalling in Dykstra's Algorithm
• Cyclic Relaxed Douglas-Rachford Splitting for Inconsistent Nonconvex Feasibility
• Nonasymptotic and asymptotic linear convergence of an almost cyclic SHQP Dykstra's algorithm for polyhedral problems