Dykstra's algorithm finds for each ${\displaystyle r}$  the only ${\displaystyle {\bar {x}}\in C\cap D}$  such that:

${\displaystyle \|{\bar {x}}-r\|^{2}\leq \|x-r\|^{2},{\text{for all }}x\in C\cap D,}$ 

where ${\displaystyle C,D}$  are convex sets. This problem is equivalent to finding the projection of ${\displaystyle r}$  onto the set ${\displaystyle C\cap D}$ , which we denote by ${\displaystyle {\mathcal {P}}_{C\cap D}}$ .

To use Dykstra's algorithm, one must know how to project onto the sets ${\displaystyle C}$  and ${\displaystyle D}$  separately.

First, consider the basic alternating projection (aka POCS) method (first studied, in the case when the sets ${\displaystyle C,D}$  were linear subspaces, by John von Neumann^[1]), which initializes ${\displaystyle x_{0}=r}$  and then generates the sequence

${\displaystyle x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right)}$ .

Dykstra's algorithm is of a similar form, but uses additional auxiliary variables. Start with ${\displaystyle x_{0}=r,p_{0}=q_{0}=0}$  and update by

${\displaystyle y_{k}={\mathcal {P}}_{D}(x_{k}+p_{k})}$ 

${\displaystyle p_{k+1}=x_{k}+p_{k}-y_{k}}$ 

${\displaystyle x_{k+1}={\mathcal {P}}_{C}(y_{k}+q_{k})}$ 

${\displaystyle q_{k+1}=y_{k}+q_{k}-x_{k+1}.}$ 

Then the sequence ${\displaystyle (x_{k})}$  converges to the solution of the original problem. For convergence results and a modern perspective on the literature, see ^[2]

• Boyle, J. P.; Dykstr, R. L. (1986). "A Method for Finding Projections onto the Intersection of Convex Sets in Hilbert Spaces". Advances in Order Restricted Statistical Inference. Lecture Notes in Statistics. Vol. 37. pp. 28–47. doi:10.1007/978-1-4613-9940-7_3. ISBN 978-0-387-96419-5.
• Gaffke, N.; Mathar, R. (1989). "A cyclic projection algorithm via duality". Metrika. 36: 29–54. doi:10.1007/bf02614077. S2CID 120944669.