Distributed Least-Squares Iterative Methods in Large-Scale Networks: A Survey

doi:10.3969/j.issn.1673-5188.2017.03.005

ZTE Communications ›› 2017, Vol. 15 ›› Issue (3): 37-45.DOI: 10.3969/j.issn.1673-5188.2017.03.005

收稿日期:2017-02-14 出版日期:2017-08-25 发布日期:2019-12-24

Distributed Least-Squares Iterative Methods in Large-Scale Networks: A Survey

SHI Lei¹, ZHAO Liang², SONG Wenzhan³, Goutham Kamath¹, WU Yuan⁴, LIU Xuefeng⁵

1. Georgia State University, Atlanta, GA 30302, USA
2. Georgia Gwinnett College, Lawrenceville, GA 30043, USA
3. University of Georgia, Athens, GA 30602, USA
4. Zhejiang University of Technology, Hangzhou 310023, China
5. The Hong Kong Polytechnic University, Hong Kong, China

Received:2017-02-14 Online:2017-08-25 Published:2019-12-24
About author:SHI Lei (lshi1@student.gsu.edu) received his B.Sc. degree in software engineering from Tongji University, China in 2007, and the M.Sc. degree in computer science from Shanghai Jiao Tong University, China in 2010. He has received his Ph.D. degree from the Department of Computer Science of Georgia State University, USA. His research interests include wireless sensor networks, in-network processing and distributed systems.|ZHAO Liang (lzhao2@ggc.edu) received his Ph.D. in computer science from Georgia State University, USA and M.S in electrical engineering from Lehigh University, USA in 2016 and 2012, respectively. He is currently an assistant professor in computer science at Georgia Gwinnett College, USA. His current research interests are in the area of optimization and data analytics for distributed systems.|SONG Wenzhan (wsong@uga.edu) is now a professor at College of Engineering, University of Georgia, USA. His research mainly focuses on sensor web, smart grid and smart environment where sensing, computing, communication and control play a critical role and need a transformative study. His research has received 6 million+ research funding from NSF, NASA, USGS, Boeing, etc. since 2005. He is an IEEE senior member.|Goutham Kamath (gkamath1@student.gsu.edu) received his B.E. degree from India in 2009 and M.S. in electrical engineering from University of Wyoming, USA in 2012. He has received his Ph.D. degree in the Department of Computer Science of Georgia State University, USA. His research interests include wireless sensor networks, distributed systems and mobile ad-hoc networks.|WU Yuan (iewuy@zjut.edu.cn) received the Ph.D. degree in electronic and computer engineering from the Hong Kong University of Science and Technology, China in 2010. He is currently an associate professor at the College of Information Engineering of Zhejiang University of Technology, China. His research interests focus on resource allocations for cognitive radio networks and smart grids.|LIU Xuefeng (csxfliu@comp.polyu.edu.hk) received the M.S. and Ph.D. degrees from Beijing Institute of Technology, China, and University of Bristol, United Kingdom, in 2003 and 2008, respectively. He is currently a research fellow at the Department of Computing of Hong Kong Polytechnic University, China. His research interests include wireless sensor networks, distributed computing, and in-network processing.
Supported by:
This work is partially supported by US NSF under Grant(No. NSF-CNS-1066391);This work is partially supported by US NSF under Grant(No. NSF-CNS-0914371);This work is partially supported by US NSF under Grant(NSF-CPS-1135814);This work is partially supported by US NSF under Grant(NSF-CDI-1125165)

摘要/Abstract

Abstract:

Many science and engineering applications involve solving a linear least-squares system formed from some field measurements. In the distributed cyber-physical systems (CPS), each sensor node used for measurement often only knows partial independent rows of the least-squares system. To solve the least-squares all the measurements must be gathered at a centralized location and then perform the computation. Such data collection and computation are inefficient because of bandwidth and time constraints and sometimes are infeasible because of data privacy concerns. Iterative methods are natural candidates for solving the aforementioned problem and there are many studies regarding this. However, most of the proposed solutions are related to centralized/parallel computations while only a few have the potential to be applied in distributed networks. Thus distributed computations are strongly preferred or demanded in many of the real world applications, e.g. smart-grid, target tracking, etc. This paper surveys the representative iterative methods for distributed least-squares in networks.

