Abstract
The Alternating Projection Method (APM) is a fundamental algorithm for finding the closest points between two sets. While its behavior is well-understood for convex sets, nonconvexity introduces significant theoretical challenges, particularly regarding convergence to a single point rather than just subsequence convergence. This paper introduces a new analysis framework leveraging the Kurdyka-Lojasiewicz (KL) property to guarantee that APM converges to a critical point for nonconvex, non-intersecting sets. We provide explicit convergence rates based on the KL exponent and validate the framework on engineering applications such as prescribed column norms and equiangular tight frames.
Introduction
Finding the shortest distance between two sets in high-dimensional space is a core problem in signal processing, compressed sensing, and communication system design. The Alternating Projection Method (APM) offers a "tuning-free" approach: starting from an initial point, one iteratively projects onto the first set, then the second, and so on.
While APM is highly effective for convex sets (e.g., spheres or cubes), many modern applications involve nonconvex sets, such as the set of matrices with a specific rank. In these nonconvex settings, the algorithm's behavior becomes unpredictable; it may cycle indefinitely or fail to converge to a stable point. Most existing convergence proofs rely on the sets being convex or having a non-empty intersection. This work addresses the more general and realistic scenario where sets are nonconvex and potentially non-intersecting.
Methodology
The authors establish a rigorous convergence framework by formalizing three geometric properties:
- The Three-Point Property: Ensures that each projection step results in a "sufficient decrease" in the distance between iterates.
- The Local Contraction Property: A local version of non-expansiveness, ensuring that projections of nearby points do not diverge.
- The Kurdyka-Lojasiewicz (KL) Property: Exploits the algebraic geometry of the objective function to show it is not "too flat" near critical points, facilitating convergence.
By combining these properties, the authors prove that the sequence of iterates is a Cauchy sequence. This is a significant advancement over previous "subsequence convergence" results, as it guarantees the algorithm settles at a single, stable critical point rather than just having a limit point it might never reach.
Convergence Rates and the KL Exponent
A key insight of this work is the relationship between the convergence speed and the "KL exponent" ($\theta$). The authors demonstrate that $\theta$ acts as a "speedometer" for the algorithm:
- Finite Convergence: Occurs when $\theta = 0$.
- Linear Convergence: Achieved when $\theta \in (0, 1/2]$, representing very fast convergence.
- Sublinear Convergence: Occurs when $\theta \in (1/2, 1)$, indicating a slower rate.
This framework is robust enough to recover known linear convergence rates for convex sets as a special case, proving its theoretical consistency.
Applications and Results
The theoretical framework was validated on two concrete engineering applications:
- Prescribed Column Norms: Designing matrices with specific column lengths for DS-CDMA communication. The authors improved upon previous results by proving full sequence convergence.
- Equiangular Tight Frames (ETFs): Designing vector sets with maximal spread for sparse representation. The paper establishes specific distance bounds under which APM is guaranteed to converge for ETFs.
Conclusion
This paper provides a significant theoretical leap by guaranteeing the convergence of APM for nonconvex, non-intersecting sets. While the framework is powerful, practical challenges remain, such as the difficulty of calculating the exact KL exponent for complex sets and the algorithm's sensitivity to initialization. Future work may extend these principles to more general alternating minimization problems, potentially impacting a broader range of machine learning loss functions.
Summary updated