Graph splitting methods: Fixed points and strong convergence for linear subspaces

This paper establishes a general fixed-point analysis for graph splitting methods, deriving an explicit formula for their limit points when applied to normal cones of closed linear subspaces to unify and extend existing convergence results.

The Gist

Imagine you are trying to find a single, perfect meeting spot where a group of friends, each with their own strict rules about where they can stand, can all gather at the same time.

In the world of mathematics and computer science, this is called a feasibility problem. You have several "operators" (the friends with rules), and you want to find a point $x$ that satisfies all of them simultaneously.

This paper is about Graph Splitting Methods. Think of these as a set of instructions for a group of robots trying to solve this problem together without getting confused or stuck.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: Too Many Rules

Imagine you have $n$ friends.

• Friend 1 says, "I can only stand on the blue carpet."
• Friend 2 says, "I can only stand on the red rug."
• Friend 3 says, "I can only stand on the green mat."

You want to find the spot where the blue carpet, red rug, and green mat all overlap. If you try to solve this by looking at all the rules at once, it might be too complicated. So, you use a Splitting Method: you let the friends take turns adjusting their positions based on their own rules, hoping they eventually all agree on one spot.

2. The Old Way vs. The New Way

For a long time, mathematicians had specific recipes for 2 friends (Douglas-Rachford) and 3 friends (Ryu's method). But when you have 10, 20, or 100 friends, the old recipes got messy.

• The "Lifting" Problem: To make the math work, the robots need to carry extra "backpacks" (variables) to keep track of who is talking to whom. The more friends you have, the more backpacks you need.
• The Innovation: A previous team (Bredies, Chenchene, and Naldi) invented a Graph Framework. Imagine drawing a map where dots are the friends and lines show who talks to whom. They proved that any connected map (graph) could generate a working algorithm, as long as you carry the minimum number of backpacks required.

3. What This Paper Does: The "Universal Translator"

This paper takes that Graph Framework and asks: "Can we predict exactly where the robots will stop?"

Usually, when you run these algorithms, you just watch them run and hope they stop. This paper says, "No, we can calculate the exact stopping point before we even start the robots."

They do this by focusing on a special, simple case: Linear Subspaces.

• Analogy: Instead of friends standing on weird, curved shapes, imagine the friends are standing on flat sheets of paper (planes) floating in space.
• When the rules are just "flat sheets," the math becomes much cleaner. The paper derives a formula that tells you exactly where the group will converge based on where they started and how the graph is drawn.

4. The Key Concepts Explained Simply

The "Shadow" and the "Governing" Variables

In these algorithms, there are two types of variables:

• Shadow Variables ($x$): These are the actual positions of the friends. They are the "shadows" cast by the math.
• Governing Variables ($v$): These are the "backpacks" or the internal state the robots carry to keep the conversation going.
• The Discovery: The paper shows that if you know the starting position of the backpacks ($v$), you can mathematically predict exactly where the shadows ($x$) will end up.

The "Graph" as a Roadmap

The paper uses Graph Theory (dots and lines) to describe the algorithm.

• Nodes: The friends (operators).
• Edges: The lines showing who passes information to whom.
• The Magic: The paper proves that no matter how you draw the map (as long as it's connected), there is a specific mathematical "balance" (called $\alpha$) that determines the final meeting spot.

Strong Convergence

In math, "convergence" means getting closer and closer to the answer. "Strong convergence" is like a magnet pulling the robots directly to the spot without them wobbling around forever.

• The Result: The authors prove that for these "flat sheet" problems, the robots don't just get close; they lock onto the exact answer and stop moving. They even provide the formula for that exact spot.

5. Why Does This Matter?

Imagine you are designing a self-driving car fleet or a power grid. You have thousands of components that need to agree on a setting.

• Before: You had to test each specific setup individually to see if it worked and where it would stop.
• Now: Thanks to this paper, you can look at your network map (the graph), plug in your starting numbers, and use their universal formula to instantly know the final result.

Summary

This paper is like a master key.

1. It takes a complex, new way of organizing algorithms (Graph Splitting).
2. It applies it to a common, practical scenario (finding where flat planes intersect).
3. It gives you a calculator that tells you the exact final answer for any algorithm built on this framework, unifying many different methods into one simple theory.

It turns a "guess and check" process into a precise, predictable science.

Technical Summary

Here is a detailed technical summary of the paper "Fixed points and strong convergence for linear subspaces" by Aragón-Artacho, Bauschke, Campoy, and López-Pastor.

1. Problem Statement

The paper addresses the fundamental inclusion problem in convex analysis and optimization:
$$\text{find } x \in H \text{ such that } 0 \in \sum_{i=1}^n A_i(x)$$
where $H$ is a real Hilbert space and $A_1, \dots, A_n: H \Rightarrow H$ are maximally monotone operators.

While the Proximal Point Algorithm can solve this by computing the resolvent of the sum $\sum A_i$, this is often computationally intractable. Splitting methods offer an alternative by computing the resolvents of individual operators $J_{A_i}$ separately.

The specific focus of this work is on Graph Splitting Methods (introduced by Bredies, Chenchene, and Naldi in 2024). These methods use a graph structure to define the interaction between "shadow variables" (resolvent outputs) and "governing variables" (dual variables). The paper specifically investigates the case where the operators $A_i$ are normal cones of closed linear subspaces ($A_i = N_{U_i}$), which corresponds to the Feasibility Problem (finding a point in the intersection of subspaces $\bigcap U_i$).

2. Methodology

The authors utilize a unified graph-based framework to analyze the fixed points and convergence of these splitting algorithms.

A. Graph-Theoretic Framework

• Algorithmic Graph ($G$): A directed graph with nodes $\{1, \dots, n\}$ representing the operators. An edge $(i, j)$ exists if the shadow variable $x_i$ is used as an input for the resolvent of $A_j$.
• Spanning Subgraph ($G'$): A connected subgraph of $G$ used to define the "lifting" (the number of governing variables).
• Laplacian Decomposition: The method relies on an onto decomposition $Z$ of the Laplacian matrix of $G'$ (i.e., $Lap(G') = ZZ^*$). This matrix $Z$ maps the governing variables to the space of shadow variables.

B. Operator Construction

The authors define two key operators based on the graph structure:

1. Preconditioner ($M$): Constructed using the Laplacian of $G'$ and the decomposition $Z$.
2. Composite Operator ($A$): A block operator involving the individual operators $A_i$ and the graph structure matrices.

The splitting algorithms are analyzed as Preconditioned Proximal Point Algorithms applied to these operators. The iteration is defined by:
$$u^{k+1} = (1-\theta)u^k + \theta T(u^k)$$
where $T = J_{M^{-1}A}$ is the resolvent of the preconditioned operator.

C. Specialization to Linear Subspaces

The core technical contribution lies in specializing the general monotone operator theory to the case where $A_i = N_{U_i}$. In this setting:

• The resolvent $J_{A_i}$ becomes the metric projection $P_{U_i}$.
• The fixed point sets of the splitting operators become affine subspaces (specifically, linear subspaces shifted by a vector).
• This allows for the derivation of explicit closed-form formulas for the limit points of the algorithms.

3. Key Contributions

1. Explicit Characterization of Fixed Points

The paper derives explicit expressions for the sets of fixed points ($\text{Fix } T$ and $\text{Fix } \tilde{T}$) for any valid pair of graphs $(G, G')$.

• They introduce a degree balance vector $\delta$ and a vector $\alpha = Z^\dagger \delta$ (where $Z^\dagger$ is the Moore-Penrose inverse).
• They prove that the fixed points are characterized by a linear combination of the solution space and a specific subspace $E$ derived from the graph structure.

2. Strong Convergence and Limit Points

For the case of linear subspaces, the authors prove strong convergence (not just weak) of the generated sequences. They provide exact formulas for the limit points:

• Shadow Variables ($x^k$): Converge to the projection of the initial data onto the intersection of the subspaces, weighted by the graph structure.
• Governing Variables ($v^k$): Converge to a specific point in the fixed point set determined by the initial conditions and the vector $\alpha$.

3. Unified Analysis of Existing and New Algorithms

The framework unifies the analysis of several well-known algorithms and derives new ones without needing ad-hoc proofs for each:

• Douglas–Rachford: Recovered as a specific graph case ($n=2$).
• Generalized Ryu: Analyzed for $n \ge 3$ operators.
• Malitsky–Tam: Analyzed using a ring graph.
• Parallel Up/Down & Sequential: New or less-studied configurations are analyzed.
• Complete Graph: A new splitting method is analyzed.

4. Projection Formulas

The paper provides explicit formulas for the M-projection (for the preconditioned space) and the orthogonal projection onto the fixed point sets. This is significant because it allows one to predict exactly where an algorithm will converge based on the starting point, rather than just knowing it converges.

4. Key Results

• Theorem 4.7 & 4.8: Establish strong convergence for Algorithms 1 (Preconditioned) and 2 (Reduced) when $A_i$ are normal cones.
• Explicit Limit Points:
  • For Algorithm 2, the shadow sequence converges to:
    $$\bar{x} = \frac{1}{\|\alpha\|^2} P_U \left( \sum_{j=1}^{n-1} \alpha_j v^0_j \right)$$
    where $U = \bigcap U_i$ and $\alpha$ depends on the graph topology.
  • The governing sequence converges to $\alpha \bar{x} + P_E(v^0)$.
• Vector $\alpha$ Computation: The paper provides closed-form calculations for $\alpha$ for various graph topologies (e.g., for a tree, $\alpha = \mathbf{1}$; for a complete graph, $\alpha_j$ follows a specific quadratic pattern).
• Subspace $E$: The paper characterizes the subspace $E$ (related to the kernel of the graph Laplacian) for specific graphs, showing how the graph topology dictates the "noise" or offset in the governing variables.

5. Significance

1. Unification: The paper resolves the fragmentation in the literature where algorithms like Ryu's, Malitsky-Tam's, and others were analyzed separately. It shows they are all instances of a single graph-based framework.
2. Predictability: By providing explicit formulas for limit points, the paper moves beyond qualitative convergence analysis. Practitioners can now calculate exactly what the algorithm will output given a specific initialization and graph structure.
3. Strong Convergence: In the context of linear subspaces, the paper guarantees strong convergence, which is a stronger and more desirable property than the weak convergence often found in general monotone operator settings.
4. Generalization: The methodology allows for the immediate analysis of new splitting algorithms simply by defining their graph structure, without re-deriving convergence proofs from scratch.
5. Feasibility Problems: The results are directly applicable to finding intersections of subspaces, a core problem in signal processing, image reconstruction, and machine learning.

In summary, this paper provides a rigorous, unified, and explicit mathematical foundation for a broad class of graph-based splitting algorithms, transforming them from heuristic procedures into predictable tools with known convergence behavior for linear feasibility problems.