Distributed Recursive Least-Squares: Stability and Performance Analysis

A. Prior art on distributed adaptive estimation

• Prior approaches include I-RLS, which can attain the centralized EWLS benchmark with a Hamiltonian cycle, and diffusion RLS, which exchanges raw observations and regression vectors but suffers degraded performance with communication noise.The Hamiltonian-cycle requirement is challenging in large networks.Source: A. Prior art on distributed adaptive… · pp. 2–3

B. Contributions and paper outline

• D-RLS reformulates the exponentially weighted least-squares problem as separable constrained subproblems and uses AMA so sensors refine local estimates and exchange messages with one-hop neighbors, including over noisy links.The method supports adaptive estimation and tracking without requiring a central processor.Source: §I · p. 2, B. Contributions and paper outline · pp. 3–4

II. PROBLEM STATEMENT AND DISTRIBUTED RLS ALGORITHM

• The method is designed for ad hoc networks that may lack a Hamiltonian cycle and requires no underlying state-space model.The network model uses symmetric links, a connected graph, and single-hop communication.Source: B. Contributions and paper outline · p. 3, §II · p. 5

B. Contributions and paper outline

• The paper derives closed-form steady-state MSD and excess-MSE expressions under independence-setting assumptions and gives sufficient conditions for mean- and MSE-sense stability.The analysis uses an averaged error-form system for linearly related observations and a time-invariant parameter.Source: B. Contributions and paper outline · p. 4

II. PROBLEM STATEMENT AND DISTRIBUTED RLS ALGORITHM

• For λ < 1, exponentially discarding past data enables the EWLSE to track nonstationary processes, while WSNs also motivate low-cost estimation of stationary signals.The problem is formulated from sequentially acquired sensor regression vectors and scalar observations.Source: §I · p. 2, §II · p. 5

A. The D-RLS algorithm

• AMA minimizes the ordinary Lagrangian for local estimate updates, while its auxiliary-variable updates and dual ascent steps match those used in AD-MoM.The regularized EWLS cost is strictly convex, supporting AMA’s unique local minimizers.Source: A. The D-RLS algorithm · p. 7
• The recursions update local estimates and multipliers through neighbor communication, alongside per-sensor matrix and vector updates for the AMA-based algorithm.When links are virtually ideal, prior results allow further reductions in communication overhead and memory storage.Source: A. The D-RLS algorithm · pp. 8–9
• At each time instant, AMA-based local estimates converge to the global EWLSE as consensus iterations increase, provided the step parameter satisfies the stated upper bound.In practice, sufficiently many iterations can approximate this limit.Source: A. The D-RLS algorithm · p. 8
• Setting the consensus-iteration index equal to the observation time yields a single-time-scale D-RLS algorithm with one consensus iteration per acquired observation, suitable for nonstationary networks.The algorithm accounts for additive communication noise in exchanges of multipliers and local estimates.Source: A. The D-RLS algorithm · p. 8

B. Comparison with the AD-MoM-based D-RLS algorithm

• For λ ≠ 1, the AD-MoM regularization term prevents a rank-one update, so direct inversion is needed at each iteration.Setting the penalty coefficient to zero is not a workaround: the algorithm breaks down.Source: B. Comparison with the AD-MoM-based… · p. 9
• The AMA-based D-RLS offers an order-of-magnitude reduction in per-sensor computational complexity, while its communication overhead matches that of AD-MoM-based D-RLS.For the AD-MoM version, direct matrix inversion per iteration dominates complexity at roughly O(p^3).Source: B. Comparison with the AD-MoM-based… · pp. 9–10
• AMA convergence to the centralized EWLSE requires c ∈ (0, cu), whereas AD-MoM reaches the EWLSE for any c > 0.The AMA condition applies when many consensus iterations can be afforded.Source: B. Comparison with the AD-MoM-based… · p. 10
• AD-MoM does not require tuning the extra parameter δ and remains applicable when Φ0 = 0 because its augmented Lagrangian supplies regularization.The AMA-based comparison identifies its reduced computation as the alternative’s advantage.Source: B. Comparison with the AD-MoM-based… · p. 10

A. Scope of the analysis: assumptions and approximations

• The analysis assumes a linear observation model with a time-invariant parameter and independence-setting conditions, while allowing sensor-specific statistical profiles that remain time invariant.The assumptions delineate the scope of the stability and performance results.Source: A. Scope of the analysis: assumptions… · pp. 10–11
• The independence assumption can fail for shift-structured regressors in FIR filtering, but steady-state predictions reportedly remain accurate with time-correlated sensor data.The paper points to its numerical tests as support for this extension beyond the assumption.Source: A. Scope of the analysis: assumptions… · pp. 10–11
• The analysis approximates stochastic D-RLS recursions with an averaged system because the expected inverse-matrix updates are difficult to evaluate directly.The approximation is described as crude, with experimental evidence suggesting sufficient accuracy as the forgetting factor approaches unity.Source: A. Scope of the analysis: assumptions… · p. 11
• As λ approaches one, the exponentially weighted moving average uses an equivalent sliding window of length 1/(1 − λ), which grows with λ.This observation and the stated assumptions motivate the approximation used in the analysis.Source: A. Scope of the analysis: assumptions… · p. 11

B. Error-form D-RLS