Key words: distributed computing, iterative methods, least-squares, mesh network

. [J]. ZTE Communications, 2017, 15(3): 37-45.

SHI Lei, ZHAO Liang, SONG Wenzhan, Goutham Kamath, WU Yuan, LIU Xuefeng. Distributed Least-Squares Iterative Methods in Large-Scale Networks: A Survey[J]. ZTE Communications, 2017, 15(3): 37-45.

图/表 6

Figure 1. Row partition of matrix A.

Table 1 List of notations

Notation	Definition
$A, E, L, U, Q, R$	Matrices
$x, y, a, b, r$	Vectors
$α, β, δ, λ, γ$	Scalars
$m, n$	Rows and columns of matrices
$R$	Real space
$N$	Network size
$D avg, D max$	Average and maximum node degree in the network
$u, v$	Nodes in the network
$k$	Iteration number of iterative methods

Table 1 List of notations

Notation	Definition
$A, E, L, U, Q, R$	Matrices
$x, y, a, b, r$	Vectors
$α, β, δ, λ, γ$	Scalars
$m, n$	Rows and columns of matrices
$R$	Real space
$N$	Network size
$D avg, D max$	Average and maximum node degree in the network
$u, v$	Nodes in the network
$k$	Iteration number of iterative methods

Table 2 Analysis of communication cost and time-to-completion

Algorithm	Communication cost	Time-to-completion
D-MS	$km N 2$	$km N - 1$
D-MCGLS	$k + 1 m + N N + k n + N N$	$k m + n + 2 N - 1$
D-CARP	$2 knN$	$2 n N - 1 + n log N$
D-CE	$knN$	$k n D max$
D-LMS	$kN D avg + 1$	$2 k D max$
D-RLS	$n + n 2 N - 1$	$n + n 2 N - 1$

Table 2 Analysis of communication cost and time-to-completion

Algorithm	Communication cost	Time-to-completion
D-MS	$km N 2$	$km N - 1$
D-MCGLS	$k + 1 m + N N + k n + N N$	$k m + n + 2 N - 1$
D-CARP	$2 knN$	$2 n N - 1 + n log N$
D-CE	$knN$	$k n D max$
D-LMS	$kN D avg + 1$	$2 k D max$
D-RLS	$n + n 2 N - 1$	$n + n 2 N - 1$

Figure 2. Communication pattern of D-LMS method.

Figure 3. Communication pattern of D-RLS method.

Table 3 Communication cost and convergence speed comparison

Algorithm	Communication cost	Convergence rate
DGD	$O kN$	Convergence to a neighborhood
D-NG	$O kN$	$O log k / k$ for objective function
EXTRA	$O kN$	Ergodic rate $O 1 k$ for residual
FDGD	$O kN$	$O 1 k 2$ for objective function

Table 3 Communication cost and convergence speed comparison

Algorithm	Communication cost	Convergence rate
DGD	$O kN$	Convergence to a neighborhood
D-NG	$O kN$	$O log k / k$ for objective function
EXTRA	$O kN$	Ergodic rate $O 1 k$ for residual
FDGD	$O kN$	$O 1 k 2$ for objective function

参考文献 37

