PaperlayerView exact revision on arXiv

Source-linked AI summary

A Distributed Algorithm for Solving a Linear Algebraic Equation

Shaoshuai Mou, Ji Liu, A. Stephen Morse

arXiv:1503.00808v1eess.SYcs.DCcs.MA

TL;DR

The paper develops a distributed approach for solving consistent linear equations across real matrix pairs. It establishes applicability to every solvable pair and shows that the method finds a solution at least exponentially fast.

  • Problem

    A distributed method is needed that applies to any pair of real matrices (A, b) for which Ax = b has at least one solution.

  • Method

    The analysis shifts each agent state x_i to an error state e_i interpreted as the error between x_i and a solution.

  • Results

    The algorithm is capable of finding a solution at least exponentially fast, with the analysis establishing contraction properties.

  • Takeaways & Limitations

    The supported conclusion is a distributed solver applicable to every solvable real matrix pair while achieving at least exponential convergence.

Abstract

from arXiv · show

A distributed algorithm is described for solving a linear algebraic equation of the form $Ax=b$ assuming the equation has at least one solution. The equation is simultaneously solved by $m$ agents assuming each agent knows only a subset of the rows of the partitioned matrix $(A,b)$, the current estimates of the equation's solution generated by its neighbors, and nothing more. Each agent recursively updates its estimate by utilizing the current estimates generated by each of its neighbors. Neighbor relations are characterized by a time-dependent directed graph $\mathbb{N}(t)$ whose vertices correspond to agents and whose arcs depict neighbor relations. It is shown that for any matrix $A$ for which the equation has a solution and any sequence of "repeatedly jointly strongly connected graphs" $\mathbb{N}(t)$, $t=1,2,\ldots$, the algorithm causes all agents' estimates to converge exponentially fast to the same solution to $Ax=b$. It is also shown that the neighbor graph sequence must actually be repeatedly jointly strongly connected if exponential convergence is to be assured. A worst case convergence rate bound is derived for the case when $Ax=b$ has a unique solution. It is demonstrated that with minor modification, the algorithm can track the solution to $Ax = b$, even if $A$ and $b$ are changing with time, provided the rates of change of $A$ and $b$ are sufficiently small. It is also shown that in the absence of communication delays, exponential convergence to a solution occurs even if the times at which each agent updates its estimates are not synchronized with the update times of its neighbors. A modification of the algorithm is outlined which enables it to obtain a least squares solution to $Ax=b$ in a distributed manner, even if $Ax=b$ does not have a solution.

I. INTRODUCTION

The paper studies distributed solution of Ax=b when agents have local equation data and communicate only with changing neighbors. It develops an algorithm supporting broad directed, time-varying networks, exponential convergence, exact solutions, and asynchronous operation.

  • Problem formulation: Agents iteratively solve Ax=b using local rows of (A,b) and state estimates received from their neighbors.The network is modeled by a time-dependent directed graph whose arcs represent information flow.
  • Problem formulation: The proposed algorithm applies to any real matrices (A,b) for which Ax=b has at least one solution, without requiring uniqueness.It is designed to let all agents reach agreement on a common solution.
  • Main contributions: Exponential convergence is established for repeatedly strongly connected time-varying neighbor graphs, and this graph condition is identified as necessary for assured exponential convergence.The paper contrasts this with prior results that established exponential convergence only for fixed complete graphs.
  • Main contributions: The method finds an exact solution in the absence of round-off and communication errors while requiring at most an n-dimensional state vector from each neighbor at each clock time.It does not require agents to know an upper bound on their neighbors’ numbers or to share a common upper bound.
  • Main contributions: The algorithm supports asynchronous operation and is motivated by networks where physical separation and communication constraints preclude centralized processing.A restricted asynchronous version ignores communication delays; delayed communication is treated elsewhere.
  • Relation to prior work: Existing distributed optimization methods may require bidirectional or fixed networks, shared time-varying step sizes, extra agent states, or provide only bounded-error solutions.The paper positions its approach as avoiding these requirements while retaining distributed computation.

III. THE ALGORITHM

