Distributed Least-Squares Iterative Methods in Networks: A Survey
---
paper_title: Numerical Methods for Least Squares Problems

paper_content:

Preface 1. Mathematical and statistical properties of least squares solutions 2. Basic numerical methods 3. Modified least squares problems 4. Generalized least squares problems 5. Constrained least squares problems 6. Direct methods for sparse problems 7. Iterative methods for least squares problems 8. Least squares problems with special bases 9. Nonlinear least squares problems Bibliography Index.
---
paper_title: Parallel algorithms for sparse linear systems

paper_content:

This paper surveys recent progress in the development of parallel algorithms for solving sparse linear systems on computer architectures having multiple processors. Attention is focused on direct methods for solving sparse symmetric positive definite systems, specifically by Cholesky factorization. Recent progress on parallel algorithms is surveyed for all phases of the solution process, including ordering, symbolic factorization, numeric factorization, and triangular solution.
---
paper_title: Preconditioning techniques for large linear systems: A survey

paper_content:

This article surveys preconditioning techniques for the iterative solution of large linear systems, with a focus on algebraic methods suitable for general sparse matrices. Covered topics include progress in incomplete factorization methods, sparse approximate inverses, reorderings, parallelization issues, and block and multilevel extensions. Some of the challenges ahead are also discussed. An extensive bibliography completes the paper.
---
paper_title: Component-averaged row projections: A robust, block-parallel scheme for sparse linear systems

paper_content:

A new method for the parallel solution of large sparse linear systems is introduced. It proceeds by dividing the equations into blocks and operating in block-parallel iterative mode; i.e., all the blocks are processed in parallel, and the partial results are "merged" to form the next iterate. The new scheme performs Kaczmarz row projections within the blocks and merges the results by certain component-averaging operations---hence it is called component-averaged row projections, or CARP\@. The system matrix can be general, nonsymmetric, and ill-conditioned, and the division into blocks is unrestricted. For partial differential equations (PDEs)\@, if the blocks are domain-based, then only variables at the boundaries between domains are averaged, thereby minimizing data transfer between processors. CARP is very robust; its application to test cases of linear systems derived from PDEs shows that it converges in difficult cases where state-of-the-art methods fail. It is also very memory efficient and exhibits an almost linear speedup ratio, with efficiency greater than unity in some cases. A formal proof of convergence is presented: It is shown that the component-averaging operations are equivalent to row projections in a certain superspace, so the convergence properties of CARP are identical to those of Kaczmarz's algorithm in the superspace. CARP and its convergence proof also apply to the consistent convex feasibility problem.
---
paper_title: Iterative Solution of Linear Systems in the 20-th Century

paper_content:

This paper sketches the main research developments in the area of iterative methods for solving linear systems during the 20th century. Although iterative methods for solving linear systems nd their origin in the early 19th century (work by Gauss), the eld has seen an explosion of activity spurred by demand due to extraordinary technological advances in engineering and sciences. The past ve decades have been particularly rich in new developments, ending with the availability of large toolbox of specialized algorithms for solving the very large problems which arise in scientic and industrial computational models. As in any other scientic area, research in iterative methods has been a journey characterized by a chain of contributions building on each other. It is the aim of this paper not only to sketch the most signicant of these contributions during the past century, but also to relate them to one another. c 2000 Elsevier Science B.V. All rights reserved.
---
paper_title: Iterative Solution of Nonlinear Equations in Several Variables

paper_content:

Preface to the Classics Edition Preface Acknowledgments Glossary of Symbols Introduction Part I. Background Material. 1. Sample Problems 2. Linear Algebra 3. Analysis Part II. Nonconstructive Existence Theorems. 4. Gradient Mappings and Minimization 5. Contractions and the Continuation Property 6. The Degree of a Mapping Part III. Iterative Methods. 7. General Iterative Methods 8. Minimization Methods Part IV. Local Convergence. 9. Rates of Convergence-General 10. One-Step Stationary Methods 11. Multistep Methods and Additional One-Step Methods Part V. Semilocal and Global Convergence. 12. Contractions and Nonlinear Majorants 13. Convergence under Partial Ordering 14. Convergence of Minimization Methods An Annotated List of Basic Reference Books Bibliography Author Index Subject Index.
---
paper_title: A parallel multisplitting solution of the least squares problem

