From Surf Wiki (app.surf) — the open knowledge base

Dykstra's projection algorithm

Optimization algorithm

Dykstra's algorithm is a method that computes a point in the intersection of convex sets, and is a variant of the alternating projection method (also called the projections onto convex sets method). In its simplest form, the method finds a point in the intersection of two convex sets by iteratively projecting onto each of the convex set; it differs from the alternating projection method in that there are intermediate steps. A parallel version of the algorithm was developed by Gaffke and Mathar.

The method is named after Richard L. Dykstra who proposed it in the 1980s.

A key difference between Dykstra's algorithm and the standard alternating projection method occurs when there is more than one point in the intersection of the two sets. In this case, the alternating projection method gives some arbitrary point in this intersection, whereas Dykstra's algorithm gives a specific point: the projection of r onto the intersection, where r is the initial point used in the algorithm,

Algorithm

Dykstra's algorithm finds for each r the only \bar{x} \in C\cap D such that: : |\bar{x}-r|^2\le |x-r|^2, \text{for all } x\in C \cap D,

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

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

First, consider the basic alternating projection (aka POCS) method (first studied, in the case when the sets C,D were linear subspaces, by John von Neumann), which initializes x_0=r and then generates the sequence

: 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 x_0 =r, p_0=q_0=0 and update by

: y_k = \mathcal{P}_D( x_k + p_k )

: p_{k+1} = x_k + p_k - y_k

: x_{k+1} = \mathcal{P}_C( y_k + q_k )

: q_{k+1} =y_k + q_k - x_{k+1}.

Then the sequence (x_k) converges to the solution of the original problem. For convergence results and a modern perspective on the literature, see.

Citations

References

J. von Neumann, On rings of operators. Reduction theory, Ann. of Math. 50 (1949) 401–485 (a reprint of lecture notes first distributed in 1933).
P. L. Combettes and J.-C. Pesquet, "Proximal splitting methods in signal processing," in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, (H. H. Bauschke, [[Regina S. Burachik. R. S. Burachik]], P. L. Combettes, V. Elser, D. R. Luke, and H. Wolkowicz, Editors), pp. 185–212. Springer, New York, 2011 [https://link.springer.com/chapter/10.1007/978-1-4419-9569-8_10]

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

convex-geometry optimization-algorithms-and-methods

Want to explore this topic further?

Ask Mako anything about Dykstra's projection algorithm — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report