• The global state collects local estimation errors, while aggregate noise represents observation and communication noise affecting those errors across the network.Source: B. Error-form D-RLS · p. 12
• For sufficiently large t and λ below one, the global state approximately follows the averaged error-form system, with its initial condition linked to the original state.The approximation is stated for t ≥ t0 with t0 sufficiently large.Source: B. Error-form D-RLS · p. 12
• The state covariance contains the information needed to evaluate per-sensor and networkwide performance measures.The representation is also used to investigate sufficient conditions for mean stability.Source: B. Error-form D-RLS · pp. 12–13

C. Performance Metrics

• The state covariance yields the local and networkwide MSE, EMSE, and MSD performance measures.Local MSD is the trace of the local error covariance; networkwide MSD and EMSE are averages expressed through the global error covariance.Source: C. Performance Metrics · pp. 13–14
• The steady-state MSE analysis is scoped to asymptotic behavior because the averaged-system approximation improves as λ approaches one and time grows.Source: C. Performance Metrics · p. 14

IV. STABILITY AND STEADY-STATE PERFORMANCE ANALYSIS

• Stability analysis assesses D-RLS in both the mean and MSE senses because its recursions are stochastic.Source: §IV · p. 14

A. Mean Stability

• D-RLS achieves mean consensus on the sought parameter when the stated penalty-coefficient condition holds.For λ close to one, the sufficient condition is not restrictive in practice; the bound depends on the network topology.Source: A. Mean Stability · pp. 14–15

MSE Stability and Steady-State Performance

• The covariance recursion models state dynamics driven by communication noise in local-estimate and Lagrange-multiplier transmissions, and by observation noise.The resulting global error covariance yields local and networkwide MSE, EMSE, and MSD steady-state values.Source: B. MSE Stability and Steady-State… · pp. 15, 16, 18
• If c > 0 makes Ψ stable, D-RLS is MSE stable under (a1)–(a3) and 0 ≪ λ < 1, so the global error covariance has bounded entries as t → ∞.Stability means all eigenvalues lie strictly inside the unit circle.Source: B. MSE Stability and Steady-State… · p. 17
• The sufficient condition permits MSE stability despite additive communication noise while using a constant step-size c, unlike approaches relying on diminishing step-sizes.The paper notes that diminishing step-sizes limit applicability in stationary environments.Source: B. MSE Stability and Steady-State… · p. 18
• Under the same assumptions and stability condition, D-RLS estimation errors are weakly stochastically bounded: their probability of exceeding a radius tends to zero as the radius grows.This ensures that, with overwhelming probability, local estimates remain within a finite-radius ball centered at the true parameter.Source: B. MSE Stability and Steady-State… · p. 19

Numerical Tests

• The simulated network has 15 sensors and is a connected ad hoc wireless sensor network generated from a random geometric graph on the unit square with communication range r = 0.3.The regression data is temporally correlated, so assumption (a2) does not hold.Source: §V · pp. 19–20
• The predicted steady-state EMSE and MSD values closely match empirical results despite data violating (a2) and the analysis using simplifying approximations; noisy links incur a performance penalty.The test uses λ = 0.95, c = 0.1, and δ = 100.Source: §V · p. 20
• D-RLS improves steady-state EMSE and MSD uniformly across sensors versus D-LMS, with gains up to 5 dB in estimation error and per-iteration complexity rising from O(p) to O(p^2).The comparison uses D-LMS parameters µ = 5 × 10^-3 and c = 1.Source: §V · p. 20

• D-RLS minimizes a separable reformulation of the exponentially weighted least-squares cost with alternating minimization, enabling local estimation and one-hop cooperation in networks that may lack a Hamiltonian cycle and have noisy links.The approach is designed to reduce per-sensor computational complexity while retaining RLS features such as fast convergence.Source: §VI · p. 20
• Under simplifying approximations and independence assumptions, an averaged error system yields closed-form steady-state performance expressions and sufficient mean- and MSE-stability conditions.The analysis implies estimation errors remain within a finite interval with high probability, even with additive communication noise; simulations also support its accuracy for temporally correlated data.Source: §VI · p. 21
• For λ = 1, the steady-state MSE approximations used in the paper are invalid, and formal consistency analysis remains ongoing.The authors also identify stochastic trajectory locking between D-RLS and its time-invariant averaged-system companion as future work.Source: §VI · p. 21

• Stacking the local recursions and their forcing terms gives the compact state update for y(t + 1).Source: APPENDIX · p. 22
• The transition matrix Υ contains Laplacian-based coupling blocks, with [Υ]22 = IJp, [Υ]12 = −IJp, and [Υ]11 = −[Υ]21 = −Lc.Source: APPENDIX · p. 22
• For a connected network, the Laplacian-coupled matrix has a p-dimensional nullspace associated with consensus vectors.Source: APPENDIX · p. 23
• For t ≥ t0, induction and matrix identities establish equivalence between systems (24) and (27), with the corresponding inner-state recursion.Source: APPENDIX · pp. 23–24
• Under the stated independence assumption, the noise supervector follows a first-order recursion, and cross-covariances are evaluated using independence from the prior inner state.Source: APPENDIX · p. 24
• Spatially uncorrelated communication noise gives block-diagonal covariance structure, and each sensor’s self-communication covariance block is zero.Source: APPENDIX · p. 25