paper_content:

The linear least squares problem, minx kAx bk2, is solved by applying a multisplitting(MS) strategy in which the system matrix is decomposed by columns into p blocks. The b and x vectors are partitioned consistently with the matrix decomposition. The global least squares problem is then replaced by a sequence of local least squares problems which can be solved in parallel by MS. In MS the solutions to the local problems are recombined using weighting matrices to pick out the appropriate components of each subproblem solution. A new two-stage algorithm which optimizes the global update each iteration is also given. For this algorithm the updates are obtained by finding the optimal update with respect to the weights of the recombination. For the least squares problem presented, the global update optimization can also be formulated as a least squares problem of dimension p. Theoretical results are presented which prove the convergence of the iterations. Numerical results which detail the iteration behavior relative to subproblem size, convergence criteria and recombination techniques are given. The two-stage MS strategy is shown to be effective for near-separable problems. © 1998 John Wiley & Sons, Ltd.
---
paper_title: Solution of systems of linear equations by minimized iterations

paper_content:

In an earlier publication [14] a method was described which generated the eigenvalues and eigenvectors of a matrix by a successive algorithm based on minimizations by least squares. The advantage of this method consists in the fact that the successive iterations are constantly employed with maximum efficiency which guarantees fastest convergence for a given number of iterations. Moreover, with the proper care the accumulation of rounding errors can be avoided. The resulting high precision is of great advantage if the separation of closely bunched eigenvalues and eigenvectors is demanded [16]. It was pointed out in [14, p. 256] that the inversion of a matrix, and thus the solution of simultaneous systems of linear equations, is contained in the general procedure as a special case. However, in view of the great importance associated with the solution of large systems of linear equations, this problem deserved more than passing attention. It is the purpose of the present discussion to adopt the general principles of the previous investigation to the specific demands that arise if we are not interested in the complete analysis of a matrix but only in the more special problem of obtaining the solution of a given set of linear equations
---
paper_title: Methods of Conjugate Gradients for Solving Linear Systems

paper_content:

An iterative algorithm is given for solving a system Ax=k of n linear equations in n unknowns. The solution is given in n steps. It is shown that this method is a special case of a very general method which also includes Gaussian elimination. These general algorithms are essentially algorithms for finding an n dimensional ellipsoid. Connections are made with the theory of orthogonal polynomials and continued fractions.
---
paper_title: Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems

paper_content:

