×

Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints. (English) Zbl 1467.90075

The authors study the Euclidean distance matrix optimization with ordinal constraints (EDMOC) and propose the feasibility of EDMOC. The authors develop a majorized penalty method to solve a large-scale EDMOC model and convert a convex EDM optimization problem into an isotonic regression problem. Due to the partial spectral decomposition and the fast solver for an isotonic regression problem, the performance of the proposed algorithm is demonstrated to be superior both in terms of the solution quality and CPU-time in sensor network localization and molecular conformation.

MSC:

90C30 Nonlinear programming

Software:

SNLSDP; smacof; QSDP; DISCO
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bai, SH; Qi, HD, Tackling the flip ambiguity in wireless sensor network localization and beyond, Digital Signal Process., 55, C, 85-97 (2016) · doi:10.1016/j.dsp.2016.05.006
[2] Barlow, RE; Bartholomew, DJ; Bremner, JM; Brunk, HD, Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression (1973), New York: Wiley, New York
[3] Berman, HM; Westbrook, J.; Feng, ZK; Gilliland, G.; Bhat, TN; Weissig, H.; Shindyalov, IN; Bourne, PE, The protein data bank, Nucl. Acids Res., 28, 1, 235-242 (2000) · doi:10.1093/nar/28.1.235
[4] Biswas, P.; Liang, TC; Toh, KC; Ye, Y.; Wang, TC, Semidefinite programming approaches for sensor network localization with noisy distance measurements, IEEE Trans. Autom. Sci. Eng., 3, 4, 360-371 (2006) · doi:10.1109/TASE.2006.877401
[5] Biswas, P., Ye, Y.Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, pp. 46-54 (2004)
[6] Bogdan, M.; Van, DBE; Sabatti, C.; Su, W.; Candès, EJ, SLOPE-adaptive variable selection via convex optimization, Ann. Appl. Stat., 9, 3, 1103-1140 (2015) · Zbl 1454.62212 · doi:10.1214/15-AOAS842
[7] Borg, I.; Groenen, P., Modern multidimensional scaling: theory and applications, J. Educ. Meas., 40, 3, 277-280 (2010) · doi:10.1111/j.1745-3984.2003.tb01108.x
[8] Borg, I.; Groenen, PJF, Modern Multidensional Scaling (2005), Berlin: Springer, Berlin · Zbl 1085.62079
[9] Cox, TF; Cox, MAA, Multidimensional Scaling (2000), London: Chapman and Hall/CRC, London
[10] Dattorro, J., Convex Optimization and Euclidean Distance Geometry (2005), Mountain View: Meboo, Mountain View
[11] De Leeuw, J.: Applications of convex analysis to multidimensional scaling. Recent Developments in Statistics, pp. 133-146 (2011)
[12] De Leeuw, J.; Mair, P., Multidimensional scaling using majorization: SMACOF in R, J. Stat. Softw., 31, 3, 1-30 (2009) · doi:10.18637/jss.v031.i03
[13] Ding, C.; Qi, HD, Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation, Comput. Optim. Appl., 66, 1, 187-218 (2017) · Zbl 1369.90120 · doi:10.1007/s10589-016-9858-5
[14] Elte, EL, The Semiregular Polytopes of the Hyperspaces (1912), Groningen: Hoitsema, Groningen · JFM 43.0637.02
[15] Fang, X.Y., Toh, K.C.: Using a distributed SDP approach to solve simulated protein molecular conformation problems. In: Distance Geometry, pp. 351-376. Springer (2013) · Zbl 1271.68233
[16] Gao, Y.; Sun, DF, Calibrating least squares covariance matrix problems with equality and inequality constraints, SIAM J. Matrix Anal., 31, 3, 1432-1457 (2009) · Zbl 1201.49031 · doi:10.1137/080727075
[17] Glunt, W.; Hayden, TL; Raydan, M., Molecular conformations from distance matrices, J. Comput. Chem., 14, 1, 114-120 (1993) · doi:10.1002/jcc.540140115
[18] Gower, JC, Properties of Euclidean and non-Euclidean distance matrices, Linear Algebra Appl., 67, none, 81-97 (1985) · Zbl 0569.15016 · doi:10.1016/0024-3795(85)90187-9
[19] Kruskal, JB, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29, 1, 1-27 (1964) · Zbl 0123.36803 · doi:10.1007/BF02289565
[20] Kruskal, JB, Nonmetric multidimensional scaling: a numerical method, Psychometrika, 29, 2, 115-129 (1964) · Zbl 0123.36804 · doi:10.1007/BF02289694
[21] Leung, N.; Hang, Z.; Toh, KC, An SDP-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization, SIAM J. Sci. Comput., 31, 6, 4351-4372 (2009) · Zbl 1203.93157 · doi:10.1137/080733103
[22] Li, QN; Qi, HD, An inexact smoothing Newton method for Euclidean distance matrix optimization under ordinal constraints, J. Comput. Math., 35, 4, 469-485 (2017) · Zbl 1413.90265 · doi:10.4208/jcm.1702-m2016-0748
[23] Liberti, L.; Lavor, C.; Maculan, N.; Mucherino, A., Euclidean distance geometry and applications, Quant. Biol., 56, 1, 3-69 (2012) · Zbl 1292.51010
[24] Mordukhovich, BS, Variational Analysis and Generalized Differentiation I (2006), Berlin: Springer, Berlin
[25] Qi, HD, A semismooth Newton’s method for the nearest Euclidean distance matrix problem, SIAM J. Matrix Anal. Appl., 34, 34, 67-93 (2013) · Zbl 1266.49052 · doi:10.1137/110849523
[26] Qi, HD, Conditional quadratic semidefinite programming: examples and methods, J. Oper. Res. Soc. China, 2, 2, 143-170 (2014) · Zbl 1338.90296 · doi:10.1007/s40305-014-0048-9
[27] Qi, HD; Xiu, NH; Yuan, XM, A Lagrangian dual approach to the single-source localization problem, IEEE Trans. Signal Process., 61, 15, 3815-3826 (2013) · Zbl 1393.94401 · doi:10.1109/TSP.2013.2264814
[28] Qi, HD; Yuan, XM, Computing the nearest Euclidean distance matrix with low embedding dimensions, Math. Program., 147, 1-2, 351-389 (2014) · Zbl 1304.49051 · doi:10.1007/s10107-013-0726-0
[29] Rosman, G., Bronstein, A.M., Bronstein, M.M., Sidi, A., Kimmel, R.: Fast multidimensional scaling using vector extrapolation. Technical report, Computer Science Department, Technion, (2008)
[30] Schoenberg, IJ, Remarks to maurice frechet’s article “sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de hilbert, Ann. Math., 36, 3, 724-732 (1935) · Zbl 0012.30703 · doi:10.2307/1968654
[31] Toh, KC, An inexact primal-dual path-following algorithm for convex quadratic SDP, Math. Program., 112, 1, 221-254 (2008) · Zbl 1136.90027 · doi:10.1007/s10107-006-0088-y
[32] Torgerson, WS, Multidimensional scaling: I. Theory and method, Psychometrika, 17, 4, 401-419 (1952) · Zbl 0049.37603 · doi:10.1007/BF02288916
[33] Young, G.; Householder, AS, Discussion of a set of points in terms of their mutual distances, Psychometrika, 3, 1, 19-22 (1938) · JFM 64.1302.04 · doi:10.1007/BF02287916
[34] Zhai, F.Z., Li, Q.N.: A Euclidean distance matrix model for protein molecular conformation. J. Global Optim. (2019) · Zbl 1436.90112
[35] Zhou, SL; Xiu, NH; Qi, HD, A fast matrix majorization-projection method for constrained stress minimization in MDS, IEEE Trans. Signal Process., 66, 3, 4331-4346 (2018) · Zbl 1414.90260 · doi:10.1109/TSP.2018.2849734
[36] Zhou, S.L., Xiu, N.H., Qi, H.D.: Robust Euclidean embedding via EDM optimization. Math. Program. Comput. (2019) · Zbl 1458.90500
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.