The algorithm maintains each agent’s estimate within its locally feasible solution set while moving it toward its neighbors’ average estimates. This yields a totally distributed iteration without a relaxation factor.

  • Local feasibility: Each agent begins with a local solution z_i(t) to A_i x = b_i and updates within the affine set of local solutions.Using a basis K_i for ker A_i, the update has the form x_i(t + 1) = z_i(t) + K_i u_i(t).
  • Neighbor agreement: Consensus principles motivate choosing the correction so each agent’s next estimate incorporates its neighbors’ estimates.A direct average update is generally impossible because the neighbor average is not typically in the required local image.
  • Neighbor agreement: The update chooses x_i(t + 1) to satisfy A_i x_i(t + 1) = b_i while approximating the average of neighbors’ current estimates.The desired average may not lie in the image of K_i, so the correction is selected by minimizing the discrepancy in a least-squares sense.
  • Algorithm properties: The algorithm is totally distributed and does not involve a relaxation factor.Its correctness is established separately from the intuition motivating the update.
  • Analysis representation: The analysis represents the iteration through products of projected stochastic mixing matrices rather than ordinary stochastic consensus products.The relevant matrices have the form P(S ⊗ I)P, with block projections P and stochastic matrices S.

IV. ORGANIZATION

The paper develops a direct analysis of distributed linear-equation consensus, establishing convergence conditions and extending the algorithm to changing systems, asynchronous updates, and inconsistent equations.

  • Analysis: Theorem 3 provides the main technical result underlying exponential convergence of the matrix products.Its proof uses mixed-matrix norms, projection matrix polynomials, and projection block matrices.
  • Synchronous operation: Theorem 2 shows that repeatedly jointly strongly connected graph sequences are necessary under A ≠ 0 and non-redundant local projections.This condition is stronger than repeatedly joint rootedness used for unconstrained consensus.
  • Extensions: The paper also addresses slowly time-varying A and b, asynchronous updates without communication delays, and least-squares solutions when Ax = b is inconsistent.The least-squares extension addresses the stated limitation that the basic algorithm applies only when a solution exists.

A. Notation

This section defines graph composition and repeatedly jointly strongly connected sequences, then states the paper’s principal synchronous convergence results and their assumptions.

  • Notation: A graph sequence is repeatedly jointly strongly connected when every successive block of l graphs, after τ0, composes to a strongly connected graph.Across each such interval, every proper subset of agents receives information from the rest.
  • Synchronous operation: Theorem 1 states that this connectivity condition guarantees a common solution with exponential convergence for the distributed iteration.There is a positive λ < 1 such that convergence occurs as fast as λ^t approaches zero.
  • Convergence rate: When Ax = b has a unique solution and every neighbor graph is strongly connected, Corollary 1 supplies a worst-case geometric rate bound.The rate is represented by λ from equation (4).

VI. ANALYSIS

The analysis converts the distributed iteration into a projected linear recursion and proves exponential decay of its matrix products. A decomposition extends the argument from unique to non-unique solutions.

  • Error recursion: The agent states are shifted relative to any solution x* of Ax = b, producing error vectors that lie in the local projection subspaces.Because each error belongs to ker A_i, the corresponding projection leaves it unchanged.
  • Error recursion: The individual updates are combined into a block linear recursion involving the projection matrix P and stochastic mixing matrix F(t).P is block diagonal with the local projections, while F(t) ⊗ I replaces each scalar mixing entry by an identity-scaled block.
  • Contraction analysis: The mixed-matrix norm is sub-multiplicative, and finite products of projected stochastic matrices are non-expansive in this norm.These properties support contraction arguments for products associated with strongly connected graph blocks.
  • Contraction analysis: Theorem 3 shows that sufficiently long products contract exponentially when the stochastic matrices have positive diagonals and repeatedly jointly strongly connected graphs.The proof partitions the product into contiguous blocks long enough to be contractions, then applies sub-multiplicativity.
  • Multiple solutions: For multiple solutions, the proof decomposes the error into a projected component that decays exponentially and a consensus component governed by standard unconstrained consensus.The two components together make all agent errors converge to a common limit.
  • Unique solution: For a unique solution, Theorem 3 directly implies exponential convergence of all agents’ estimates to x*.The projected error product tends to zero, and the original state convergence follows from the shifted-state representation.

B. Repeatedly Jointly Strongly Connected Sequences are Necessary

The paper shows that repeatedly jointly strongly connected neighbor graphs are necessary for exponential convergence, including when Ax=b has multiple solutions.

  • Failure of connectivity: If repeated joint strong connectivity fails, arbitrarily late graph compositions can be chosen that are not strongly connected.This permits decomposition around an essential mutually reachable class and leads to a unit eigenvalue in a state-transition matrix.
  • Graph decomposition: A non-strongly-connected composition has a proper essential class with no arcs from that class to its complement across the constituent graphs.Self-arcs ensure that arcs in each constituent graph also occur in the composition, preserving the absence of such cross-class arcs.
  • Contradiction: The resulting block-triangular transition product retains an eigenvalue at 1, contradicting uniform asymptotic stability.A nonzero vector formed from the intersection of projection subspaces remains fixed by the complementary subsystem.
  • Necessity of repeated joint strong connectivity: Uniform asymptotic stability of the distributed system implies that the neighbor-graph sequence is repeatedly jointly strongly connected.The proof derives a contradiction by constructing a transition product with norm one when connectivity fails.
  • Multiple solutions: The same necessity argument extends from a unique solution to the general consistent case through an exponentially stable subsystem.When Ax=b has multiple solutions, exponential convergence of the overall system implies exponential stability of the subsystem at the origin.

