PaperlayerView exact revision on arXiv

Source-linked AI summary

Diffusion Adaptation over Networks

Ali H. Sayed

arXiv:1205.4220v2cs.MAcs.LG

TL;DR

Agents with only partial access to a global cost function need decentralized cooperation to estimate shared optima. This article develops diffusion strategies and shows that they can converge to optimal solutions while supporting continuous adaptation and learning.

  • Problem

    Agents possess only partial information about a shared global cost function, motivating decentralized cooperation to reach its optimum.

  • Method

    The article develops diffusion adaptation strategies using local cost functions, neighborhood combination weights, and constant step-sizes for distributed optimization and learning.

  • Results

    Diffusion algorithms make all network estimates converge to the optimal solution, with adaptive variants converging in the mean under stated step-size and data conditions.

  • Takeaways & Limitations

    Diffusion strategies provide a theoretical framework for decentralized optimization alongside continuous adaptation, learning, and tracking over networks.

  • Takeaways & Limitations

    The presentation assumes strictly convex individual costs with a common minimizer and notes that noisy regression-data exchanges alter mean-error dynamics.

Abstract

from arXiv · show

Adaptive networks are well-suited to perform decentralized information processing and optimization tasks and to model various types of self-organized and complex behavior encountered in nature. Adaptive networks consist of a collection of agents with processing and learning abilities. The agents are linked together through a connection topology, and they cooperate with each other through local interactions to solve distributed optimization, estimation, and inference problems in real-time. The continuous diffusion of information across the network enables agents to adapt their performance in relation to streaming data and network conditions; it also results in improved adaptation and learning performance relative to non-cooperative agents. This article provides an overview of diffusion strategies for adaptation and learning over networks. The article is divided into several sections: 1. Motivation; 2. Mean-Square-Error Estimation; 3. Distributed Optimization via Diffusion Strategies; 4. Adaptive Diffusion Strategies; 5. Performance of Steepest-Descent Diffusion Strategies; 6. Performance of Adaptive Diffusion Strategies; 7. Comparing the Performance of Cooperative Strategies; 8. Selecting the Combination Weights; 9. Diffusion with Noisy Information Exchanges; 10. Extensions and Further Considerations; Appendix A: Properties of Kronecker Products; Appendix B: Graph Laplacian and Network Connectivity; Appendix C: Stochastic Matrices; Appendix D: Block Maximum Norm; Appendix E: Comparison with Consensus Strategies; References.

1 Motivation

The motivation is decentralized estimation and optimization: agents with partial information cooperate through local interactions and continuous information sharing to approach a shared global optimum. The article focuses on diffusion strategies that support cooperation, adaptation, and learning in real time over connected networks.

  • Shared estimation objective: Agents estimate a shared parameter vector w_o, defined as the minimizer of a global cost function J_glob(w).The parameter vector has size M × 1.
  • Cooperation under partial information: Partial access to the global cost function makes cooperation beneficial, enabling agents to converge toward the global optimum w_o through neighboring agents.Information propagates indirectly when neighbors cooperate with their own neighbors.
  • Decentralized processing: Decentralized processing lets spatially distributed agents pursue a global objective using only local information, in-network processing, and continuous neighbor information sharing.This process can bring agents close to the global performance level despite localized interactions.
  • Network structure: The network model mainly considers connected graphs, where every pair of nodes is linked by at least one path.Neighbor relations are symmetric, but information flow need not be: directed edge weights can differ or be zero.
  • Diffusion adaptation: The article surveys diffusion adaptation as a means for adaptive learning and cooperation over networks that respond in real time to changing data statistics.It presents illustrative examples and discusses why diffusion strategies are useful alongside alternative consensus approaches.

2 Mean-Square-Error Estimation

