Dilated POCS: Minimax Convex Optimization

1. Problem Statement

The paper addresses the limitations of Alternating Projection onto Convex Sets (POCS) when dealing with non-intersecting convex constraints.

• Standard POCS: Typically used to find a signal satisfying multiple convex constraints. If the sets intersect, the algorithm converges to a point in the intersection. If they do not intersect, standard POCS enters a "greedy limit cycle" (oscillating between the closest points of the sets) or requires Simultaneous Weighted Projections to find a compromise solution.
• The Limitation of MMSE: The standard compromise solution for non-intersecting sets is the Minimum Mean Square Error (MMSE) solution. This minimizes the sum of squared distances to all sets. However, MMSE can be "degenerate" in specific scenarios (e.g., when one constraint is an outlier far from a cluster of others), effectively ignoring the outlier to minimize the global error.
• The Goal: The authors propose an alternative optimization criterion: the Minimax solution. This approach seeks to minimize the maximum Euclidean distance to any of the convex constraints, ensuring that no single constraint is violated more than necessary. This is particularly desirable in image synthesis and tomography where worst-case error must be controlled.

2. Methodology: Dilated POCS

The core contribution is the introduction of Dilated POCS, which utilizes morphological dilation to force non-intersecting sets to overlap, thereby finding a minimax solution.

• Morphological Dilation: The authors define the dilation of a convex set $C_x$ by a kernel $C_y$ as $C_x \oplus C_y = \{ \vec{x} + \vec{y} \mid \vec{x} \in C_x, \vec{y} \in C_y \}$. In the context of signal sets, this effectively "expands" the feasible region of a constraint.
• The Algorithm:
  1. Expansion: Non-intersecting convex constraint sets are progressively dilated (expanded) by a scalar parameter $\epsilon$.
  2. Intersection Search: The dilation continues until the expanded sets intersect.
  3. Minimax Convergence: The point of intersection achieved with the smallest necessary dilation parameter $\epsilon$ corresponds to the minimax solution. At this point, the maximum distance from the solution to any original constraint set is minimized.
• Handling Weights: Unlike simultaneous weighted projections which use explicit scalar weights ($w_i$), Dilated POCS controls the importance of constraints through the degree of dilation. Tighter constraints (hard constraints) are dilated less or not at all, while softer constraints are dilated more.
• Optimization of Dilation: The optimal dilation parameter is found using interval halving. If the sets do not intersect (under-dilation), the algorithm detects a limit cycle. If they intersect significantly (over-dilation), the algorithm converges to a solution dependent on initialization. The optimal point lies between these states.
• Signal Set Erosion: The paper also suggests morphological erosion (shrinking sets) as a method to resolve cases where intersecting sets have a large common area. By eroding the sets, the solution space can be narrowed to a single unique point, removing initialization dependence.

3. Key Contributions

• Minimax Formulation for POCS: The paper establishes a theoretical framework for solving convex optimization problems using a minimax criterion rather than the traditional MMSE criterion.
• Dilated POCS Algorithm: It introduces a novel iterative procedure that uses morphological dilation to transform non-intersecting constraint problems into intersecting ones, yielding a minimax solution.
• Alternative to Weighted Projections: It offers a method to handle conflicting constraints without explicit weighting coefficients, instead using the geometry of dilation to balance constraint importance.
• Application to Tomography: The method is successfully applied to Computed Tomography (CT) reconstruction, demonstrating superior performance in handling noise and motion artifacts compared to standard methods.
• Fuzzy Set Interpretation: The authors interpret dilated POCS through the lens of fuzzy convex sets, where the dilation contours represent membership functions, and the solution is found where these fuzzy boundaries touch.

4. Results and Experiments

The authors validate the method using two primary examples:

• Low-Rank Matrix Solution (Linear Inversion):

  • A system of linear equations $\vec{y} = A\vec{x}$ with no exact solution was tested.
  • MMSE Result: The standard least-squares solution minimized the global error but was heavily influenced by the cluster of constraints, ignoring outliers.
  • Minimax Result: The Dilated POCS solution minimized the maximum error. In a specific test case, the minimax solution lay midway between a cluster of constraints and a distant outlier, whereas the MMSE solution was pulled toward the cluster.

• Computed Tomography (CT) Reconstruction:

  • Setup: Reconstruction of a Shepp-Logan phantom from noisy sinograms (projection data) using 180 angles.
  • Noise Models: Tested with Gaussian noise and Uniform noise combined with lateral motion (simulating patient movement).
  • Comparison: The results were compared against Simultaneous Algebraic Reconstruction Technique (SART) (MMSE approach) and Filtered Back-Projection (FBP).
  • Findings:
    • Noise Handling: While the MMSE (SART) solution produced a sinogram with the lowest $L_2$-norm error to the noisy data, the resulting image was less coherent.
    • Artifact Suppression: The Dilated POCS (Minimax) approach produced images with cleaner edges, sharper features, and significantly suppressed streak artifacts caused by motion.
    • Box-Dilation: The authors demonstrated that "box-dilation" (dilation in specific dimensions like lateral movement) was particularly effective for handling motion artifacts, outperforming standard ball-kernel approaches.

5. Significance

• New Imaging Modality: Dilated POCS adds a new tool to the image synthesis toolbox, specifically for over-constrained systems where a compromise (MMSE) is insufficient or undesirable.
• Robustness to Outliers: By minimizing the worst-case error, the method is more robust to outliers and extreme noise conditions compared to MMSE, which averages errors.
• Physical Constraints: The ability to treat certain constraints as "hard" (non-dilated) while relaxing others via dilation allows for a more physically intuitive modeling of real-world problems (e.g., adhering strictly to physical laws while allowing for measurement noise).
• Theoretical Bridge: The connection between morphological operations, convex optimization, and fuzzy set theory provides a rich theoretical foundation for future research in signal recovery.

In conclusion, the paper demonstrates that Dilated POCS is a powerful alternative to traditional MMSE optimization, offering a minimax solution that is particularly effective in medical imaging and signal recovery scenarios involving conflicting or noisy constraints.