Find your next learning step
Dykstra’s correction vectors preserve constraint history, turning repeated convex projections into a best-approximation method rather than a feasibility routine.
Open the chapter contents · Topology root · Gold Standard of Education · How X Works
Chapter contents
Choose the route closest to the question, or read from Chapter 1 for the complete argument. The chapters remain open on the page; these grouped routes are an index.
Route 1 · Define the target
Route 2 · Work the correction ledger
Route 3 · Transfer and generalise
Route 4 · Check limits and implementation
Route 5 · Ask and continue
CHAPTER 1 OF 12 · DEFINE THE TARGET
1. Feasible is not the same as nearest
Alternating or cyclic projections can find a point in an intersection of convex sets. Yet many applications ask for the nearest feasible point to a starting point. These are different goals. Dykstra’s algorithm adds correction vectors so that repeated projections recover the metric projection onto the intersection under its convex assumptions.
The correction vectors are memory. They restore displacement that a later projection would otherwise erase. This is why Dykstra can reach the best approximation while plain alternating projections may stop at another feasible point.
CHAPTER 2 OF 12 · DEFINE THE TARGET
2. The two-set algorithm
Let C and D be closed convex sets in a Hilbert space, with a nonempty intersection. Start at x⁰ with corrections p⁰=q⁰=0. One cycle computes y=P_C(x+p), updates p=x+p−y, then computes x=P_D(y+q) and updates q=y+q−x.
The formulas look like alternating projections with two residuals attached. Those residuals are not numerical errors. They are dual-like corrections associated with constraints, and their update order belongs to the algorithm.
CHAPTER 3 OF 12 · WORK THE CORRECTION LEDGER
3. An example where alternating projections stop early
Work in the plane. Let C={(x₁,x₂):x₁≤0} and D={(x₁,x₂):x₁+x₂≤0}. Start at z=(2,1). Plain alternating projection first maps z to (0,1) in C, then to (−0.5,0.5) in D. That point already lies in both sets, so later cycles do nothing.
Its squared distance from z is (2.5)²+(0.5)²=6.5. The origin is also feasible and has squared distance 2²+1²=5. In fact the origin is the nearest feasible point. Plain alternation found feasibility, not the best approximation.
CHAPTER 4 OF 12 · WORK THE CORRECTION LEDGER
4. The correction-vector ledger
Dykstra begins with the same two projections but carries what was removed.
| Cycle | Projection onto C gives y | p after C | Projection onto D gives x | q after D |
|---|---|---|---|---|
| 1 | (0, 1) | (2, 0) | (−0.5, 0.5) | (0.5, 0.5) |
| 2 | (0, 0.5) | (1.5, 0) | (−0.25, 0.25) | (0.75, 0.75) |
| 3 | (0, 0.25) | (1.25, 0) | (−0.125, 0.125) | (0.875, 0.875) |
The geometric sequence here makes the limit visible. In larger problems, a stopping rule must demonstrate the same target rather than rely on a picture.
CHAPTER 5 OF 12 · WORK THE CORRECTION LEDGER
5. Why the corrections change the limit
After D projects to (−0.5,0.5), plain alternation has forgotten that C removed two units from the first coordinate. Dykstra’s p=(2,0) reintroduces that displacement before the next projection onto C. The q correction performs the analogous bookkeeping for D.
The corrections connect Dykstra’s method to coordinate optimisation in a dual problem. That perspective explains why the method is more than a cosmetic residual adjustment and why resetting corrections changes the algorithm.
CHAPTER 6 OF 12 · TRANSFER AND GENERALISE
6. Stopping evidence
Track at least three quantities: change in the primal iterate, violation of every set and change in the objective ||x−z||². Where a dual formulation is available, add a primal–dual gap or KKT residual. A tiny iterate change alone can describe slow movement or a numerical stall.
| Check | What it answers | Failure it catches |
|---|---|---|
| Maximum set violation | Is x feasible? | Apparent convergence outside a set |
| Iterate displacement norm | Has the cycle stabilised? | Persistent cycling |
| Distance to z | Is the target improving? | Feasible but non-nearest limit |
| Correction/KKT residual | Are optimality conditions credible? | Wrong update or early stop |
CHAPTER 7 OF 12 · TRANSFER AND GENERALISE
7. Changed-context transfer: an affine set
If one set is an affine subspace, alternating projections has stronger best-approximation behaviour than it has for arbitrary convex sets. In some two-set configurations, both methods therefore reach the same point. That agreement does not make corrections universally unnecessary; it reflects extra geometry.
The transfer check is to state the set class before choosing an algorithm. Compare the result with alternating projections and fixed-point limits, then perturb the affine set into a curved convex set. If plain alternation changes target while Dykstra continues to solve the projection problem, the distinction becomes operational.
CHAPTER 8 OF 12 · TRANSFER AND GENERALISE
8. More than two sets
For C₁,…,C_m, Dykstra cycles through projections and keeps one correction per set. Order can affect the path and convergence speed, even when the final best approximation is determined. Save the order, initial point, warm-start state and corrections if a run must be reproduced.
Block or parallel variants require their own guarantees. They should not be described as equivalent merely because each invokes the same individual projectors. The cyclic projections article gives the corresponding feasibility perspective.
CHAPTER 9 OF 12 · CHECK LIMITS AND IMPLEMENTATION
9. Empty intersections and nonconvex sets
The standard best-approximation-to-an-intersection statement requires a nonempty intersection of closed convex sets. If the intersection is empty, the requested projection does not exist. Iterates or cycles may still have useful interpretations in specialised formulations, but they are not the same theorem.
With nonconvex sets, projectors can be multivalued and local behaviour can depend on initialization. Correction vectors do not manufacture global convexity. State local regularity results separately and test multiple starts when using the method heuristically.
CHAPTER 10 OF 12 · CHECK LIMITS AND IMPLEMENTATION
10. Practical implementation checks
Test each individual projector on points inside, outside and on its boundary. Verify idempotence numerically: projecting an already projected point should change it only within tolerance. Use exact small examples such as the halfspaces above before scaling up.
Keep correction arrays separate for every set, apply updates in the documented order and avoid silently resetting them between cycles. Compare against a direct quadratic-program solution on small instances. That independent solution is an evidence check, not part of the production algorithm.
CHAPTER 11 OF 12 · ASK AND CONTINUE
11. Frequently asked questions
Are correction vectors error bars?
No. They are algorithmic state linked to constraint corrections. They do not quantify statistical uncertainty.
Does Dykstra always converge faster?
No. Its value is the target and guarantee under stated assumptions. Speed depends on geometry, ordering, conditioning and projector cost.
Can the method start from a warm solution?
Yes, but the primal point and compatible correction state must be handled deliberately. Reusing only the point may define a different restart.
CHAPTER 12 OF 12 · ASK AND CONTINUE
12. Sources and next reading
Boyle and Dykstra present the projection method in A Method for Finding Projections onto the Intersection of Convex Sets in Hilbert Spaces. Bregman, Censor and Reich analyse Dykstra’s algorithm as a nonlinear extension of Bregman’s optimisation method. The halfspace ledger and stopping checks above are original teaching examples.
Continue through the Topology root, cyclic projections, alternating projections and nearest-point projections and retractions. The Gold Standard of Education and How X Works connect the method to broader transfer.
Top · Contents · Previous · How X Works