Source-linked AI summary
Network Flows that Solve Linear Equations
Guodong Shi, Brian D. O. Anderson, U. Helmke
TL;DR
The paper addresses analysis challenges in using distributed network flows to solve linear equations. It studies two flows combining consensus and projection in different ways, and proves convergence to a common solution when one exists; it also considers approximate least-squares solutions.
Problem
Analyzing these flows poses challenges not covered by prior studies, including loss of intersection boundedness and interior points for exact solutions and loss of intersection sets for least-squares solutions.
Source: §1 · p. 3, §2.4.2 · p. 7Method
The paper studies a consensus + projection flow combining consensus dynamics with projection onto affine subspaces, and a projection consensus flow using projected relative-state feedback.
Source: §2.3 · p. 6, §6 · p. 27Results
Under the stated graph conditions, both flows make node states converge asymptotically to a common solution of the linear equation when one exists.
Source: §1 · p. 3Takeaways & Limitations
When exact solutions do not exist, the consensus + projection flow can bring node states arbitrarily near a least-squares solution by increasing its gain.
Source: §6 · p. 27The projection consensus flow guarantees only local convergence, requiring initial values to lie in the affine subspaces.
Source: §3.1 · p. 8
Abstract
from arXiv · showhide
We study distributed network flows as solvers in continuous time for the linear algebraic equation $\mathbf{z}=\mathbf{H}\mathbf{y}$. Each node $i$ has access to a row $\mathbf{h}_i^{\rm T}$ of the matrix $\mathbf{H}$ and the corresponding entry $z_i$ in the vector $\mathbf{z}$. The first "consensus + projection" flow under investigation consists of two terms, one from standard consensus dynamics and the other contributing to projection onto each affine subspace specified by the $\mathbf{h}_i$ and $z_i$. The second "projection consensus" flow on the other hand simply replaces the relative state feedback in consensus dynamics with projected relative state feedback. Without dwell-time assumption on switching graphs as well as without positively lower bounded assumption on arc weights, we prove that all node states converge to a common solution of the linear algebraic equation, if there is any. The convergence is global for the "consensus + projection" flow while local for the "projection consensus" flow in the sense that the initial values must lie on the affine subspaces. If the linear equation has no exact solutions, we show that the node states can converge to a ball around the least squares solution whose radius can be made arbitrarily small through selecting a sufficiently large gain for the "consensus + projection" flow under fixed bidirectional graphs. Semi-global convergence to approximate least squares solutions is demonstrated for general switching directed graphs under suitable conditions. It is also shown that the "projection consensus" flow drives the average of the node states to the least squares solution with complete graph. Numerical examples are provided as illustrations of the established results.
1 Introduction
The paper develops two distributed continuous-time flows to solve linear equations, addressing analytical challenges not covered by earlier constrained-consensus results. It establishes convergence for exact and least-squares cases under stated graph conditions.
1 Introduction
- The consensus + projection flow combines consensus dynamics with projection onto each node’s affine constraint, while projection consensus uses projected relative-state feedback.Both flows exchange relative state information among nodes.Source: §1 · p. 2
- Earlier constrained-consensus analyses rely on intersection conditions that do not hold for the linear-equation cases studied here, creating new convergence challenges.The paper identifies missing interior points and bounded intersections, and the absence of an intersection set in the least-squares case.Source: §1 · pp. 2–3
- Without dwell-time requirements and with a positive lower bound on integrated arc weights over specified intervals, both flows converge to a common exact solution when one exists.Convergence is global for consensus + projection and local for projection consensus, which requires initial values on the affine subspaces.Source: §1 · p. 3
- With no exact solution, sufficiently high consensus gain makes consensus + projection converge to an arbitrarily small ball around the least-squares solution on fixed undirected graphs.The paper also establishes semi-global convergence to approximate least-squares solutions for switching balanced directed graphs and shows that projection consensus drives the state average to the least-squares solution on complete graphs.Source: §1 · p. 3
- The convergence analysis develops a technique for handling consensus and affine-subspace projections without intersection boundedness or interior-point assumptions.The paper states that convergence results can be sharpened to exponential convergence under suitable switching-graph conditions.Source: §1 · p. 3
2 Problem Definition
The problem is to make nodes solve a shared linear equation using local row data and communication with neighbors. The section defines the equation’s solution cases, graph model, two flows, their relation to prior work, and a row-grouping extension.
2.1 Linear Equations
- The equation z = Hy has a unique solution, infinitely many solutions, or no exact solution; its rows define affine subspaces whose intersection captures exact solutions.The no-solution case instead motivates least-squares solutions.Source: §2.1 · pp. 4–5
2.2 Network Communication Structures
- Each node knows its own equation row and right-hand-side entry, exchanges state with graph neighbors, and evolves under time-varying weighted communication.The graph model defines which nodes can send information to each node and imposes boundedness and regularity on arc weights.Source: §2.1 · p. 5, §2.2 · p. 5
2.3 Distributed Flows
- Consensus + projection adds affine-subspace projection to consensus dynamics, whereas projection consensus replaces relative-state feedback with projected relative-state feedback.A common equilibrium is consensus at a solution of the equation.Source: §2.3 · p. 6
2.4.1 Geometries
- The flows have distinct geometries: consensus + projection is a special case of optimal consensus, while projection consensus is a continuous-time analogue of projected consensus.For fixed undirected graphs, projection consensus is a gradient descent on a Riemannian manifold.Source: §2.4.1 · p. 7
2.4.2 Relation with Previous Work
- Unlike earlier constrained-consensus settings, these linear dynamics lack key intersection assumptions, and the inconsistent-equation case has no intersection set to analyze.The cited prior results rely on interior-point or bounded-intersection conditions.Source: §2.4.2 · p. 7
2.4.3 Grouping of Rows
- Grouping multiple equation rows at a node preserves affine local constraint sets and lets the stated results extend to the grouped-row setting.Finding an initial value consistent with a node’s constraint can become more burdensome when it holds many rows.Source: §2.4.3 · p. 8
3 Exact Solutions
The section establishes convergence of both distributed flows to common exact solutions under graph conditions for singleton and infinite solution sets. Their guarantees differ in initialization requirements, and convergence behavior is further characterized for selected graph settings.
3 Exact Solutions
- The section frames these results as asymptotic solutions of the equation under general conditions for Cases (I) and (II).Source: §3 · p. 8
3.1 Singleton Solution Set
- For a unique solution, consensus + projection converges for all initial values under δ-UJSC or δ-BIJC graphs, while projection consensus requires every initial state to lie in its affine subspace.The projection-consensus theorem states convergence under the same graph conditions.Source: §3.1 · p. 8
3.2 Infinite Solution Set
- For an infinite solution set, consensus + projection converges from any initial value to a solution, whereas projection consensus requires each initial state to lie in its affine subspace.Both results assume δ-UJSC or δ-BIJC graphs.Source: §3.2 · p. 9
3.3 Discussion: Convergence Speed/The Limits
- For balanced switching graphs or fixed graphs, the limits depend only on the initial value and are characterized; periodic δ-UJSC graphs yield exponential convergence, but tight rates are difficult to approximate under switching interactions.The convergence rate for time-invariant networks depends on the graph Laplacian and affine-subspace structure for consensus + projection, and is upper bounded by the Laplacian’s smallest nonzero eigenvalue for projection consensus.Source: §3.3 · pp. 9–10
3.4 Preliminaries and Auxiliary Lemmas
The section assembles projection, invariance, and derivative tools for analyzing the two network flows. Its key lemmas establish invariant sets that support the later convergence proofs.
3.4.1 Affine Spaces and Projection Operators
- Projection operators are defined as nearest-point maps onto closed convex sets and satisfy a nonexpansive distance bound.The section also recalls affine spaces and convex hulls as preliminary concepts.Source: §3.4.1 · pp. 10–11
3.4.2 Invariant Sets and Dini Derivatives
- A continuous function is non-increasing when its upper Dini derivative is nonpositive, and a lower bound then ensures a finite limit.For a maximum of differentiable functions, the derivative is computed from the indices attaining that maximum.Source: §3.4.2 · p. 11
3.4.1 Affine Spaces and Projection Operators
- For an affine hyperplane, projection has the form P_K(y) = (I − aa^T)y + ba, enabling identities used to analyze differences of projected states.Related lemmas connect projections onto nested affine spaces and their associated subspaces.Source: §3.4.3 · pp. 11–12
3.4.3 Key Lemmas
- The lemmas establish positively invariant neighborhoods around a common solution for the consensus + projection flow and, separately, the projection consensus flow.For the latter, the product of the node affine subspaces is invariant.Source: §3.4.3 · pp. 12–13
3.5 Proofs of Statements
The proofs combine invariant sets and projection arguments with consensus convergence results to establish the stated exact-solution and least-squares claims under their respective graph conditions.
3.5.1 Proof of Theorems 1 and 2
- Theorem 1 follows by adapting prior optimal-consensus results to the paper’s weight assumption, while Theorem 2 follows as a special case of Theorem 4.The authors omit the details for Theorem 1’s proof.Source: §3.5.1 · p. 13
3.5.2 Proof of Theorem 3
- For the consensus + projection flow, every initial value yields a common limiting solution under the stated graph conditions.The proof uses invariant neighborhoods and a consensus argument to show node agreement and convergence.Source: §3.5.2 · p. 14
3.5.3 Proof of Theorem 4
- For the projection consensus flow, the proof shows the residual distance to the solution set vanishes under the stated jointly connected graph conditions.The proof establishes that the limiting residual is zero for δ-UJSC and δ-BIJC graphs.Source: §3.5.3 · p. 15
3.5.4 Proof of Theorem 5
- For Theorem 5, the proof projects the dynamics onto a consensus flow; balanced graphs and fixed directed graphs use the corresponding consensus properties.For fixed directed graphs, the proof invokes the Laplacian’s left eigenvector associated with eigenvalue zero.Source: §3.5.4 · p. 16
4 Least Squares Solutions
When exact solutions do not exist, the section establishes approximate least-squares convergence for the two flows under different graph and assumption conditions. It also discusses the convergence-accuracy tradeoff and the restrictions on the switching-graph result.
4 Least Squares Solutions
- Neither flow generally converges exactly to the least-squares solution because that solution is not an equilibrium, even with a fixed interaction graph.For full column rank H, the least-squares solution is y⋆ = (H^T H)^−1 H^T z.Source: §4 · pp. 17–18
- With a fixed connected bidirectional graph, sufficiently large K makes the consensus + projection states converge to an arbitrarily small ball around the unique least-squares solution.The required K depends on the desired accuracy, not the initial values.Source: §4 · p. 17
4.1 Proof of Theorem 6
- Under fixed undirected topology, the consensus + projection flow is a gradient flow, and increasing K brings its trajectories closer to the least-squares solution.The section relates its limiting optimization problem to the unique least-squares solution when rank(H) = m.Source: §4 · pp. 17–18
4 Least Squares Solutions
- For flow (28), sufficiently large K and γ can increase the convergence rate to an ε-radius ball, but the K needed for a given accuracy depends on γ.The text notes that larger γ requires larger K for that accuracy.Source: §4 · p. 18
- For balanced δ-UJSC switching graphs, the consensus + projection flow achieves semi-global convergence to approximate least-squares solutions under assumptions [A1] and [A2].For any accuracy and initial condition in the product of affine subspaces, suitable gain and time constants exist.Source: §4 · p. 19
- The switching-graph result relies on assumptions the authors call rather strong, including a bounded, nonempty intersection condition that runs opposite to the least-squares case.The authors also describe [A2] as requiring strong symmetry among the affine spaces.Source: §4 · p. 19
- With a fixed complete graph, projection consensus drives the average node state to the unique least-squares solution, although individual nodes may converge to different limits.The theorem’s setting also requires positive, constant arc weights.Source: §4 · p. 19
5 Numerical Examples
The numerical examples illustrate the flows in exact-solution and least-squares settings. Their plotted trajectories are reported as consistent with the corresponding theoretical results.
5 Numerical Examples
- In Example 1, trajectories for both flows are plotted in Figure 2 and reported as consistent with Theorems 1 and 2.The example uses three nodes interacting in a fixed directed cycle and an equation with a unique solution.Source: §5 · pp. 25–26
- Example 2 considers a three-node directed cycle with an equation having an infinite solution set, and Figure 3 plots R_i(t) for both flows.The supplied passages identify the plotted quantities and flows but do not state a numerical outcome.Source: §5 · p. 26, Figure 3 · p. 26
- In Example 3, a four-node undirected cycle has y⋆ = (0, 0), and Figure 4 compares consensus + projection trajectories for K = 1, 5, and 100.The plotted behavior is reported as consistent with Theorem 6.Source: §5 · pp. 26–27, Figure 4 · p. 27
6 Conclusions
The conclusions present two continuous-time distributed flows for solving linear equations, with distinct mechanisms for combining consensus and projection. They summarize convergence for exact solutions and least-squares cases under specified conditions.
6 Conclusions
- The “consensus + projection” flow adds consensus dynamics to projection onto each node’s affine subspace, while “projection consensus” uses projected relative-state feedback.Both flows exchange relative state information among nodes.Source: §6 · p. 27
- For a solvable equation, both flows converge to a common solution under mild graph conditions; convergence is global for “consensus + projection” and local for “projection consensus.”For the latter, initial values must lie on the affine subspaces.Source: §6 · p. 27
- With no exact solution, “consensus + projection” can approach the least-squares solution arbitrarily closely with sufficiently large gain under fixed undirected graphs.For a complete graph, “projection consensus” drives the average node state to the least-squares solution.Source: §6 · p. 27
- The conclusions identify more precise comparisons of existing equation solvers by convergence speed, computational complexity, and communication complexity as future work.Source: §6 · p. 27
A. Proof of Lemma 7. (i)
The proof uses a contradiction argument and the graph’s time-interval connectivity to show that every node’s distance to the affine-subspace intersection tends to the same limit.
A. Proof of Lemma 7. (i)
- Assuming one node’s limiting inferior distance is below the limiting maximum leads to a contradiction.The proof supposes a node has lim inf distance l§ below h§.Source: A. Proof of Lemma 7. (i) · p. 28
- Under δ-UJSC, the proof propagates the distance estimate across successive intervals using δ-arcs and Grönwall’s inequality.It recursively applies the estimate across intervals to reach additional nodes.Source: A. Proof of Lemma 7. (i) · pp. 28–29
- The argument concludes that every node’s distance to A♯ converges to h§, establishing Lemma 7(i).Source: A. Proof of Lemma 7. (i) · p. 29
B. Proof of Lemma 7. (ii)
The proof assumes the distances converge to h§, then uses the distinct directions of the vectors h_i to show that this limit must be zero.
B. Proof of Lemma 7. (ii)
- Assuming every node’s distance to A♯ converges to h§, the proof seeks to rule out a positive value of h§.Source: B. Proof of Lemma 7. (ii) · p. 29
- The proof assumes the vectors h_1, …, h_N are distinct, since nodes with identical vectors can be combined into a cluster.It denotes the nonzero angle between distinct unit vectors by β_ij.Source: B. Proof of Lemma 7. (ii) · p. 30
- Since ε can be arbitrary, h§ = 0 is the only possibility, and this proves Lemma 7(ii).Source: B. Proof of Lemma 7. (ii) · p. 30
C. Proof of Lemma 8
The proof uses the distinct-vector assumption and a contradiction argument based on (71) to conclude that h§ equals zero.
C. Proof of Lemma 8
- The proof assumes distinct h_i vectors without loss of generality before applying (71).It notes that x_j*(t) remains in A_j* for all t ≥ 0.Source: C. Proof of Lemma 8 · p. 30
- A contradiction argument using (71) leads directly to the conclusion h§ = 0.Source: C. Proof of Lemma 8 · p. 31
- The proof’s stated conclusion is the vanishing of h§.Source: C. Proof of Lemma 8 · p. 31