This section motivates distributed in-network processing through mean-square-error estimation, showing that individual nodes can recover a shared parameter vector from local statistical moments while cooperation can improve adaptation and convergence. It develops linear-model examples, including noisy AR estimation, and relates MMSE solutions to the desired parameter vector.

  • Problem Setup: Strictly convex local costs are assumed to share the same unique minimizer w_o, enabling distributed estimation of a common parameter.The presentation uses these assumptions to motivate cooperation and later distributed optimization strategies.
  • Linear Model: Noisy AR observations are represented by a linear model whose parameters are collected in w_o and whose measurement quality may vary across nodes.The noise power profile is allowed to differ spatially, so some agents collect noisier data than others.
  • Non-Cooperative Mean-Square-Error Solution: Each node can recover w_o non-cooperatively from its local moments {r_du,k, R_u,k} by solving the associated linear equations.The covariance matrix R_u,k is assumed positive-definite, ensuring invertibility.
  • Non-Cooperative Mean-Square-Error Solution: The unique minimizer of each node’s quadratic MMSE cost is w_o, establishing why mean-square-error criteria are appropriate for linear-model estimation.The gradient vanishes at the same w_o defined by the normal equations.
  • Adaptive and Cooperative Estimation: Smaller step-sizes improve MSE performance but slow convergence, while cooperative adaptive schemes can provide smaller mean-square-deviation and faster convergence than non-cooperative adaptation.Adaptive solutions can track changing statistics when the non-stationarity rate is slow enough for the filter to follow.

3 Distributed Optimization via Diffusion Strategies

The section develops diffusion strategies for distributed optimization of global costs formed from local convex costs, using a local approximation followed by node-level steepest descent. It motivates cooperation and adaptation by emphasizing unknown statistics, real-time tracking, and improved network-wide performance, while allowing flexible combination rules and constant step-sizes.

  • 3 Distributed Optimization via Diffusion Strategies: Positive-definite covariance matrices make the local and global MSE costs strictly convex with a unique minimizer wo satisfying Ru,k wo = rdu,k for every node.If the required moments were known, each node could determine wo independently by solving the normal equations.
  • 3 Distributed Optimization via Diffusion Strategies: Adaptive cooperative methods are needed because local moments may be unknown, instantaneous data support real-time tracking, and information sharing can improve performance across nodes.Without cooperation, performance is limited by the noise power at each node’s location, so some nodes may perform significantly worse than others.
  • 3 Distributed Optimization via Diffusion Strategies: Diffusion optimization approximates the global cost with a distributed local cost, then has each node optimize that alternative cost through steepest descent.The alternative cost is obtained using completion of squares or a second-order Taylor expansion and is designed for localized interactions.
  • 3 Distributed Optimization via Diffusion Strategies: Combination coefficients are designer-selected weights whose row sums define a right-stochastic matrix C and influence the performance of the resulting algorithms.The coefficients weight relationships between each node and its neighborhood.
  • 3 Distributed Optimization via Diffusion Strategies: Diffusion strategies can handle nonquadratic local costs, use constant step-sizes for continual adaptation and tracking, and adapt estimates, combination weights, or network topology.Unlike consensus-type strategies, diffusion does not require C and A to be doubly stochastic or force nodes to agree exactly on wo.

4 Adaptive Diffusion Strategies

Adaptive diffusion strategies replace unavailable true gradient information with stochastic approximations derived from streaming observations, yielding adaptive ATC and CTA implementations. These updates introduce gradient noise while retaining diffusion’s information-exchange and aggregation structure and extending to general, nonquadratic local costs.

  • Stochastic gradient approximations: Agents approximate unavailable true gradients using observations of the random processes {d_k(i), u_k,i}, since the required moments are often unavailable beforehand.The unavailable moments prevent direct evaluation of the true gradient vectors.
  • Stochastic gradient approximations: Dropping the expectation operator produces instantaneous approximations that lead to adaptive implementations of both ATC and CTA diffusion strategies.The adaptive solutions rely on stochastic approximations.
  • Gradient noise: The stochastic approximations introduce gradient noise into the recursive updates by replacing true gradients with approximate gradients.This formulation also applies to optimization problems with more general local costs that are not necessarily quadratic.
  • ATC and CTA operation: Adaptive ATC exchanges neighbors’ data and then aggregates it to update each node’s estimate, whereas adaptive CTA aggregates neighbors’ estimates before exchanging data.ATC follows information exchange followed by aggregation; CTA follows aggregation followed by information exchange.
  • Non-cooperative case: With suitable combination coefficients, adaptive ATC and CTA reduce to non-cooperative adaptive solutions in which each node runs its own individual LMS filter.The non-cooperative case is represented through the combination matrices A and C.

5 Performance of Steepest-Descent Diffusion Strategies

