A comparative numerical study of graph-based splitting algorithms for linear subspaces

This paper presents a comparative numerical study of six graph-based splitting algorithms specialized for linear subspaces, identifying optimal relaxation parameters and analyzing iteration counts to reveal performance patterns that may inform future theoretical analysis.

The Gist

Imagine you are trying to find a single, perfect spot where several different groups of people all agree to meet. In math terms, these "groups" are linear subspaces (think of them as flat sheets or lines floating in a high-dimensional space), and the "spot" is the one point where they all overlap.

This is a classic problem in optimization, and for a long time, mathematicians have used a method called the Douglas–Rachford (DR) algorithm to find this spot when there are only two groups. It's like a game of "hot and cold" where you bounce back and forth between the two groups until you land right in the middle.

But what happens when you have three, four, or even twelve groups trying to meet? The old "bounce back and forth" method breaks down. It gets lost, confused, and might never find the meeting spot.

The New Solution: A Graph-Based Team

To fix this, researchers recently invented a whole family of new algorithms called Graph-Based Splitting Methods.

Think of these algorithms as different ways to organize a team of messengers to deliver a message to the meeting spot.

• The Graph: Imagine a map connecting the different groups (nodes).
• The Strategy: Each algorithm chooses a different map (graph) to decide who talks to whom and in what order.
  • Some send messages in a line (Sequential).
  • Some let everyone talk to everyone at once (Complete).
  • Some send messages up a ladder (Parallel Up) or down a ladder (Parallel Down).
  • Some use a ring (Malitsky–Tam) or a complex web (Generalized Ryu).

The Experiment: Testing the Messengers

The authors of this paper wanted to know: Which messenger strategy is the fastest?

They set up a massive simulation with 12 different scenarios (varying the number of groups from 3 to 12). For each scenario, they tested six different "graph strategies." But there was a catch: every strategy had a "dial" called the Relaxation Parameter ($\theta$).

The Analogy of the Dial:
Imagine you are walking toward a target.

• If you take tiny steps, you get there slowly.
• If you take huge, wild leaps, you might overshoot and run in circles.
• The Relaxation Parameter is the size of your step. The researchers wanted to find the perfect step size for each strategy to get to the target as fast as possible.

What They Discovered

1. The "Goldilocks" Step Size
For most of the strategies (the Sequential, Complete, Parallel Up, and Parallel Down), the perfect step size was exactly 1.0.

• The Symmetry: They found a funny pattern: taking a step size of 0.1 was just as good as taking a step size of 1.9. It's like walking forward slowly is just as effective as walking backward quickly in this specific mathematical world.
• The Exception: The Generalized Ryu strategy loved big steps (1.9), while the Malitsky–Tam strategy was picky; it liked big steps when there were few groups, but switched to small steps (1.0) when there were many groups.

2. The Race Results
Once they tuned the dials to the perfect settings, they ran the race again. Here's how the messengers performed:

• The Slowpoke: The Sequential strategy (passing the message down a line, one by one) was the slowest. As the number of groups grew, it got slower and slower.
• The Twins: Parallel Up and Parallel Down were almost identical. Even though they looked different on paper, they moved at the exact same speed. It's like two people running up and down a hill; if the hill is symmetrical, they finish at the same time.
• The Heavy Hitters: The Complete strategy (everyone talking to everyone) and Malitsky–Tam were the winners.
  • When there were few groups, Malitsky–Tam was slightly faster.
  • But as the number of groups got large (8 or more), the Complete strategy took the crown, consistently finding the meeting spot faster than anyone else.
• The Wildcard: The Generalized Ryu strategy was unpredictable. Sometimes it was fast, but often it got confused, especially when the groups were far apart (large angles).

The "Geometry" Factor

The researchers also noticed that the speed depended on how "spread out" the groups were. They used a concept called the Friedrichs Angle (think of it as the "awkwardness" of the meeting).

• If the groups were already close to agreeing (small angle), everyone found the spot quickly.
• If the groups were very different (large angle), it took much longer.
• The Complete strategy was the most robust; it handled "awkward" meetings better than the others, following a smooth, predictable curve.

The Big Takeaway

This paper is essentially a car review for mathematical algorithms.

• Conclusion: If you have a simple problem with few groups, almost any strategy works. But if you have a complex problem with many groups, the "Complete" strategy (where everyone communicates with everyone) is the most reliable and fastest way to find the solution, provided you set the "step size" dial to 1.0.

The authors are now left with a few mysteries (like why the step size symmetry exists), which they hope to solve in future research. But for now, they've given mathematicians a clear map on how to choose the best tool for the job.

Technical Summary

Here is a detailed technical summary of the paper "A comparative numerical study of graph-based splitting algorithms for linear subspaces."

1. Problem Statement

The paper addresses the feasibility problem of finding a point $x$ that lies in the intersection of $n$ linear subspaces $U_1, \dots, U_n$ in $\mathbb{R}^p$:
$$\text{Find } x \in \bigcap_{i=1}^n U_i$$

