Abstract
In this article, we investigate some theoretical and computational issues of the geometric buildup algorithm proposed by Sit, Wu and Yuan (Bull. Math. Biol. 71:1914–1933, 2009) for the solution of the distance geometry problem with sparse and inexact distances. This algorithm repeatedly uses a least-squares approximation to determine the position of an undetermined atom, using the distances from this atom to a set of previously determined ones. The least-squares approximation, obtained from the singular value decomposition of a distance-induced matrix, can find the best possible position for the atom, even if the distances have small errors, as they usually do in practice, and therefore make the geometric buildup algorithm more stable than its previous versions that relied on linear system solvers. We estimate its numerical errors and prove some of its key mathematical properties. We also present some numerical results with varying some of the parameters in the algorithm and show how they may be used to improve its performance and computational accuracy.
Similar content being viewed by others
References
Sit, A., Wu, Z., Yuan, Y.: A geometric buildup algorithm for the solution of the distance geometry problem using least-squares approximation. Bull. Math. Biol. 71, 1914–1933 (2009)
Crippen, G.M., Havel, T.F.: Distance Geometry and Molecular Conformation. Wiley, New York (1988)
Havel, T.F.: Distance geometry: theory, algorithms, and chemical applications. In: Encyclopedia of Computational Chemistry. Wiley, New York (1998)
Huang, H.-X., Liang, Z.-A., Pardalos, P.: Some properties for the Euclidean distance matrix and positive semi-definite matrix completion problems. J. Glob. Optim. 25, 3–21 (2003)
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput. 21, 65–84 (1992)
Saxe, J.B.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proceedings 17th Annual Allerton Conference on Communication, Control and Computing, pp. 480–489 (1979)
Kearsley, A., Tapia, R., Trosset, M.: The solution of the metric STRESS and SSTRESS problems in multidimensional scaling using Newton’s method. Comput. Comput. Stat. 13, 369–396 (1998)
Klock, H., Buhmann, J.M.: Multidimensional scaling by deterministic annealing. In: Pilillo, M., Hancock, E.R. (eds.) Energy Minimization Methods in Computer Vision and Pattern Recognition. Lecture Notes in Computer Science, vol. 1223, pp. 246–260. Springer, Berlin (1997)
So, A., Ye, Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)
Wang, Z., Zheng, S., Boyd, S., Ye, Y.: Further relaxations of the SDP approach to sensor network localization. SIAM J. Optim. 19, 655–673 (2008)
Zheng, Z.-Z., Luo, X.-L., Wu, Z.: A geometric buildup algorithm for the solution of the sensor network localization problem. Comput. Optim. Appl. (2010, accepted)
Hou, J.T., Sims, G.E., Zhang, C., Kim, S.H.: A global representation of the protein fold space. Proc. Natl. Acad. Sci. USA 100, 2386–2390 (2003)
Moré, J.J., Wu, Z.: ε-optimal solutions to distance geometry problems via global continuation. In: Pardalos, P.M., Shalloway, D., Xue, G. (eds.) Global Minimization of Non-convex Energy Functions: Molecular Conformation and Protein Folding, pp. 151–168. American Mathematical Society, Providence (1996)
Glunt, W., Hayden, T.L.: Improved convergence and speed for the distance geometry program APA to determine protein structure. Comput. Chem. 25, 223–230 (2001)
Glunt, W., Hayden, T.L., Hong, S., Wells, J.: An alternating projection algorithm for computing the nearest Euclidean distance matrix. SIAM J. Matrix Anal. Appl. 11, 589–600 (1990)
Glunt, W., Hayden, T.L., Raydan, M.: Molecular conformations from distance matrices. J. Comput. Chem. 14, 114–120 (1993)
Hendrickson, B.: The molecule problem: exploiting structure in global optimization. SIAM J. Optim. 5, 835–857 (1995)
Moré, J.J., Wu, Z.: Distance geometry optimization for protein structures. J. Glob. Optim. 15, 219–234 (1999)
Zou, Z.H., Bird, R.H., Schnabel, R.B.: A stochastic/perturbation global optimization algorithm for distance geometry problems. J. Glob. Optim. 11, 91–105 (1997)
Le Thi, A.H., Pham Dinh, T.: Large scale molecular optimization from distance matrices by a d. c. optimization approach. SIAM J. Optim. 14, 77–114 (2003)
Biswas, P., Toh, K.C., Ye, Y.: A distributed SDP approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput. 30, 1251–1277 (2008)
Grosso, A., Locatelli, M., Schoen, F.: Solving molecular distance geometry problems by global optimization algorithms. Comput. Optim. Appl. 43, 23–37 (2009)
Huang, H.-X., Pardalos, P.M.: A multivariate partition approach to optimization problems. Cybern. Syst. Anal. 38, 265–275 (2002)
Huang, H.-X., Pardalos, P.M., Shen, Z.-J.: Equivalent formulations and necessary optimality conditions for the Lenard-Jones problem. J. Glob. Optim. 22, 97–118 (2002)
Dong, Q., Wu, Z.: A linear-time algorithm for solving the molecular distance geometry problem with exact inter-atomic distances. J. Glob. Optim. 22, 365–375 (2002)
Dong, Q., Wu, Z.: A geometric buildup algorithm for solving the molecular distance geometry problem with sparse distance data. J. Glob. Optim. 26, 321–333 (2003)
Wu, D., Wu, Z.: An updated geometric buildup algorithm for solving the molecular distance geometry problem with sparse distance data. J. Glob. Optim. 37, 661–673 (2007)
Strang, G.: Linear Algebra and Its Applications, 3rd edn. Thomson Learning, Andover (1988)
Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore (1989)
Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkürlichen Funktionen nach System vorgeschriebener. Math. Ann. 63, 433–476 (1907)
Weyl, H.: Das asymptotische Verteilungsgesetz der Eigenwert linearer partieller Differentialgleichungen (mit einer Anwendung aufder Theorie der Hohlraumstrahlung). Math. Ann. 71, 441–479 (1912)
Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218 (1936)
Hoffman, A.J., Wielandt, H.W.: The variation of the spectrum of a normal matrix. Duke Math. J. 20, 37–39 (1953)
Golub, G.H., Kahan, W.: Calculating the singular values and pseudo-inverse of a matrix. SIAM J. Numer. Anal. 2, 205–224 (1965)
Stewart, G.W.: On the early history of the singular value decomposition. SIAM Rev. 35, 551–566 (1993)
Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (1999)
Stewart, G.W.: Perturbation theory for the singular value decomposition. In: Vacarro, R.J. (ed.) SVD and Signal Processing, II. Elsevier, Amsterdam (1991)
MATLAB 6.5, The MathWorks Inc. (2003). http://www.mathworks.com
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Luo, Xl., Wu, Zj. Least-Squares Approximations in Geometric Buildup for Solving Distance Geometry Problems. J Optim Theory Appl 149, 580–598 (2011). https://doi.org/10.1007/s10957-011-9806-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-011-9806-6