The section analyzes a general steepest-descent diffusion recursion that includes ATC and CTA as special cases, establishing conditions for convergence to the global optimum. It further shows that diffusion can accelerate convergence relative to non-cooperative adaptation and clarifies how the combination matrices affect stability and convergence rate.

  • General diffusion formulation: A general distributed steepest-descent diffusion recursion subsumes ATC, CTA, weight-sharing, and non-cooperative modes through different choices of A1, C, and A2.A1 = IN and A2 = A gives ATC, A1 = A and A2 = IN gives CTA, C = IN gives weight-sharing, and A1 = A2 = C = IN gives non-cooperation.
  • General diffusion formulation: The analysis assumes A1 and A2 are left stochastic and C is right stochastic, with these matrices defining neighborhood information sharing.The coefficients of A1, C, and A2 are nonnegative, and the matrices satisfy the stated stochasticity conditions.
  • Convergence: All node estimates converge to the optimal solution wo when positive step-sizes are sufficiently small under the stated covariance-dependent stability condition.Theorem 5.1 establishes convergence for the distributed steepest-descent diffusion algorithm, while the preceding result provides a sufficient bound on the step-sizes.
  • Roles of combination matrices: C influences network stability through the bound involving neighborhood covariance matrices, whereas A1 and A2 do not influence stability; all three matrices affect convergence rate.The matrices A1 and A2 influence convergence rate through their role in the diffusion dynamics, while C affects stability because the matrices Rk depend on its entries.
  • Convergence-rate performance: Diffusion error magnitudes decay more rapidly than in the non-cooperative case, and this convergence-rate improvement also holds for ATC and CTA when C = IN.For C = IN, the enhancement does not require uniform step-sizes or uniform covariance data.

6 Performance of Adaptive Diffusion Strategies … 6.4 Convergence in the Mean

The section develops mean and mean-square performance analysis for adaptive diffusion, covering cooperation modes, data and error models, and convergence toward the optimal solution. It shows that adaptive diffusion can be asymptotically unbiased and can enhance mean convergence relative to non-cooperative LMS under stated conditions.

  • 6 Performance of Adaptive Diffusion Strategies: Adaptive diffusion strategies are analyzed in mean and mean-square senses because gradient and measurement noise make their behavior random.The analysis examines convergence of weight estimates and steady-state performance under both noise sources.
  • 6 Performance of Adaptive Diffusion Strategies: Different choices of non-negative coefficients in A1, C, and A2 define cooperation modes, including adaptive ATC, CTA, weight-estimate sharing, and non-cooperative LMS.A1 = A2 = C = IN yields independent stand-alone LMS updates.
  • 6.1 Data Model: The data model assumes jointly wide-sense stationary, zero-mean processes, with temporally white and spatially independent measurement noise independent of regression data.The resulting performance expressions continue to match simulations for sufficiently small step-sizes even when regression-data independence does not hold.
  • 6.2 Performance Measures: Performance is quantified through MSE, EMSE, and MSD, with EMSE capturing the adaptive offset and MSD measuring mean-square distance from wo.The output-error variance is at least σ2_v,k and exceeds it by the a-priori error variance.
  • 6.3 Error Recursions: Adaptive diffusion error recursions include gradient noise and measurement noise, producing stochastic, time-dependent neighborhood covariance matrices Ri whose average agrees with R.The network weight-error vector evolves through a diffusion stochastic recursion, whereas non-cooperative LMS omits A1 and A2.
  • 6.4 Convergence in the Mean: Under the stated data assumptions, adaptive diffusion estimators converge in the mean to wo when the step-size satisfies the mean-stability condition, making the solution asymptotically unbiased.The mean recursion has the same form as the steepest-descent recursion after replacing the error vector by its expectation.
  • 6.4 Convergence in the Mean: Diffusion enhances mean convergence relative to non-cooperative LMS under uniform step-sizes, uniform covariance data, and also for ATC and CTA with C = IN.C determines mean stability through the neighborhood covariance matrices Rk, while A1, A2, and C jointly influence convergence rate through the error-recursion dynamics.

6.5 Mean-Square Stability · 6.6 Network Mean-Square Performance