C. Justification for Theorem 3

Lemma 2 establishes norm and fixed-vector properties for products of orthogonal projection matrices, providing the algebraic basis for the later contraction argument.

  • Projection properties: Orthogonal projection matrices have singular values in {0,1}, so each has norm at most 1 and finite products are non-expansive.The proof uses symmetry, eigenvalues 0 or 1, and sub-multiplicativity of the norm.
  • Fixed-vector property: If a product of projection matrices preserves a vector’s norm, every projection in the product fixes that vector.The claim is proved first for one projection and then by induction using the chain of norm inequalities.
  • Strict contraction condition: When the intersection of the projection subspaces is {0}, a product of all projections cannot have singular value 1.Any norm-preserved vector would be fixed by every projection and therefore belong to the trivial intersection.

1) Projection Matrix Polynomials:

The paper introduces projection matrix polynomials and projection block matrices, then uses nominal bounds and mixed norms to characterize non-expansiveness and contraction.

  • Projection Matrix Polynomials: Projection matrix polynomials are nonnegative linear combinations of products of orthogonal projection matrices, together with the zero matrix.The coefficients are positive real numbers, and each factor is selected from a fixed set of projections.
  • Projection Matrix Polynomials: A complete projection matrix polynomial contains a component in which every projection appears at least once.Complete polynomials have mixed products with norm strictly below their nominal bounding values, though the converse need not hold.
  • Mixed Matrix Norm: The mixed matrix norm is sub-multiplicative, and its blockwise magnitude is bounded using the infinity norm.These properties remain valid for any pair of sub-multiplicative standard matrix norms.
  • Projection Block Matrices: If a projection block matrix has a stochastic nominal bound, it is non-expansive in the mixed matrix norm.The nominal bound is formed from blockwise polynomial bounds, while stochasticity supplies the unit norm bound.
  • Projection Block Matrices: If every block row contains a complete entry, the projection block matrix is a contraction in the mixed matrix norm.Completeness makes each relevant row inequality strict, strengthening non-expansiveness to contraction.

3) Technical Results:

The technical results connect graph connectivity to contraction of distributed projection products, yielding uniform exponential convergence bounds.

  • Contraction from connectivity: For repeatedly l-connected graph sequences, products with p ≥ (m−1)^2l are contractions in the mixed matrix norm.Repeated connectivity creates complete graph compositions and complete block entries, enabling Proposition 1.
  • Route and block structure: A route through a sequence of stochastic-matrix graphs produces a corresponding product of projection matrices within a block entry.This route-to-component relationship is established inductively.
  • Contraction from connectivity: The contraction proof constructs routes that visit distinct vertex labels and thereby make every off-diagonal block entry complete.Each composed strongly connected block supplies routes between arbitrary vertex pairs.
  • Uniform contraction: For sequences in the compact connectivity class, there is a uniform λ < 1 bounding sufficiently long products.Compactness converts pointwise strict contraction into a common contraction factor.
  • Convergence rate: The resulting transition products satisfy a geometric bound based on λ and the number of complete contraction blocks.Writing t = ωlq_t + ρ_t yields λ^(ωlq_t) = λ^(t−ρ_t), which is further bounded using ρ_t < lω.

D. Convergence Rate

The section justifies a worst-case expression for λ and derives a geometric convergence-rate bound when Ax = b has a unique solution.

  • The section establishes a worst-case expression for λ used to bound the algorithm's geometric convergence rate.The argument proceeds through an inductive lemma on products of projection and flocking matrices.
  • Lemma 5 bounds nonzero block projection-matrix-polynomial coefficients from below through induction on the product length.The induction starts at s = 1 and extends from p to p + 1 using the structure of flocking matrices.
  • The mixed-matrix-norm analysis connects the nominal bound of the product to a stochastic-matrix bound.The proof uses block entries and the associated projection-product norms to establish the claimed bound.
  • Each nonzero off-diagonal block is represented as a complete projection matrix polynomial whose projection products enter the convergence bound.Completeness ensures that every projection matrix appears in the relevant product at least once.

VII. TRACKING

