{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:49Z","timestamp":1740145189956,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20H02385"],"award-info":[{"award-number":["JP20H02385"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The problem of sensor network localization (SNL) can be formulated as a semidefinite programming problem with a rank constraint. We propose a new method for solving such SNL problems. We factorize a semidefinite matrix with the rank constraint into a product of two matrices via the Burer\u2013Monteiro factorization. Then, we add the difference of the two matrices, with a penalty parameter, to the objective function, thereby reformulating SNL as an unconstrained multiconvex optimization problem, to which we apply the block coordinate descent method. In this paper, we also provide theoretical analyses of the proposed method and show that each subproblem that is solved sequentially by the block coordinate descent method can also be solved analytically, with the sequence generated by our proposed algorithm converging to a stationary point of the objective function. We also give a range of the penalty parameter for which the two matrices used in the factorization agree at any accumulation point. Numerical experiments confirm that the proposed method does inherit the rank constraint and that it estimates sensor positions faster than other methods without sacrificing the estimation accuracy, especially when the measured distances contain errors.<\/jats:p>","DOI":"10.1007\/s11590-021-01762-9","type":"journal-article","created":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T09:03:29Z","timestamp":1623056609000},"page":"1051-1071","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A block coordinate descent method for sensor network localization"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4871-9156","authenticated-orcid":false,"given":"Mitsuhiro","family":"Nishijima","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5479-100X","authenticated-orcid":false,"given":"Kazuhide","family":"Nakata","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,7]]},"reference":[{"key":"1762_CR1","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Goldenberg, D., Yang, Y. R.: On the computational complexity of sensor network localization. In: ALGOSENSORS 2004, Lecture Notes in Computer Science. 3121, 32\u201344 (2004)","DOI":"10.1007\/978-3-540-27820-7_5"},{"issue":"2","key":"1762_CR2","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1145\/1149283.1149286","volume":"2","author":"P Biswas","year":"2006","unstructured":"Biswas, P., Lian, T.-C., Wang, T.-C., Ye, Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sens. Netw. 2(2), 188\u2013220 (2006)","journal-title":"ACM Trans. Sens. Netw."},{"issue":"4","key":"1762_CR3","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TASE.2006.877401","volume":"3","author":"P Biswas","year":"2006","unstructured":"Biswas, P., Liang, T.-C., Toh, K.-C., Ye, Y.: Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE Trans. Autom. Sci. Eng. 3(4), 360\u2013371 (2006)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"1762_CR4","doi-asserted-by":"crossref","unstructured":"Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: Third International Symposium on Information Processing in Sensor Networks, 46\u201354 (2004)","DOI":"10.1145\/984622.984630"},{"key":"1762_CR5","first-page":"69","volume-title":"Multiscale Optim. Methods Appl.","author":"P Biswas","year":"2006","unstructured":"Biswas, P., Ye, Y.: A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. In: Hager, W.W., Huang, S.-J., Pardalos, P.M., Prokopyev, O.A. (eds.) Multiscale Optim. Methods Appl., pp. 69\u201384. Springer, Boston (2006)"},{"issue":"1","key":"1762_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2010","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2010)","journal-title":"Found. Trends Mach. Learn."},{"key":"1762_CR7","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. Ser. B 95, 329\u2013357 (2003)","journal-title":"Math. Program. Ser. B"},{"issue":"5","key":"1762_CR8","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1080\/10556788.2016.1233973","volume":"32","author":"X Chang","year":"2017","unstructured":"Chang, X., Liu, S.: A feasible method for sensor network localization. Optim. Methods Softw. 32(5), 1113\u20131131 (2017)","journal-title":"Optim. Methods Softw."},{"key":"1762_CR9","unstructured":"Chang, X., Xue, W.: Parallel implementation of feasible direction algorithm for large-scale sensor network location problems. In: IEEE 12th International Conference on Dependable, Autonomic and Secure Computing. 245\u2013251 (2014)"},{"issue":"2","key":"1762_CR10","first-page":"98","volume":"39","author":"X Chang","year":"2016","unstructured":"Chang, X., Zhu, W., Li, D.: A feasible direction algorithm for solving 3D sensor network localization. J. Beijing Univ. Posts Telecommun. 39(2), 98\u2013102 (2016)","journal-title":"J. Beijing Univ. Posts Telecommun."},{"issue":"4","key":"1762_CR11","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1137\/S105262349630009X","volume":"8","author":"D Goldfarb","year":"1998","unstructured":"Goldfarb, D., Scheinberg, K.: Interior point trajectories in semidefinite programming. SIAM J. Optim. 8(4), 871\u2013886 (1998)","journal-title":"SIAM J. Optim."},{"key":"1762_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00186-007-0161-1","volume":"66","author":"J Gorski","year":"2007","unstructured":"Gorski, J., Pfeuffer, F., Klamroth, K.: Biconvex sets and optimization with biconvex functions: a survey and extensions. Math. Methods Oper. Res. 66, 373\u2013407 (2007)","journal-title":"Math. Methods Oper. Res."},{"issue":"1","key":"1762_CR13","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1137\/080713380","volume":"20","author":"S Kim","year":"2009","unstructured":"Kim, S., Kojima, M., Waki, H.: Exploiting sparsity in SDP relaxation for sensor network localization. SIAM J. Optim. 20(1), 192\u2013215 (2009)","journal-title":"SIAM J. Optim."},{"key":"1762_CR14","unstructured":"Liang, T.-C., Wang, T.-C., Ye, Y.: A gradient search method to round the semidefinite programming relaxation solution for ad hoc wireless sensor network localization. Technical Report, Department of Management Science and Engineering, Stanford University (2004)"},{"issue":"1","key":"1762_CR15","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF00939948","volume":"72","author":"ZQ Luo","year":"1992","unstructured":"Luo, Z.Q., Tseng, P.: On the convergence of the coordinate descent method for convex differentiable minimization. J. Optim. Theory Appl. 72(1), 7\u201335 (1992)","journal-title":"J. Optim. Theory Appl."},{"key":"1762_CR16","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s10589-007-9131-z","volume":"43","author":"J Nie","year":"2009","unstructured":"Nie, J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43, 151\u2013179 (2009)","journal-title":"Comput. Optim. Appl."},{"key":"1762_CR17","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, NY (2006)","edition":"2"},{"key":"1762_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10107-006-0040-1","volume":"109","author":"AM-C So","year":"2007","unstructured":"So, A.M.-C., Ye, Y.: Theory of semidefinite programming for sensor network localization. Math. Program. Ser. B 109, 367\u2013384 (2007)","journal-title":"Math. Program. Ser. B"},{"issue":"1","key":"1762_CR19","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1137\/050640308","volume":"18","author":"P Tseng","year":"2007","unstructured":"Tseng, P.: Second-order cone programming relaxation of sensor network localization. SIAM J. Optim. 18(1), 156\u2013185 (2007)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1762_CR20","doi-asserted-by":"publisher","first-page":"1040","DOI":"10.1109\/TCNS.2019.2926775","volume":"7","author":"C Wan","year":"2020","unstructured":"Wan, C., Jing, G., You, S., Dai, R.: Sensor network localization via alternating rank minimization algorithms. IEEE Trans. Control Netw. Syst. 7(2), 1040\u20131051 (2020)","journal-title":"IEEE Trans. Control Netw. Syst."},{"key":"1762_CR21","doi-asserted-by":"crossref","unstructured":"Wan, C., You, S., Jing, G., Dai, R.: A distributed algorithm for sensor network localization with limited measurements of relative distance. In: 2019 American Control Conference, 4677\u20134682 (2019)","DOI":"10.23919\/ACC.2019.8814418"},{"issue":"2","key":"1762_CR22","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/060669395","volume":"19","author":"Z Wang","year":"2008","unstructured":"Wang, Z., Zheng, S., Ye, Y., Boyd, S.: Further relaxations of the semidefinite programming approach to sensor network localization. SIAM J. Optim. 19(2), 655\u2013673 (2008)","journal-title":"SIAM J. Optim."},{"key":"1762_CR23","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s10107-012-0584-1","volume":"142","author":"Z Wen","year":"2013","unstructured":"Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. Ser. A 142, 397\u2013434 (2013)","journal-title":"Math. Program. Ser. A"},{"key":"1762_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Program. Ser. B 151, 3\u201334 (2015)","journal-title":"Math. Program. Ser. B"},{"issue":"3","key":"1762_CR25","doi-asserted-by":"publisher","first-page":"1758","DOI":"10.1137\/120887795","volume":"6","author":"Y Xu","year":"2013","unstructured":"Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3), 1758\u20131789 (2013)","journal-title":"SIAM J. Imaging Sci."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01762-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01762-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01762-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T06:20:08Z","timestamp":1647843608000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01762-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,7]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["1762"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01762-9","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2021,6,7]]},"assertion":[{"value":"29 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}