Mean-square analysis evaluates how node error variances evolve and determines their steady-state MSD and EMSE performance. Under sufficiently small step-sizes, mean-square stability is characterized by the stability of F, while the steady-state variance relation yields network MSD and EMSE.

  • 6.5 Mean-Square Stability: Mean-square-error analysis tracks the time evolution and steady-state values of error-vector variances for each node.This analysis is needed because mean convergence alone does not exclude large fluctuations around zero.
  • 6.5 Mean-Square Stability: The steady-state values of the analyzed quantities determine node MSD and EMSE performance and convey network performance information.Under the independence assumption on regression data, the EMSE variance admits the stated weighted-square representation.
  • 6.5 Mean-Square Stability: Theorem 6.6 provides a variance relation for adaptive diffusion under independent noise and regression-data conditions, sufficiently small step-sizes, and stochastic combination matrices.The relation applies to any Hermitian nonnegative-definite weighting matrix Σ with σ = vec(Σ).
  • 6.5 Mean-Square Stability: Adaptive diffusion is mean-square stable if and only if F, or its small-step-size approximation, is stable with all eigenvalues strictly inside the unit disc.For general step-sizes, mean-square stability requires selecting step-sizes that stabilize F in addition to ensuring mean stability.
  • 6.5 Mean-Square Stability: The convergence rate is determined by [ρ(B)]2, and the approximation gives ρ(F) = [ρ(B)]2.Thus, F is stable if and only if B is stable under the stated approximation.
  • 6.6 Network Mean-Square Performance: In steady-state, Corollary 6.1 supplies a variance relation for the adaptive diffusion weight-error vector under the same setting as Theorem 6.6.The relation holds for any Hermitian nonnegative-definite weighting matrix Σ with σ = vec(Σ).
  • 6.6 Network Mean-Square Performance: Proper selection of σ, or equivalently Σ, allows the steady-state relation to evaluate network MSD and EMSE.Network MSD and EMSE are defined as averages of the corresponding individual-node quantities, with separate weighting selections producing their expressions.

6.7 Mean-Square Performance of Individual Nodes · 6.8 Uniform Data Profile · 6.9 Transient Mean-Square Performance

The paper derives individual-node mean-square performance from the network analysis, simplifies network MSD under a uniform data profile, and characterizes transient learning through a recursion. These results connect node-level measures, cooperation conditions, and mean-square stability.

  • 6.7 Mean-Square Performance of Individual Nodes: Individual-node MSD and EMSE are obtained by selecting block-diagonal weighting matrices for node k within the network performance analysis.The MSD selector uses an identity block, while the EMSE selector uses Ru,k.
  • 6.7 Mean-Square Performance of Individual Nodes: The network formulas recover non-cooperative node performance by setting A1 = A2 = C = IN.This corresponds to each node adapting individually.
  • 6.7 Mean-Square Performance of Individual Nodes: The network MSD also admits a series representation obtained by expanding (I −F)−1 as I + F + F2 + . . . when F is stable.The expansion applies when the filter is mean-square stable.
  • 6.8 Uniform Data Profile: A uniform data profile requires Ru,k = Ru for all k, µk = µ for all k, and a doubly stochastic combination matrix C.Noise variances need not be uniform, so the network SNR may still vary across nodes.
  • 6.8 Uniform Data Profile: Under these conditions, the network MSD remains represented by the series form while its factors separate step-size and covariance effects from combination matrices and noise profile.The two factor groups are {µ, Ru} and {A1, A2, C, Rv}.
  • 6.9 Transient Mean-Square Performance: The transient recursion evolves weighted squared error measures over time, and mean-square stability requires F to be stable so terms involving Fi remain bounded.The recursion relates the measures at times i and i −1.
  • 6.9 Transient Mean-Square Performance: The network learning curve is the time evolution of ζ(i), the network EMSE obtained by averaging the individual-node EMSEs at time i.Corollary 6.4 gives its recursion for i ≥0 using F, Y, and Ru.

7 Comparing the Performance of Cooperative Strategies

The section compares adaptive ATC and CTA diffusion strategies under doubly stochastic combination matrices, examines information exchange under uniform data profiles, and contrasts adaptive CTA with non-cooperative LMS. It concludes that performance depends on whether cooperation suppresses or amplifies measurement-noise effects.

  • Adaptive ATC versus CTA: For doubly stochastic A, adaptive ATC diffusion outperforms adaptive CTA diffusion.The comparison considers CTA with A1 = A, A2 = IN and ATC with A1 = IN, A2 = A.
  • Information exchange: CTA with information exchange performs better than CTA without information exchange when cooperation does not amplify measurement noise.This condition is described through the comparison of Rv and CT RvC; uniform network noise is an example.
  • Information exchange: CTA without information exchange performs better when the cooperation matrix amplifies the effect of measurement noise.The result reverses the preceding comparison under the alternative condition on {Rv, C}.
  • Information exchange: The ATC information-exchange comparison likewise depends on how Rv and CT RvC compare.The section repeats the with-versus-without exchange analysis for adaptive ATC under the corresponding strategy selections.
  • Adaptive CTA versus non-cooperative LMS: Adaptive CTA diffusion performs better than non-cooperative LMS under uniform data-profile conditions and doubly stochastic A.The comparison assumes doubly stochastic A and C and uses the CTA and LMS network-MSD expressions.