{The conjugate gradient method applied to the normal equations ATAx=ATb (CGLS) is often used for solving large sparse linear least squares problems. The mathematically equivalent algorithm LSQR based on the Lanczos bidiagonalization process is an often recommended alternative. In this paper, the achievable accuracy of different conjgate gradient and Lanczos methods in finite precision is studied. It is shown that an implementation of algorithm CGLS in which the residual sk=AT(b-Axk) of the normal equations is recurred will not in general achieve accurate solutions. The same conclusion holds for the method based on Lanczos bidiagonalization with starting vector ATb. For the preferred implementation of CGLS we bound the error ||r-rk|| of the computed residual rk. Numerical tests are given that confirm a conjecture of backward stability. The achievable accuracy of LSQR is shown to be similar. The analysis essentially also covers the preconditioned case.
---
paper_title: Parallel MCGLS and ICGLS methods for least squares problems on distributed memory architectures

paper_content:

In this paper we mainly study the parallelization of the CGLS method, a basic iterative method for large and sparse least squares problems in which the conjugate gradient method is applied to solve normal equations. On modern parallel architectures its parallel performance is always limited because of the global communication required for inner products, the main bottleneck of parallel performance. In this paper, we describe a modified CGLS (MCGLS) method which improve parallel performance by assembling the results of a number of inner products collectively and by creating situations where communication can be overlapped with computation. More importantly, we also propose an improved CGLS (ICGLS) method to reduce inner product's global synchronization points to half, then significantly improve the parallel performance accordingly compared with the standard CGLS method and the MCGLS method.
---
paper_title: Distributed LMS for Consensus-Based In-Network Adaptive Processing

paper_content:

Adaptive algorithms based on in-network processing of distributed observations are well-motivated for online parameter estimation and tracking of (non)stationary signals using ad hoc wireless sensor networks (WSNs). To this end, a fully distributed least mean-square (D-LMS) algorithm is developed in this paper, offering simplicity and flexibility while solely requiring single-hop communications among sensors. The resultant estimator minimizes a pertinent squared-error cost by resorting to i) the alternating-direction method of multipliers so as to gain the desired degree of parallelization and ii) a stochastic approximation iteration to cope with the time-varying statistics of the process under consideration. Information is efficiently percolated across the WSN using a subset of ldquobridgerdquo sensors, which further tradeoff communication cost for robustness to sensor failures. For a linear data model and under mild assumptions aligned with those considered in the centralized LMS, stability of the novel D-LMS algorithm is established to guarantee that local sensor estimation error norms remain bounded most of the time. Interestingly, this weak stochastic stability result extends to the pragmatic setup where intersensor communications are corrupted by additive noise. In the absence of observation and communication noise, consensus is achieved almost surely as local estimates are shown exponentially convergent to the parameter of interest with probability one. Mean-square error performance of D-LMS is also assessed. Numerical simulations: i) illustrate that D-LMS outperforms existing alternatives that rely either on information diffusion among neighboring sensors, or, local sensor filtering; ii) highlight its tracking capabilities; and iii) corroborate the stability and performance analysis results.
---
paper_title: Consensus in Ad Hoc WSNs With Noisy Links—Part I: Distributed Estimation of Deterministic Signals

paper_content:

We deal with distributed estimation of deterministic vector parameters using ad hoc wireless sensor networks (WSNs). We cast the decentralized estimation problem as the solution of multiple constrained convex optimization subproblems. Using the method of multipliers in conjunction with a block coordinate descent approach we demonstrate how the resultant algorithm can be decomposed into a set of simpler tasks suitable for distributed implementation. Different from existing alternatives, our approach does not require the centralized estimator to be expressible in a separable closed form in terms of averages, thus allowing for decentralized computation even of nonlinear estimators, including maximum likelihood estimators (MLE) in nonlinear and non-Gaussian data models. We prove that these algorithms have guaranteed convergence to the desired estimator when the sensor links are assumed ideal. Furthermore, our decentralized algorithms exhibit resilience in the presence of receiver and/or quantization noise. In particular, we introduce a decentralized scheme for least-squares and best linear unbiased estimation (BLUE) and establish its convergence in the presence of communication noise. Our algorithms also exhibit potential for higher convergence rate with respect to existing schemes. Corroborating simulations demonstrate the merits of the novel distributed estimation algorithms.
---
paper_title: Diffusion Strategies Outperform Consensus Strategies for Distributed Estimation over Adaptive Networks

paper_content:

