How to Learn Dykstra’s Projection Algorithm: Convex Sets, Correction Vectors, Alternating Projections and Best Approximation

Wait, What?

If a point violates several convex constraints, repeatedly projecting onto one constraint at a time is not always enough to recover the closest feasible point.

Dykstra’s projection algorithm solves a deceptively subtle problem: given a point and several closed convex sets whose intersection is nonempty, find the Euclidean projection of that point onto the intersection. In plain language, find the feasible point that is closest to the original point.

A beginner might try ordinary alternating projections: project onto set A, then B, then A again, and so on. That can find a feasible point, but in general it need not find the particular feasible point that is closest to the original input. Dykstra’s algorithm adds correction vectors that remember information lost at previous projection steps.

At beginner level, this is a lesson about geometry and iterative correction. At professional level, it becomes a lesson in convex analysis, primal–dual interpretation, stopping criteria, numerical tolerances, stalling, warm starts, distributed variants and independent optimality checks.

Quick Answer

Learn Dykstra in this order: Euclidean projection → convex sets → projection onto an intersection → alternating projections → why alternating projections can miss the best approximation → correction vectors → cyclic Dykstra updates → convergence → stopping criteria → numerical stability → stalling → generalisations → professional validation.

1. Start with the projection problem

For a closed convex set C and point x0, the Euclidean projection is:

P_C(x0) = argmin over x in C of ||x - x0||²

Because the set is closed and convex, the closest point is well defined and unique in Euclidean space.

If C is a half-space, box, affine subspace, ball or simple cone, projection may have a direct formula.

2. Intersections create the real challenge

Suppose:

C = C1 ∩ C2 ∩ ... ∩ Cm

and each individual projection P_Ci is easy, while projection directly onto the whole intersection is difficult.

This structure appears in constrained least squares, signal processing, statistics, image reconstruction, matrix problems and feasibility formulations.

3. Alternating projections are the obvious first idea

For two sets:

x = x0
repeat:
    x = P_C1(x)
    x = P_C2(x)

Alternating projections are elegant and important. But when the intersection contains many points, the limit need not equal the Euclidean projection of the original x0 onto the intersection.

Dykstra’s correction terms repair this missing information.

4. The correction vector is the memory

For two convex sets, a common Dykstra form maintains two correction vectors p and q:

x = x0
p = 0
q = 0

repeat:
    y = P_C1(x + p)
    p = x + p - y

    x_new = P_C2(y + q)
    q = y + q - x_new

    x = x_new

The corrections carry forward the discrepancy introduced when projection onto one set moved the iterate.

5. Why the correction term is not just momentum

It is tempting to compare p and q with momentum in optimisation. That analogy is too loose.

The correction vectors have a precise convex-analytic role. Dykstra’s method can be understood through a dual optimisation problem, where these variables correspond to dual information associated with the constraints.

Use the geometric intuition for beginners, but do not teach the corrections as an arbitrary acceleration trick.

6. A simple geometric example

Imagine a point outside both a disk and a half-space, while the disk and half-space overlap. Projecting alternately onto one and then the other can converge to a feasible point.

Dykstra’s corrections ensure the sequence instead converges to the point in the intersection that minimises distance to the original point.

A useful classroom exercise is to draw both sequences on graph paper. The paths may look similar while their limiting interpretation differs.

7. The many-set cyclic algorithm

For sets C1,...,Cm, maintain one correction vector per set:

x = x0
p[i] = 0 for all i

repeat cycles:
    for i = 1..m:
        y = P_Ci(x + p[i])
        p[i] = x + p[i] - y
        x = y

This is the core cyclic Dykstra pattern.

The exact notation varies across texts, so when implementing from a source, derive the update carefully rather than copying formulas from two different conventions.

8. Projection operators deserve their own tests

Dykstra can only be as correct as the individual projections. Before combining them, test each P_Ci independently.

For a projection routine, verify:

the returned point lies in the set;
idempotence: projecting an already feasible point changes nothing beyond tolerance;
known analytic examples;
boundary cases;
scale behaviour.

9. Half-space projection is a useful first implementation

For a half-space:

aᵀx ≤ b

if x is already feasible, return x. Otherwise project orthogonally to the boundary:

x - ((aᵀx - b) / ||a||²) a

This gives learners a concrete projection primitive before moving to richer sets.

10. Box projection is even simpler

For component-wise bounds:

lower_i ≤ x_i ≤ upper_i

projection is just clipping:

x_i = min(max(x_i, lower_i), upper_i)

Combining a box with another convex constraint makes an excellent first Dykstra exercise.

11. The algorithm targets best approximation, not just feasibility

Always state the objective explicitly:

minimise ||x - x0||²
subject to x in every Ci

If you only care about finding any feasible point, other projection methods may be adequate. Dykstra is especially important when closeness to the original point matters.

12. Stopping criteria need more than “x barely moved”

A small change between iterates can occur even when the solution is not sufficiently accurate. Modern analyses highlight that Dykstra can exhibit stalling behaviour on some problems.

Useful stopping signals can include:

primal iterate change;
maximum constraint violation;
dual or correction residuals;
objective improvement;
independent optimality checks when available.

Use a combination appropriate to the application.

13. Feasibility tolerance and optimality tolerance are different

A point can be almost feasible but still not be the closest feasible point. Conversely, numerical noise can make an excellent solution appear microscopically infeasible.