8 Selecting the Combination Weights

This section presents ways to select diffusion combination matrices, from degree-based fixed rules to adaptive weights that account for network data quality. It derives the relative-variance rule by approximately minimizing network MSD and describes an adaptive procedure for learning the required variance products.

  • Fixed combination rules: Combination matrices A1 and A2 are left-stochastic, C is right-stochastic, and the section describes constructions for left-stochastic or doubly-stochastic matrices.A right-stochastic matrix such as C can be obtained separately.
  • Fixed combination rules: Fixed combination weights depend largely on node degrees, but may degrade adaptation because they ignore differing noise profiles across the network.The weighting schemes account for connectivity while overlooking that some nodes may be noisier than others.
  • Adaptive combination weights: The relative-variance rule results from an approximate optimization that replaces direct network-MSD minimization with minimizing an upper bound’s first term.Direct minimization over left-stochastic matrices is generally non-trivial, motivating the approximation.
  • Adaptive combination weights: The relative-variance rule assigns each neighbor’s weight in proportion to the inverse of its noise-data variance product, giving larger weights to nodes with smaller variance products.The variance product scales a node’s noise variance by its step-size squared and regression-data covariance power.
  • Adaptive combination weights: Equations (402) and (406) provide an adaptive construction that lets nodes recursively estimate neighbors’ variance products from streaming data.The required variance products and regression covariance traces are not known beforehand, so nodes learn them from data realizations.

9 Diffusion with Noisy Information Exchanges

This section models additive noise on diffusion information exchanges and derives how exchange noise changes error dynamics and steady-state performance. Under unperturbed regression-data exchange, mean and mean-square convergence conditions remain unchanged, while MSD and EMSE deteriorate; noisy exchanges also motivate modified combination-weight selection.

  • Noisy exchange model: Additive noise is introduced into each diffusion exchange, with distinct source-to-destination noise signals perturbing weights, regressors, and measurements.The exchange noises are modeled as temporally white, spatially independent, zero-mean processes under stated independence assumptions.
  • Error dynamics: The weight-error recursion gains exchange-noise contributions beyond the noiseless diffusion recursion.The covariance R_i is replaced by R′, C^T s_i is replaced by z_i, and two new driving terms account for exchanged weight-estimate noises.
  • Convergence conditions: When regression data are exchanged without perturbation, exchange-link noise does not affect the conditions for mean or mean-square convergence.If regression-data exchange is noisy, the mean-error recursion changes and convergence conditions are affected by a driving nonzero bias term.
  • Mean-square stability: Mean-square stability is governed by stability of the matrix F, while the convergence rate is determined by [ρ(B)]2.The result assumes sufficiently small step-sizes so higher-order step-size terms can be ignored.
  • Selecting combination weights: The relative-variance rule incorporates exchange-noise covariances into combination-weight selection, providing an adaptive construction for the weights {aℓk}.The resulting measure explicitly accounts for the covariance terms associated with noisy exchanges.

10 Extensions and Further Considerations

Section 10 surveys extensions of diffusion strategies that add temporal processing, address distributed recursive least-squares and state-space estimation, and introduce related projection-based methods. It also summarizes performance results showing that adaptation before spatial cooperation is preferable in smoothed diffusion variants, while diffusion RLS can outperform consensus updates.

  • Extensions and Further Considerations: Diffusion strategies can be extended with temporal processing, distributed recursive least-squares, and state-space estimation capabilities.Temporal processing supplements nodes’ spatial cooperation abilities.
  • Temporal Processing and Smoothing: The ATS strategy performs adaptation, temporal smoothing, and spatial cooperation in that order.Its three operations are labeled adaptation (A), temporal filtering or smoothing (T), and spatial cooperation (S).
  • Temporal Processing and Smoothing: Among six smoothed diffusion variants, performing adaptation before spatial cooperation yields better network MSD performance.The comparison assumes doubly stochastic combination matrices and filtering coefficients that do not vary across nodes.
  • Temporal Processing and Smoothing: When P = 1, temporal processing disappears, so TAS reduces to ATC and TSA reduces to CTA; this agrees with ATC outperforming CTA.The temporal step uses current and past weight estimates rather than only current estimates and raw data.
  • Distributed RLS: Diffusion RLS shares only local data and intermediate estimates, and its implementation has enhanced performance compared with the corresponding consensus-based update.The mean-square performance and convergence of diffusion RLS are studied in the cited work.

