Convergence Analysis of Alternating Nonconvex Projections

Zhihui Zhu, Xiao Li

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:

  1. The Three-Point Property: Ensures that each projection step results in a "sufficient decrease" in the distance between iterates.
  2. The Local Contraction Property: A local version of non-expansiveness, ensuring that projections of nearby points do not diverge.
  3. 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.
Algorithm 1: The Alternating Projection Method (APM) for two sets $\mathbb{X}$ and $\mathbb{Y}$.

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

Abstract

Alternating projection method has been used in a wide range of engineering applications since it is a gradient-free method (without requiring tuning the step size) and usually has fast speed of convergence. In this paper, we formalize two properties of proper, lower semi-continuous and semi-algebraic sets: the three-point property for all possible iterates and the local contraction property that serves as the non-expensiveness property of the projector but only for the iterates that are close enough to each other. Then by exploiting the geometric properties of the objective function around its critical point, i.e. the Kurdyka-\L{ojasiewicz} (KL) property, we establish a new convergence analysis framework to show that if one set satisfies the three-point property and the other one obeys the local contraction property, the iterates generated by alternating projection method is a convergent sequence and converges to a critical point. We complete this study by providing convergence rate which depends on the explicit expression of the KL exponent. As a byproduct, we use our new analysis framework to recover the linear convergence rate of alternating projection method onto closed convex sets. To illustrate the power of our new framework, we provide new convergence result for a class of concrete applications: alternating projection method for designing structured tight frames that are widely used in sparse representation, compressed sensing and communication.
BibTeX
@misc{zhu2018convergence,
  author = {Zhihui Zhu and Xiao Li},
  title = {{Convergence Analysis of Alternating Nonconvex Projections}},
  year = {2018},
  eprint = {1802.03889},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1802.03889},
}
Figure