Adaptive networks consist of a collection of nodes with adaptation and learning abilities. The nodes interact with each other on a local level and diffuse information across the network to solve estimation and inference tasks in a distributed manner. In this work, we compare the mean-square performance of two main strategies for distributed estimation over networks: consensus strategies and diffusion strategies. The analysis in the paper confirms that under constant step-sizes, diffusion strategies allow information to diffuse more thoroughly through the network and this property has a favorable effect on the evolution of the network: diffusion networks are shown to converge faster and reach lower mean-square deviation than consensus networks, and their mean-square stability is insensitive to the choice of the combination weights. In contrast, and surprisingly, it is shown that consensus networks can become unstable even if all the individual nodes are stable and able to solve the estimation task on their own. When this occurs, cooperation over the network leads to a catastrophic failure of the estimation task. This phenomenon does not occur for diffusion networks: we show that stability of the individual nodes always ensures stability of the diffusion network irrespective of the combination topology. Simulation results support the theoretical findings.
---
paper_title: Consensus in Ad Hoc WSNs With Noisy Links—Part II: Distributed Estimation and Smoothing of Random Signals

paper_content:

Distributed algorithms are developed for optimal estimation of stationary random signals and smoothing of (even nonstationary) dynamical processes based on generally correlated observations collected by ad hoc wireless sensor networks (WSNs). Maximum a posteriori (MAP) and linear minimum mean-square error (LMMSE) schemes, well appreciated for centralized estimation, are shown possible to reformulate for distributed operation through the iterative (alternating-direction) method of multipliers. Sensors communicate with single-hop neighbors their individual estimates as well as multipliers measuring how far local estimates are from consensus. When iterations reach consensus, the resultant distributed (D) MAP and LMMSE estimators converge to their centralized counterparts when inter-sensor communication links are ideal. The D-MAP estimators do not require the desired estimator to be expressible in closed form, the D-LMMSE ones are provably robust to communication or quantization noise and both are particularly simple to implement when the data model is linear-Gaussian. For decentralized tracking applications, distributed Kalman filtering and smoothing algorithms are derived for any-time MMSE optimal consensus-based state estimation using WSNs. Analysis and corroborating numerical examples demonstrate the merits of the novel distributed estimators.
---
paper_title: Distributed Recursive Least-Squares Strategies Over Adaptive Networks

paper_content:

A distributed least-squares estimation strategy is developed by appealing to collaboration techniques that exploit the space-time structure of the data, achieving an exact recursive solution that is fully distributed. Each node is allowed to communicate with its immediate neighbor in order to exploit the spatial dimension, while it evolves locally to account for the time dimension as well. In applications where communication and energy resources are scarce, an approximate RLS scheme that is also fully distributed is proposed in order to decrease the communication burden necessary to implement distributed collaborative solution. The performance of the resulting algorithm tends to its exact counterpart in the mean-square sense as the forgetting factor lambda tends to unity. A spatial-temporal energy conservation argument is used to evaluate the steady-state performance of the individual nodes across the adaptive distributed network for the low communications RLS implementation. Computer simulations illustrate the results.
---

Title: Distributed Least-Squares Iterative Methods in Networks: A Survey

Section 1: Introduction
Description 1: Introduce the significance of least-squares methods in solving large-scale linear systems and the need for distributed computation in mesh networks.

Section 2: Model and Assumption
Description 2: Discuss the network model, assumptions, and the performance criteria used for comparison and evaluation.

Section 3: Survey and Analysis
Description 3: Detail the state-of-the-art distributed least-squares iterative methods, analyzing their communication costs and time-to-completion.

Section 4: Distributed Multisplitting Method
Description 4: Describe the distributed multisplitting method and analyze its performance in terms of communication cost and time-to-completion.

Section 5: Distributed Modified Conjugate Gradient Least-Squares Method
Description 5: Discuss the distributed modified conjugate gradient least-squares method and provide an analysis of its communication cost and time-to-completion.

Section 6: Distributed Least Mean Squares Method
Description 6: Detail the distributed least mean squares method and evaluate its performance considering communication costs and time-to-completion.

Section 7: Distributed Recursive Least-Squares Method
Description 7: Explain the distributed recursive least-squares method and analyze its advantages and drawbacks in mesh networks.

Section 8: Conclusion
Description 8: Summarize the surveyed methods and their performance, offering insights on future research directions in the field.