A Appendix: Properties of Kronecker Products

This appendix defines the Kronecker product as a block matrix formed by replacing each entry of one matrix with its scaled multiple of another, and summarizes related properties. It also states that the eigenvalues of the product are all pairwise eigenvalue products.

  • Scope: The appendix collects useful Kronecker-product properties for compatible matrices, assuming required inverses exist.Table 9 is identified as a summary of well-known properties.
  • Definition: The Kronecker product E ⊗ B is an nm × nm block matrix whose blocks are eijB.Each entry of E is replaced by a scaled multiple of B.
  • Eigenvalues: The eigenvalues of E ⊗ B consist of all nm products λ_i(E)λ_j(B).The eigenvalues are formed from every eigenvalue of E paired with every eigenvalue of B.

B Appendix: Graph Laplacian and Network Connectivity

The appendix defines graph neighborhoods, degrees, Laplacian and incidence matrices, then relates Laplacian eigenvalues to network connectivity. In particular, the all-ones vector corresponds to eigenvalue zero, while nonzero algebraic connectivity characterizes connected graphs.

  • Graph definitions: A node’s neighborhood includes itself and every node with which it can share information, so its degree n_k equals the neighborhood size and satisfies n_k ≥ 1.The graph excludes self-loops from its edge count while allowing loops of length at least 2.
  • Graph matrices: The symmetric Laplacian L places n_k −1 on the diagonal, −1 for neighboring nodes, and 0 otherwise; its row entries therefore sum to zero.The diagonal term n_k −1 counts edges incident on node k, while the −1 entries identify its neighbors.
  • Graph matrices: The incidence matrix I has one column per edge, with +1 at the lower-indexed endpoint, −1 at the higher-indexed endpoint, and 0 elsewhere; L = I I^T.In the illustrated network, N = 6 and L = 8, giving matrix sizes 6 × 6 for L and 6 × 8 for I.
  • Laplacian and network connectivity: Because L1 = 0, the smallest eigenvalue is zero, and the second smallest eigenvalue θ_N−1 is the graph’s algebraic connectivity.A graph is connected if and only if its algebraic connectivity is nonzero.

C Appendix: Stochastic Matrices

This appendix defines right-, left-, and doubly stochastic matrices through unit row and column sums, then summarizes their spectral properties. Regularity strengthens the eigenvalue characterization, while doubly stochastic matrices provide additional closure, spectral, and trace properties.

  • Definitions: Right-stochastic matrices have rows summing to one, left-stochastic matrices have columns summing to one, and doubly stochastic matrices satisfy both conditions.All three matrix types are defined for N × N matrices with nonnegative entries.
  • General stochastic matrices: Every right-, left-, or doubly stochastic matrix has spectral radius 1, with all eigenvalues lying inside the unit disc.For right-stochastic matrices, A1 = 1 supplies the eigenvalue 1, while the maximum absolute row-sum norm is 1.
  • Regular stochastic matrices: For a regular right-stochastic matrix, all eigenvalues other than 1 lie strictly inside the unit circle, and the eigenvalue 1 is simple.The corresponding eigenvector can be scaled to have positive entries; for right-stochastic matrices it is the vector 1.
  • Doubly stochastic matrices: For doubly stochastic A, AAT and AT A are also doubly stochastic, and their eigenvalues are real and lie in [0, 1].The products are symmetric and nonnegative-definite, which yields real nonnegative eigenvalues bounded by their spectral radius.
  • Doubly stochastic matrices: For any N × N nonnegative-definite Hermitian matrix H, doubly stochastic A satisfies Tr(AT H A) ≤ Tr(H).The proof uses an orthogonal diagonalization with diagonal entries in [0, 1], which can only reduce the relevant nonnegative diagonal contributions.

D Appendix: Block Maximum Norm