While the Douglas–Rachford (DR) algorithm is well-established and converges for $n=2$, its direct extension to $n > 2$ subspaces generally fails to converge. Standard approaches involve reformulating the problem in a higher-dimensional product space (Pierra's reformulation), but recent developments have introduced graph-based splitting methods that avoid this dimensionality increase by utilizing specific graph structures to coordinate projections.

2. Methodology

The authors conduct a comprehensive numerical study of six specific algorithms derived from the graph-based splitting framework introduced in [7]. These algorithms differ based on the choice of two oriented graphs: a connected graph $G$ (preserving natural order) and a connected subgraph $G' \subseteq G$.

Algorithms Tested:

1. Sequential: $G$ and $G'$ are sequential paths.
2. Complete: $G$ and $G'$ are complete graphs (all nodes connected).
3. Parallel down: $G$ and $G'$ are star graphs directed toward a central node.
4. Parallel up: $G$ and $G'$ are star graphs directed away from a central node.
5. Malitsky–Tam: $G$ is a ring graph; $G'$ is a sequential path.
6. Generalized Ryu: $G$ is a complete graph; $G'$ is a parallel down graph.

Experimental Setup:

• Environment: Ambient space $\mathbb{R}^{50}$.
• Variables: Number of subspaces $n \in \{3, \dots, 12\}$.
• Data: 20 random problem instances per $n$, each tested with 10 random starting points.
• Stopping Criterion: $\|v_k - v^*\| < 10^{-6}$, where $v^*$ is the theoretical limit point derived from a closed-form expression involving the degree-balance vector and the initial points.
• Metric: Number of iterations required to converge.

3. Key Contributions

A. Determination of Optimal Relaxation Parameters ($\theta$)

The study systematically tests relaxation parameters $\theta \in \{0.1, \dots, 1.9\}$ to identify the optimal $\theta$ for each algorithm:

• Symmetry Group ($G = G'$): For Sequential, Complete, Parallel down, and Parallel up, the optimal parameter is consistently $\theta = 1$. These algorithms exhibit a symmetry where $\theta$ and $2-\theta$ yield identical performance.
• Generalized Ryu: The optimal parameter is consistently $\theta = 1.9$, showing a monotonic improvement as $\theta$ increases.
• Malitsky–Tam: The optimal parameter is dependent on $n$. For small $n$, a large $\theta$ is optimal (similar to Generalized Ryu), but as $n$ increases, the optimal $\theta$ decreases, converging toward $\theta = 1$.

B. Performance Comparison

Using the empirically derived optimal parameters, the authors compare the algorithms:

• Slowest: The Sequential algorithm is the least efficient, with performance deteriorating significantly as $n$ increases.
• Mid-Tier: Parallel up and Parallel down perform nearly identically (topologically isomorphic graphs) and are faster than Sequential but slower than the top performers.
• Generalized Ryu: Performs worse than the top tier, particularly as $n$ increases.
• Top Performers: Complete and Malitsky–Tam are the most efficient.
  • For small $n$, Malitsky–Tam is slightly faster.
  • For $n \geq 8$, the Complete algorithm becomes the most robust, maintaining stable iteration counts while Malitsky–Tam requires more iterations.

C. Relationship with Friedrichs Angle

The study investigates the relationship between the number of iterations and the Friedrichs angle (a measure of the geometric separation between subspaces) under Pierra's product space reformulation.

• A strong correlation exists: larger Friedrichs angles generally require more iterations.
• The Complete algorithm shows the most consistent curve fitting this relationship.
• The Generalized Ryu algorithm shows a "fading" curve for larger angles, indicating unstable performance in difficult geometric configurations.

4. Results Summary

Algorithm	Optimal $\theta$	Performance Trend	Notes
Sequential	1.0	Poor	Degrades rapidly as $n$ increases.
Parallel Up/Down	1.0	Moderate	Nearly identical performance; topologically isomorphic.
Generalized Ryu	1.9	Moderate/Poor	Performance worsens with $n$; unstable for large angles.
Malitsky–Tam	$n$-dependent	Good	Best for small $n$; converges to $\theta=1$ as $n \to \infty$.
Complete	1.0	Best	Most robust for large $n$; best curve fit with Friedrichs angle.

5. Significance and Open Questions

Significance:
This work provides the first extensive numerical benchmark for graph-based splitting methods applied to linear subspaces. It validates that the choice of graph structure ($G, G'$) and the relaxation parameter $\theta$ are critical for convergence speed. It suggests that the Complete graph configuration is currently the most reliable strategy for solving feasibility problems with many subspaces.

Open Questions for Future Research:
The authors highlight several theoretical gaps that their numerical findings suggest:

1. Optimality of $\theta=1$: Why is $\theta=1$ optimal when $G=G'$, and why does the symmetry $\theta \leftrightarrow 2-\theta$ hold?
2. General Expression: Can a general formula for the optimal $\theta$ be derived when $G \neq G'$?
3. Convergence Rate: Can a theoretical convergence rate be explicitly expressed in terms of the Friedrichs angle (or Friedrichs number) of the subspaces in the product space reformulation?

The paper concludes that while numerical patterns are clear, a rigorous theoretical explanation for these observed behaviors remains an open challenge.