[1]	A. Bjõrck , Numerical Methods for Least Squares Problems. Philadelphia, USA: SIAM, 1996.
[2]	L. Zhao, W. Z. Song, X. Ye , “Decentralized consensus in distributed networks,” International Journal of Parallel, Emergent and Distributed Systems, vol. 20, pp. 1-20, 2016. doi: 10.1080/17445760.2016.1233552. DOI URL
[3]	L. Zhao, W. Z. Song, X. Ye, Y. Gu , “Asynchronous broadcast-based decentralized learning in sensor networks,” International Journal of Parallel, Emergent and Distributed Systems, vol. 32, pp. 1-19, 2017. DOI URL
[4]	Y. Saad and H.A. van der Vorst , “Iterative solution of linear systems in the 20th century,” Journal of Computational and Applied Mathematics, vol. 123, no. 1- 2, pp. 1-33, 2000. doi: 10.1016/S0377-0427(00)00412-X. DOI URL
[5]	I. S. Duff, A. M. Erisman, J. K. Reid , Direct Methods for Sparse Matrices of Numerical Mathematics and Scientific Computation. Oxford, UK: Clarendon Press, 1989.
[6]	Y. Saad , Iterative Methods for Sparse Linear Systems, 2nd edition. Philadelphia, USA: SIAM, 2003.
[7]	C. C. Paige and M. A. Saunders , “LSQR: an algorithm for sparse linear equations and sparse least squares,” ACM Transactions on Mathematical Software, vol. 8, no. 1, pp. 43-,71, Mar. 1982. DOI URL
[8]	M. Baboulin , “Solving large dense linear least squares problems on parallel distributed computers. Application to the Earth’s gravity field computation,” Ph.D. Thesis, Toulouse Institute of Technology, Toulouse, France, 2006.
[9]	M. T. Heath, E. Ng, B. W. Peyton , “Parallel algorithms for sparse linear systems,” SIAM review, vol. 33, no. 3, pp. 420-460, 1991. DOI URL
[10]	G. Mateosand G. B. Giannakis , “Distributed recursive least-squares: stability and performance analysis,” IEEE Transactions on Signal Processing, vol. 60, no. 7, pp. 3740-3754, 2012. DOI URL
[11]	G. Mateos, I. D. Schizas, G. B. Giannakis , “Performance analysis of the consensus-based distributed LMS algorithm,” EURASIP Journal on Advances in Signal Processing, 2009. doi: 10.1155/2009/981030. DOI URL PMID
[12]	I. D. Schizas, G. B. Giannakis, S. I. Roumeliotis, A. Ribeiro , “Consensus in ad hoc WSNs with noisy links—part II: distributed estimation and smoothing of random signals,” IEEE Transactions on Signal Processing, vol. 56, no. 4, pp. 1650-1666, 2008. doi: 10.1109/TSP.2007.908943. DOI URL
[13]	I. D. Schizas, A. Ribeiro, G. B. Giannakis , “Consensus in ad hoc WSNs with noisy links—part I: distributed estimation of deterministic signals,” IEEE Transactions on Signal Processing, vol. 56, no. 1, pp. 350-364, 2008. doi: 10.1109/TSP.2007.906734. DOI URL
[14]	A. H. Sayed, C. G. Lopes , “Distributed recursive least-squares strategies over adaptive networks. signals, systems and computers,” Fortieth Asilomar Conference on Signals, Systems and Computers (ACSSC’06), Pacific Grove, USA, 2006, pp. 233-237. doi: 10.1109/ACSSC.2006.356622.
[15]	V. K. Madisetti , Digital Signal Processing Fundamentals. Boca Raton, USA: CRC Press, 2009.
[16]	D. Jakovetic, J. Xavier, J. M. F . Moura, “Fast distributed gradient methods,” IEEE Transactions on Automatic Control, vol. 59, no. 5, pp. 1131-1146, May 2014. doi: 10.1109/TAC.2014.2298712. DOI URL
[17]	I. -A. Chen , “Fast distributed first-order methods,” Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, USA, 2012.
[18]	I. Matei, J. S. Baras , “Performance evaluation of the consensus-based distributed subgradient method under random communication topologies,” IEEE Journal of Selected Topics in Signal Processing, vol. 5, no. 4, pp. 754-771, 2011. doi: 10.1109/JSTSP.2011.2120593. DOI URL
[19]	A. Nedic and A. Olshevsky , “Distributed optimization over time-varying directed graphs,” in IEEE 52nd Annual Conference on Decision and Control (CDC), Florence, Italy, 2013, pp. 6855-6860.
[20]	A. Nedic and A. Olshevsky , “stochastic gradient-push for strongly convex functions on time-varying directed graphs,” arXiv:1406. 2075,2014.
[21]	K. Yuan, Q. Ling, W. Yin, “On the convergence of decentralized gradient descent, ” arXiv: 1310. 7063, 2013.
[22]	H. Terelius, U. Topcu, R. Murray , “Decentralized multi-agent optimization via dual decomposition,” in 18th IFAC World Congress, Milano, Italy, 2011.
[23]	J. N. Tsitsiklis , “Problems in decentralized decision making and computation,” Ph.D. Thesis, MIT, Cambridge, USA, 1984.
[24]	M. Rabbat and R. Nowak , “Distributed optimization in sensor networks. Information processing in sensor networks,” in Third International Symposium on Information Processing in Sensor Networks, Berkeley, USA, 2004, pp. 20-27. doi: 10.1145/984622.984626.
[25]	G. Shi and K. H. Johansson, “Finite-time and asymptotic convergence of distributed averaging and maximizing algorithms, ” arXiv: 1205. 1733, 2012.
[26]	J. N. Tsitsiklis, D. P. Bertsekas, M. Athans , “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Transactions on Automatic Control, vol. 31, no. 9, pp. 803-812, 1986. DOI URL
[27]	L. Xiao, S. Boyd, S. Lall , “A scheme for robust distributed sensor fusion based on average consensus,” in Proc. 4th International Symposium on Information Processing in Sensor Networks, Piscataway, USA, 2005. doi: 10.1109/IPSN.2005.1440896.
[28]	M. Zargham, A. Ribeiro, A. Jadbabaie, “A distributed line search for network optimization, ” in American Control Conference ( ACC), Montreal , Canada, 2012,pages 472-477. doi: 10.1109/ACC.2012.6314986.
[29]	W. Shi, Q. Ling, G. Wu, W. Yin, “EXTRA: an exact first-order algorithm for decentralized consensus optimization, ” arXiv: 1404. 6264, 2014.
[30]	F. Iutzeler, P. Bianchi, P. Ciblat, W. Hachem. “Asynchronous distributed optimization using a randomized alternating direction method of multipliers, ”arXiv: 1303. 2837, 2013.
[31]	E. Wei and A. Ozdaglar, “On the O( 1/k) convergence of asynchronous distributed alternating direction method of multipliers, ” arXiv: 1307. 8254, 2013.
[32]	L. Zhao, W.-Z. Song, L. Shi and X. Ye , “Decentralised seismic tomography computing in cyber-physical sensor systems,” Cyber-Physical Systems, vol. 1, no. 2- 4, pp. 91-112, 2015. doi: 10.1080/23335777.2015.1062049. DOI URL
[33]	Y. Nesterov , Introductory Lectures on Convex Optimization: A Basic Course (Applied Optimization), 1st edition. New York, USA: Springer, 2004. doi: 10.1007/978-1-4419-8853-9.
[34]	S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein , “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, Jan. 2011. doi: 10.1561/2200000016. DOI URL
[35]	L. Zhao, W. Z. Song, X. Ye , “Fast decentralized gradient descent method and applications to in-situ seismic tomography,” IEEE International Conference on Big Data, Santa Clara, USA, 2015, pp. 908-917. doi: 10.1109/BigData.2015.7363839.
[36]	Y. Nesterov , “Gradient methods for minimizing composite objective function,” CORE Discussion Papers, 2007076, Catholic University of Louvain, Louvain-la-Neuve, Belgium, Sept. 2007.
[37]	S. Boyd, A. Ghosh, B. Prabhakar, D. Shah , “Randomized gossip algorithms,” IEEE Transactions on Information Theory, vol. 52, no. 6, pp. 2508-2530, Jun. 2006. doi: 10.1109/TIT.2006.874516. DOI URL

Distributed Least-Squares Iterative Methods in Large-Scale Networks: A Survey

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 37

相关文章 0

编辑推荐

Metrics