This appendix defines the block maximum norm and develops its invariance, bounding, and stochastic-matrix properties. It also relates the norm to standard maximum-row-sum and spectral-radius quantities and derives stability conditions for transformed block-diagonal matrices.

  • Definitions: The block maximum norm applies to block vectors and induces a corresponding norm for block matrices, using the Euclidean norm on individual blocks.The vector consists of N blocks of size M × 1, while the matrix consists of N × N blocks of size M × M.
  • Unitary Invariance: The block maximum norm inherits unitary invariance for block-diagonal matrices whose blocks are unitary.Lemma D.1 states this property for all block vectors and block matrices of appropriate dimensions.
  • Relation to Maximum Absolute Row Sum: For an extended block matrix, the block maximum norm equals the originating matrix’s maximum absolute row-sum norm.The extended matrix has M × M blocks, and Lemma D.3 explicitly states ∥A∥b,∞ = ∥A∥∞.
  • Block Diagonal Hermitian Matrices: For block-diagonal Hermitian matrices, the spectral radius equals the block maximum norm and the largest spectral radius among the diagonal blocks.This result underpins stability conclusions for matrices formed by transforming the block diagonal matrix with left stochastic matrices.
  • Stability Properties: The transformed matrix A2^T D A1^T is stable whenever D is stable, and it is stable for every pair of left stochastic matrices if and only if D is stable.The appendix identifies these as the two conclusions of Corollary D.1 under the setting of Lemma D.6.

E Appendix: Comparison with Consensus Strategies

The appendix frames consensus as a distributed alternative for computing the network-wide average of node states. Unlike centralized processing, consensus uses repeated local neighbor interactions and a left-stochastic combination matrix to update node states.

  • Problem setup: Each node in a connected N-node network seeks to evaluate the average of its scalar or M × 1 vector state.The node states are denoted xk, and the desired average is denoted wo.
  • Centralized solution: A centralized solution sends every measurement to a fusion center, which computes wo and broadcasts it back to the nodes.This operation requires data transmission in both directions between nodes and the central processor.
  • Consensus Recursion: Consensus provides a distributed solution in which nodes interact locally with neighbors and converge to wo through these interactions.The strategy avoids relying on a central processor for the distributed averaging task.
  • Consensus Recursion: The consensus combination matrix A is left-stochastic because its edge weights are nonnegative and each node’s weights sum to one.The k-th column of A contains the weights associated with node k’s neighbors, and A satisfies A^T 1 = 1.
  • Consensus Recursion: Each node repeatedly combines neighbors’ previous states to produce its updated state, starting from wk,o = xk for k = 1, 2, . . ., N.The node states can be collected into a column vector, yielding an equivalent vector-form consensus iteration.

Error Recursion

Consensus iterates converge to the network average wo exactly when three stated conditions hold, with convergence governed by the second-largest eigenvalue magnitude of A. Doubly stochastic regular matrices, including those induced by suitable connected graphs and positive neighbor weights, guarantee convergence, while diffusion strategies avoid consensus networks’ sensitivity to the combination matrix for mean stability.

  • Convergence Conditions: Consensus iterates converge to the network average wo for any initial states if and only if the theorem’s three conditions are satisfied.The conditions include a doubly stochastic combination matrix A and stability of the matrix AT − 1/N 11T.
  • Rate of Convergence: The convergence rate of consensus iterates toward wo is determined by the second-largest eigenvalue magnitude |λ2(A)|.The spectrum of the error-recursion coefficient matrix determines the rate, and condition (639) ensures |λ2(A)| < 1.
  • Rate of Convergence: Any doubly stochastic and regular matrix A guarantees convergence of the consensus iterates toward wo as n →∞.For such matrices, the non-unit eigenvalues satisfy |λm(A)| < 1 for m = 2, 3, . . ., N.
  • Sufficient Condition for Regularity: A doubly stochastic A is regular when the graph is connected and combination weights are strictly positive between neighbors, including akk > 0.Under these graph conditions, the consensus iterates converge toward wo as n →∞.
  • Comparison with Diffusion Strategies: Unlike consensus, diffusion strategies use different quantities on the two sides of the iteration and are not sensitive to the combination matrix for mean stability.Diffusion mean stability follows when (INM −MRu) is stable, allowing step-sizes µk < 2/λmax(Ru,k) for ATC or CTA; consensus can be mean-unstable even when individual nodes are mean-stable.
Loading 1205.4220v2…