On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
Files
(Published version)
Date
2020
Authors
Bauschke, H.H.
Burachik, R.S.
Herman, D.B.
Kaya, C.Y.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Optimization Letters, 2020; 14(8):1975-1987
Statement of Responsibility
Conference Name
Abstract
A popular method for finding the projection onto the intersection of two closed convex subsets in Hilbert space is Dykstra’s algorithm. In this paper, we provide sufficient conditions for Dykstra’s algorithm to converge rapidly, in finitely many steps. We also analyze the behaviour of Dykstra’s algorithm applied to a line and a square. This case study reveals stark similarities to the method of alternating projections. Moreover, we show that Dykstra’s algorithm may stall for an arbitrarily long time. Finally, we present some open problems.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2020 Springer
Access Condition Notes: Accepted manuscript available after 1 July 2021