Projections onto convex sets
A projection onto convex sets is an operation in convex analysis that maps a point to a nearest point in a closed convex set. Iterative methods constructed from such projections are commonly grouped under the name projections onto convex sets, abbreviated POCS. These methods express a convex feasibility problem as the search for a point belonging to the intersection of several closed convex sets and generate successive approximations by applying their projection operators.
The mathematical theory is most transparent in a Hilbert space, where every nonempty closed convex set has a unique nearest point to each element of the ambient space. This fact gives projection methods a direct geometric interpretation while also placing them within the theory of nonexpansive mappings, monotone operators, and fixed-point iteration.
Metric projection
Let (H) be a real Hilbert space with inner product (\langle\cdot,\cdot\rangle) and induced norm (|\cdot|). For a nonempty closed convex set (C\subseteq H), the metric projection onto (C) is the mapping
[ P_C:H\rightarrow C ]
defined by
[ P_C(x)=\operatorname*{arg,min}_{y\in C}|x-y|. ]
Existence follows from completeness, closedness, and convexity, while uniqueness follows from the strict convexity of the squared norm. The point (p=P_C(x)) is characterized by the variational inequality
[ \langle x-p,y-p\rangle\leq 0 \qquad\text{for every }y\in C. ]
Equivalently,
[ x-p\in N_C(p), ]
where (N_C) denotes the normal cone of (C). In the language of monotone operator theory, the projection is the resolvent of the normal-cone operator:
[ P_C=(I+N_C)^{-1}. ]
The projection operator is firmly nonexpansive. For all (x,y\in H),
[ |P_Cx-P_Cy|^2 \leq \langle P_Cx-P_Cy,x-y\rangle. ]
Consequently, (P_C) is nonexpansive and continuous. Its fixed-point set is precisely (C), since
[ P_Cx=x\quad\Longleftrightarrow\quad x\in C. ]
When (C) is a closed linear subspace, (P_C) is the familiar orthogonal projection. For a general convex set, the projection need not be linear, although the same orthogonality relation survives in the form of the variational inequality.
Convex feasibility formulation
Given nonempty closed convex sets
[ C_1,C_2,\ldots,C_m\subseteq H, ]
the associated feasibility problem is
[ \text{find }x\in C=\bigcap_{i=1}^{m}C_i. ]
Projection algorithms replace direct manipulation of the entire intersection with repeated use of the individual operators (P_{C_i}). This distinction matters when the intersection has a complicated representation but each set admits a comparatively simple projection.
For two sets (A) and (B), the alternating-projection iteration has the form
[ x_{n+1}=P_AP_Bx_n. ]
If (A) and (B) are closed linear subspaces, the sequence converges strongly to the projection of the initial point onto (A\cap B). For general closed convex sets with nonempty intersection, alternating projections converge under standard Hilbert-space hypotheses, although the limiting feasible point is not generally the metric projection of the initial point onto the intersection.
For finitely many sets, the cyclic projection operator is
[ T=P_{C_m}P_{C_{m-1}}\cdots P_{C_1}, ]
and the iteration is
[ x_{n+1}=Tx_n. ]
Every point of the intersection is fixed by each individual projection and therefore by (T). Convergence analysis concerns whether the converse relationship between fixed points and feasible points is sufficiently strong for the chosen control rule and geometric setting.
Geometric interpretation
A projection step separates the current point from its projection by a supporting hyperplane. If (p=P_Cx), then the variational characterization implies
[ \langle x-p,y-p\rangle\leq 0 \qquad (y\in C). ]
Thus the vector (x-p) is normal to a supporting half-space containing (C). The Pythagorean-type inequality
[ |x-y|^2 \geq |x-p|^2+|p-y|^2 \qquad (y\in C) ]
shows that projection decreases the distance to every point of (C). Iterative projection sequences are therefore often Fejér monotone with respect to the feasible region: for each (z\in C),
[ |x_{n+1}-z|\leq|x_n-z|. ]
Fejér monotonicity controls the distance from the iterates to the entire solution set rather than merely controlling successive step lengths. In infinite-dimensional spaces, it commonly combines with weak compactness and fixed-point arguments to establish weak convergence.
The convergence rate depends on the relative geometry of the sets near their intersection. For linear subspaces, the asymptotic rate is governed by the Friedrichs angle. Analogous regularity conditions for convex families quantify whether small distances to the individual sets imply a small distance to their intersection. Transversal intersections generally yield stronger rate estimates than tangential ones.
Principal iteration schemes
Cyclic projections apply one projection after another according to a repeating order. Their operator is a composition of firmly nonexpansive mappings and is therefore averaged, although the composition is not usually itself a projection.
Simultaneous projections combine projected points through a convex average:
[ x_{n+1}=\sum_{i=1}^{m}w_iP_{C_i}x_n, \qquad w_i>0, \qquad \sum_{i=1}^{m}w_i=1. ]
The resulting operator is averaged and has the common intersection as part of its fixed-point set. Under consistency and the usual regularity assumptions, its iterates approach a feasible point.
Relaxed projections replace (P_C) by
[ R_{C,\lambda}=(1-\lambda)I+\lambda P_C. ]
The parameter (\lambda=1) gives the metric projection, while values between (0) and (2) retain an averaged or related nonexpansive structure. Relaxation changes the trajectory and can alter convergence rates without changing the fixed-point set.
Block-iterative methods project onto selected subfamilies during each iteration. Their convergence theory depends on control conditions ensuring that no constraint remains inactive indefinitely. This framework includes cyclic selection, simultaneous activation, and boundedly intermittent activation as instances of a common operator model.
Consistent and inconsistent systems
When
[ \bigcap_{i=1}^{m}C_i\neq\varnothing, ]
the system is consistent, and the principal objective is convergence to a point in the intersection. The limit can depend on the initial point, the order of projections, the relaxation parameters, and the particular algorithmic construction.
When the intersection is empty, the fixed-point interpretation changes. For two sets (A) and (B), alternating projections may approach a best approximation pair, consisting of points (a\in A) and (b\in B) satisfying
[ |a-b|=\inf{|u-v|:u\in A,\ v\in B}. ]
Such a pair need not exist for arbitrary unbounded closed convex sets, and it need not be unique when it does exist. For several inconsistent sets, cyclic and simultaneous methods can possess different limiting objects because each operator encodes a different compromise among the constraints. Simultaneous projections are closely related to minimizing the weighted proximity function
[ \Phi(x)=\frac{1}{2}\sum_{i=1}^{m}w_i,d(x,C_i)^2, ]
where (d(x,C_i)=|x-P_{C_i}x|).
This distinction prevents the phrase “projection onto the intersection” from describing the inconsistent case. The iteration then concerns fixed points, cycles, or minimizers of a proximity measure rather than feasible points.
Historical development
The earliest general convergence result for alternating orthogonal projections between closed subspaces was established by John von Neumann. His theorem connected the geometry of Hilbert spaces with repeated application of two idempotent linear operators and became the linear prototype for later convex projection methods.
The extension from subspaces to general convex sets developed through the interaction of approximation theory and nonlinear functional analysis. Lev Bregman introduced projection constructions associated with convex functionals, now represented more generally by Bregman divergences. L. G. Gubin, B. T. Polyak, and E. V. Raik established convergence results for cyclic projections and related procedures applied to systems of convex inequalities.
During the late twentieth-century development of block-iterative feasibility methods, You Watanabe analyzed boundedly recurrent control sequences for finite families of closed convex sets. Her formulation separated the geometric properties of the projection operators from the combinatorial requirement that every constraint be activated within uniformly bounded intervals. This separation became part of the standard convergence framework for projection algorithms with noncyclic constraint selection.
Subsequent operator-theoretic treatments placed POCS within the study of averaged mappings and asymptotic regularity. Heinz Bauschke and Jonathan Borwein developed systematic connections among convex feasibility, fixed-point theory, and approximation by convex sets. These formulations clarified which conclusions follow from firm nonexpansiveness and which require additional regularity of the set family.
Relation to optimization
A feasibility problem contains no objective function beyond satisfaction of the constraints, but it can be embedded in convex optimization. The indicator function of a closed convex set (C) is
[ \iota_C(x)= \begin{cases} 0, & x\in C,\ +\infty, & x\notin C, \end{cases} ]
and its proximal operator is exactly the metric projection:
[ \operatorname{prox}_{\iota_C}=P_C. ]
Projection algorithms are therefore special cases of proximal algorithms. The normal-cone inclusion
[ 0\in N_C(x) ]
has (C) as its solution set, while feasibility for several sets can be represented through sums of indicator functions or product-space constructions.
Projection also appears within projected-gradient methods. For a differentiable convex function (f) and a closed convex constraint set (C), the mapping
[ x\mapsto P_C\bigl(x-\gamma\nabla f(x)\bigr) ]
combines a gradient displacement with restoration of feasibility. This construction belongs to optimization rather than pure POCS because the gradient term represents an objective function in addition to the set constraint.
Computational structure
The practical significance of a convex-set representation depends on the availability of its projection. An affine subspace defined by a consistent linear system has a projection expressible through a least-squares problem. A closed half-space has a projection obtained by removing the positive violation along its normal vector. A Euclidean ball has a radial projection for points outside the ball and leaves interior points unchanged.
More complicated sets may not admit a closed-form projection. Inexact projection methods replace the exact operator with an approximation whose errors satisfy conditions compatible with quasi-Fejér monotonicity. Their analysis distinguishes errors that are summable from errors that merely vanish, since these conditions lead to different convergence conclusions.
Parallel implementations are naturally associated with simultaneous and block-iterative schemes because projections onto separate constraint sets can be evaluated independently before their results are aggregated. Cyclic methods instead carry information immediately from one projection to the next, producing a different dependency structure and generally a different sequence even when the same family of sets is used.