The paper modifies the distributed algorithm to track solutions of time-varying equations. Under sufficiently small changes in A and b, agent estimates eventually track the time-varying solution with small error.

  • A modified algorithm tracks Ax = b with small error when A and b change sufficiently slowly.The modification uses time-dependent projections and a preliminary estimate for the next local equation.
  • The tracking analysis assumes uniformly bounded A(t) and b(t), full row rank for each Ai(t), and uniformly nonsingular Ai(t)Ai(t)′.The changes satisfy A(t + 1) = A(t) + δA(t) and b(t + 1) = b(t) + δb(t), with small increments.
  • Sufficiently small δA makes the relevant time-varying matrix exponentially stable under the theorem's neighbor-graph hypotheses.The perturbation term is small when δA is small, while the projection-flocking component supplies the stability argument.
  • For sufficiently slow variations in A and b, each agent eventually tracks the time-varying solution x*(t) with small error.The conclusion follows from exponential stability of the tracking-error system.

VIII. ASYNCHRONOUS OPERATION

The algorithm can operate asynchronously by modeling unsynchronized agent events on a common time scale. Under repeated joint strong connectivity of extended neighbor graphs, all agents converge exponentially to the same solution.

  • Scope: The analysis assumes communication without delays; a delayed communication model is identified as the more realistic alternative.The paper points to separate treatment for delays rather than incorporating them into this result.
  • Asynchronous operation: Agents may have completely different event-time sequences, with no assumptions on relationships between their update times.States remain constant between successive events, and inter-event intervals are bounded above and below.
  • Asynchronous operation: Unsynchronized update times are accommodated by extending each agent's neighbor set to every event on a common time scale.At times when agent i does not update, its extended neighbor set is {i}; this converts the asynchronous rules into a synchronous model.
  • Convergence guarantee: Repeated joint strong connectivity of the extended neighbor graphs guarantees exponential convergence of all xi(tp) to the same solution.There is a λ < 1 such that convergence occurs as fast as λ^p tends to zero.
  • Time-independent graph: For a time-independent strongly connected neighbor graph, the asynchronous algorithm also converges at a geometric rate.The proof obtains repeated joint strong connectivity of the extended graph sequence from the original graph's connectivity and event-time bounds.

IX. LEAST SQUARES

The paper extends the consensus-based method to obtain distributed least squares solutions when Ax = b is inconsistent. Agents solve augmented local equations whose consensus implies the normal equations A′Ax = A′b.

  • The original algorithm applies only when Ax = b has a solution, so inconsistent systems require a different decentralized least-squares construction.Local equations Ai x = bi need not have a common solution when the global equation is inconsistent.
  • The modification augments each agent's state and assigns agents transformed local equations whose consensus is always achievable.For the three-agent construction, auxiliary vectors y and z are introduced and the agents solve coupled equations.
  • Row operations produce an equivalent augmented system with a nonsingular matrix, ensuring existence of a common augmented solution.The transformed system has the same solution set because the original and modified augmented matrices are row equivalent.
  • The common x component satisfies A′Ax = A′b and therefore solves the least squares problem.Least squares solutions exist even when Ax = b has no solution.
  • Under the same conditions as Theorem 1, the modified distributed iterations make all agent estimates converge exponentially to the desired least squares solution.The update replaces xi and Pi with augmented states and projections associated with the block rows of the transformed system.

A. Generalization

The paper generalizes its distributed construction to multiple agents and outlines a distributed least-squares algorithm, including its convergence properties and practical limitations. It also identifies extensions to time-varying systems and asynchronous updates.

  • A. Generalization: The construction generalizes from an example to any number m of agents using an augmented state and consensus formulation.Agents are organized through a chosen oriented tree, and consensus on the augmented states is combined with local equations.
  • A. Generalization: A solution of the augmented system M x̄ = q exists, and its sub-vector x solves the least-squares problem.The derivation uses the rank of the incidence matrix and the nonsingularity of the transformed block system.
  • A. Generalization: A′Ax = A′b, so the recovered vector x is a least-squares solution even when Ax = b is not directly solvable.The distributed updates use augmented states and projection matrices; exponential convergence follows under the stated theorem conditions.
  • A. Generalization: The least-squares method requires a network-wide tree-design step and gives each agent an augmented state of size nm, which scales poorly with network size.Improved scaling is described as possible when neighbor relations are time invariant and communication is bidirectional, but is deferred to future work.
  • A. Generalization: The paper establishes exponential convergence conditions, derives a worst-case geometric rate for unique solutions, and extends the algorithm to slowly time-varying data and delay-free asynchronous updates.It also sketches a distributed least-squares modification applicable when Ax = b has no solution.
  • A. Generalization: Open issues include relating the convergence parameter ρ to the conditioning of A, quantifying tracking error, and reducing transmitted information.These issues are identified as future research directions.
Loading 1503.00808v1…