Define separate tolerances:

feasibility_tol
stationarity_or_optimality_tol

Do not hide both inside one unexplained epsilon.

14. Scaling can dominate numerical behaviour

If one constraint is expressed in units around 10^-6 and another around 10^9, naive absolute tolerances can be meaningless.

Normalise constraints where appropriate and report both absolute and relative residuals.

Professional numerical algorithms should state the scale conventions under which tolerances are interpreted.

15. Correction vectors should be monitored

Because the corrections encode dual information, extreme growth or unexpected oscillation can reveal:

badly scaled constraints;
projection bugs;
inconsistent numerical conventions;
very slow convergence;
incorrect set definitions.

Log their norms during development.

16. Warm starts can be useful

If a sequence of nearby best-approximation problems must be solved, reusing prior information can reduce work. Research has studied warm-start behaviour and enhanced variants of Dykstra’s method.

But a warm start changes the experimental conditions. Compare fairly against cold-start baselines and ensure reused dual/correction information is mathematically consistent with the new problem.

17. Simultaneous and distributed variants exist

Dykstra-style ideas extend beyond a simple cyclic loop. Parallel, simultaneous and distributed variants appear in optimisation research, particularly when constraints are distributed across blocks or network nodes.

The teaching rule is simple: master the cyclic finite-set version before generalising.

18. The dual viewpoint explains the algorithm’s depth

Dykstra can be interpreted as alternating minimisation or block-coordinate optimisation on a dual problem. This helps explain:

why correction vectors matter;
why updates are structured by constraints;
how convergence analysis connects to convex optimisation;
why acceleration and distributed variants are possible.

A professional learner should eventually be able to move between geometric and dual interpretations.

19. Independent validation with a generic solver is valuable

For small and moderate test problems, solve the same quadratic projection problem with a trusted convex optimisation package or quadratic-programming solver.

Compare:

objective value
constraint violations
solution vector distance

Differential validation is especially useful when writing custom projection operators.

20. Synthetic test families should include easy and pathological geometry

Test:

orthogonal affine sets;
nearly parallel half-spaces;
boxes intersecting balls;
thin feasible regions;
points already in the intersection;
points far outside;
high-dimensional sparse constraints;
cases known to exhibit slow or stalled progress.

21. Track the whole convergence profile

Do not report only final iteration count. Record:

iteration
objective distance from x0
max constraint violation
iterate change
correction-vector norms
elapsed time

Plotting these quantities often reveals whether the algorithm is converging smoothly, stalling or suffering from scale problems.

22. How to teach this from beginner to professional

Predict: project a point onto a line, box or half-space by hand.
Run: trace alternating projections between two simple sets.
Investigate: add Dykstra corrections and compare the path.
Modify: rescale one constraint and observe numerical behaviour.
Make: implement a multi-set solver with residual logging, independent validation and several stopping criteria.

This sequence combines worked examples, visible traces and progressive independence rather than dropping learners immediately into abstract convex analysis.

23. A useful trace table

cycle | set | input x+p_i | projected y | correction p_i | violation | objective

Students should be able to explain why each correction changes and what information it preserves.

24. Common failure states

Calling ordinary alternating projections “Dykstra” without correction vectors.
Using an incorrect projection operator.
Stopping only because consecutive iterates are close.
Using one tolerance for both feasibility and optimality.
Ignoring scale differences between constraints.
Mixing formulas from incompatible notation conventions.
Assuming any feasible limit is the best approximation.
Benchmarking only well-conditioned intersections.
Failing to compare against an independent convex solver on test cases.

25. Practice ladder

Beginner: compute projections onto simple convex sets.
Foundation: implement alternating projections.
Intermediate: add Dykstra corrections for two and then many sets.
Advanced: derive the dual interpretation, improve stopping criteria and study stalling.
Professional: build a tested projection library with warm starts, sparse high-dimensional constraints, convergence telemetry, solver cross-checks and workload-specific acceleration experiments.

26. Ownership boundary

This article owns Dykstra’s projection algorithm as an algorithm-learning topic: convex projections, correction vectors, intersections, convergence, stopping, numerical behaviour and validation. It does not replace general convex optimisation, statistical modelling, image-processing pipelines, learner measurement or private system architecture.

Sources and further reading

Richard L. Dykstra, “An Algorithm for Restricted Least Squares Regression,” Journal of the American Statistical Association 78(384), 1983: DOI.
H. H. Bauschke and J. M. Borwein, “On Projection Algorithms for Solving Convex Feasibility Problems,” SIAM Review 38(3), 1996: DOI.
Xiaozhou Wang and Ting Kei Pong, “Convergence Rate Analysis of a Dykstra-Type Projection Algorithm,” SIAM Journal on Optimization, 2024: DOI.
Claudio Vestini and Idris Kempf, “Fast-Forwarding Stalling in Dykstra’s Algorithm,” 2025 preprint: arXiv.
ACM/IEEE-CS/AAAI CS2023, Algorithmic Foundations: CS2023.
Sue Sentance, Jane Waite and Maria Kallia, PRIMM programming pedagogy: SIGCSE 2019.

Professional rule: you understand Dykstra’s algorithm when you can distinguish best approximation from mere feasibility, explain the purpose of every correction vector, test each projection operator independently, separate feasibility from optimality stopping conditions, and verify your result against an independent solver on controlled problems.

Small Group Tutorials