Non-expansiveness of Projection

Projections Never Increase Distances

📐 Corollary 2: Non-expansiveness Property

For any x ∈ X and y ∈ ℝ^d:

||Π_X(y) - x||₂ ≤ ||y - x||₂

Meaning: Projecting y onto X brings it closer to (or at least no farther from) every point x in X.

🎯 Intuitive Understanding

What does "non-expansive" mean?

Projection is a distance-reducing (or distance-preserving) operation
The projected point Π_X(y) is never farther from any x ∈ X than the original point y
Think of projection as "pulling y into X" along the shortest path

Click to place point y outside the constraint set
Then click to place point x inside the constraint set

Constraint Set X

Point y (outside X)

Projection Π_X(y)

Point x (in X)

||y - x||₂ (before projection)

||Π_X(y) - x||₂ (after projection)

💡 Interactive Instructions:

First click: Place point y anywhere (preferably outside X)
Second click: Place point x inside the constraint set X
Observe the two distances and verify that ||Π_X(y) - x|| ≤ ||y - x||
Try "Multiple Points" to see this property holds for many x simultaneously!

🔑 Key Implication for PGD

Why this matters for optimization:

Projections never "overshoot" or increase distances. This is why PGD algorithms remain stable — the projection step can only help, never hurt, our proximity to the optimal solution.

If x* ∈ X is optimal, then after projection:

||Π_X(y) - x*||₂ ≤ ||y - x*||₂

⟹ We're guaranteed to stay close to (or get closer to) x*!

✅ Non-expansive Operations

Projection onto convex sets (this property!)
Proximal operators
Averaged operators
Property: ||T(y) - T(x)|| ≤ ||y - x||

❌ Expansive Operations

Gradient of non-smooth functions
Some nonlinear transformations
Arbitrary functions
Problem: May increase distances, causing instability

📚 Mathematical Proof Sketch

Why is projection non-expansive?

Key fact: Π_X(y) is the closest point in X to y
For any x ∈ X: By definition of projection,
||Π_X(y) - y||₂ ≤ ||x - y||₂
Triangle inequality:
||Π_X(y) - x||₂ ≤ ||Π_X(y) - y||₂ + ||y - x||₂
By acute angle property: The angle at Π_X(y) between vectors to y and to x is ≥ 90°, which gives:
||Π_X(y) - x||₂² ≤ ||y - x||₂² - ||Π_X(y) - y||₂²
Therefore: ||Π_X(y) - x||₂ ≤ ||y - x||₂ ✓

🎓 Implications for Optimization

1. Stability of PGD:

After gradient step: y = x_s - η∇f(x_s)
After projection: x_s+1 = Π_X(y)
Non-expansiveness ensures: ||x_s+1 - x*|| ≤ ||y - x*||
Projection can only improve (or maintain) distance to optimum!

2. Contraction Property:

When combined with other operators, projection helps create contractive iterations:

||x_s+1 - x*|| ≤ α||x_s - x*|| for some α < 1

3. Convergence Guarantees:

Non-expansiveness is crucial for proving convergence
Ensures iterates don't "blow up" or oscillate wildly
Provides bounded error propagation

🔬 Special Cases

Case 1: y already in X

If y ∈ X, then Π_X(y) = y, and the inequality becomes an equality: ||y - x|| ≤ ||y - x||

Case 2: x = Π_X(y)

If we choose x to be the projection itself, then: ||Π_X(y) - Π_X(y)|| = 0 ≤ ||y - Π_X(y)||

Case 3: y on the boundary

The projection is "sticky" on the boundary — distances are preserved for boundary points in certain directions.

🌟 The Big Picture

Non-expansiveness is a fundamental geometric property that:

Makes projections "well-behaved" operators
Ensures stability in iterative algorithms
Is the key reason why PGD converges reliably
Connects to fixed-point theory and operator theory

Bottom line: Projection is a friendly operation that can only make things better (or stay the same), never worse!