“Controlling singular values with semidefinite programming” by Kovalsky, Aigerman, Basri and Lipman

  • ©Shahar Z. Kovalsky, Noam Aigerman, Ronen Basri, and Yaron Lipman




    Controlling singular values with semidefinite programming

Session/Category Title: Geometry Processing




    Controlling the singular values of n-dimensional matrices is often required in geometric algorithms in graphics and engineering. This paper introduces a convex framework for problems that involve singular values. Specifically, it enables the optimization of functionals and constraints expressed in terms of the extremal singular values of matrices.Towards this end, we introduce a family of convex sets of matrices whose singular values are bounded. These sets are formulated using Linear Matrix Inequalities (LMI), allowing optimization with standard convex Semidefinite Programming (SDP) solvers. We further show that these sets are optimal, in the sense that there exist no larger convex sets that bound singular values.A number of geometry processing problems are naturally described in terms of singular values. We employ the proposed framework to optimize and improve upon standard approaches. We experiment with this new framework in several applications: volumetric mesh deformations, extremal quasi-conformal mappings in three dimensions, non-rigid shape registration and averaging of rotations. We show that in all applications the proposed approach leads to algorithms that compare favorably to state-of-art algorithms.


    1. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3d. ACM Trans. Graph. 32, 4, 106–120. Google ScholarDigital Library
    2. Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. Proc. SIGGRAPH, 157–164. Google ScholarDigital Library
    3. Alexa, M. 2002. Linear combination of transformations. ACM Trans. Graph. 21, 3 (July), 380–387. Google ScholarDigital Library
    4. Allen, B., Curless, B., and Popović, Z. 2003. The space of human body shapes: Reconstruction and parameterization from range scans. ACM Trans. Graph. 22, 3 (July), 587–594. Google ScholarDigital Library
    5. Andersen, E. D., and Andersen, K. D. 1999. The MOSEK interior point optimization for linear programming: an implementation of the homogeneous algorithm. Kluwer Academic Publishers, 197–232.Google Scholar
    6. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: Shape completion and animation of people. ACM Trans. Graph. 24, 3 (July), 408–416. Google ScholarDigital Library
    7. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14, 2 (Feb.), 239–256. Google ScholarDigital Library
    8. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4 (July), 98:1–98:12. Google ScholarDigital Library
    9. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, New York, NY, USA. Google ScholarDigital Library
    10. Boyer, D. M., Lipman, Y., St. Clair, E., Puente, J., Patel, B. A., Funkhouser, T., Jernvall, J., and Daubechies, I. 2011. Algorithms to automatically quantify the geometric similarity of anatomical surfaces. Proceedings of the National Academy of Sciences 108, 45, 18221–18226.Google ScholarCross Ref
    11. Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
    12. Candès, E. J., and Recht, B. 2009. Exact matrix completion via convex optimization. Foundations of Computational mathematics 9, 6, 717–772. Google ScholarDigital Library
    13. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4, 38. Google ScholarDigital Library
    14. Ecker, A., Jepson, A. D., and Kutulakos, K. N. 2008. Semidefinite programming heuristics for surface reconstruction ambiguities. In ECCV 2008. Springer, 127–140. Google ScholarDigital Library
    15. Floater, M. S., and Hormann, K. 2005. Surface parameterization: a tutorial and survey. In Advances in Multiresolution for Geometric Modelling, Springer, 157–186.Google Scholar
    16. Freitag, L. A., and Knupp, P. M. 2002. Tetrahedral mesh improvement via optimization of the element condition number. International Journal for Numerical Methods in Engineering 53, 6, 1377–1391.Google ScholarCross Ref
    17. Giorgi, D., Biasotti, S., and Paraboschi, L., 2007. Shape retrieval contest 2007: Watertight models track.Google Scholar
    18. Goemans, M. X., and Williamson, D. P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6 (Nov.), 1115–1145. Google ScholarDigital Library
    19. Hernandez, F., Cirio, G., Perez, A. G., and Otaduy, M. A. 2013. Anisotropic strain limiting. In Proc. of Congreso Español de Informática Gráfica.Google Scholar
    20. Hormann, K., and Greiner, G. 2000. MIPS: An efficient global parametrization method. In Curve and Surface Design: Saint-Malo 1999. Vanderbilt University Press, 153–162.Google Scholar
    21. Hormann, K., Lévy, B., and Sheffer, A. 2007. Mesh parameterization: Theory and practice. In ACM SIGGRAPH 2007 Courses, ACM, New York, NY, USA, SIGGRAPH ’07. Google ScholarDigital Library
    22. Huang, Q., and Guibas, L. 2013. Consistent shape maps via semidefinite programming. Proc. Eurographics Symposium on Geometry Processing 32, 5, 177–186. Google ScholarDigital Library
    23. Huang, Q.-X., Adams, B., Wicke, M., and Guibas, L. J. 2008. Non-rigid registration under isometric deformations. In Proc. Eurographics Symposium on Geometry Processing, 1449–1457. Google ScholarDigital Library
    24. Igarashi, T., Moscovich, T., and Hughes, J. F. 2005. As-rigid-as-possible shape manipulation. ACM Trans. Graph. 24, 3 (July), 1134–1141. Google ScholarDigital Library
    25. Jeuris, B., Vandebril, R., and Vandereycken, B. 2012. A survey and comparison of contemporary algorithms for computing the matrix geometric mean. Electronic Transactions on Numerical Analysis 39, 379–402.Google Scholar
    26. Karcher, H. 1977. Riemannian center of mass and mollifier smoothing. Comm. pure and applied mathematics 30, 5, 509–541.Google Scholar
    27. Kiwiel, K. 1986. A linearization algorithm for optimizing control systems subject to singular value inequalities. IEEE Transactions on Automatic Control 31, 7, 595–603.Google ScholarCross Ref
    28. Lévy, B., Petitjean, S., Ray, N., and Maillot, J. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3 (July), 362–371. Google ScholarDigital Library
    29. Li, H., Sumner, R. W., and Pauly, M. 2008. Global correspondence optimization for non-rigid registration of depth scans. Proc. Eurographics Symposium on Geometry Processing 27, 5. Google ScholarDigital Library
    30. Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4, 108. Google ScholarDigital Library
    31. Lipman, Y. 2014. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM J. Imaging Sci., to appear.Google Scholar
    32. Liu, L., Zhang, L., Xu, Y., Gotsman, C., and Gortler, S. J. 2008. A local/global approach to mesh parameterization. Proc. Eurographics Symposium on Geometry Processing 27, 5, 1495–1504. Google ScholarDigital Library
    33. Löfberg, J. 2004. Yalmip: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference.Google ScholarCross Ref
    34. Lu, Z., and Pong, T. K. 2011. Minimizing condition number via convex programming. SIAM J. Matrix Analysis Applications 32, 4, 1193–1211. Google ScholarDigital Library
    35. Maréchal, P., and Ye, J. J. 2009. Optimizing condition numbers. SIAM Journal on Optimization 20, 2, 935–947. Google ScholarDigital Library
    36. Paillé, G.-P., and Poulin, P. 2012. As-conformal-as-possible discrete volumetric mapping. Computers & Graphics 36, 5, 427–433. Google ScholarDigital Library
    37. Polak, E., and Wardi, Y. 1982. Nondifferentiable optimization algorithm for designing control systems having singular value inequalities. Automatica 18, 3, 267–283. Google ScholarDigital Library
    38. Rentmeesters, Q., and Absil, P.-A. 2011. Algorithm comparison for karcher mean computation of rotation matrices and diffusion tensors. In Proc. European Signal Processing Conference, EURASIP, 2229–2233.Google Scholar
    39. Rossignac, J., and Vinacua, A. 2011. Steady affine motions and morphs. ACM Trans. Graph. 30, 5 (Oct.), 116:1–116:16. Google ScholarDigital Library
    40. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In Int. Conf. 3D Digital Imaging and Modeling.Google Scholar
    41. Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. Proc. SIGGRAPH, 409–416. Google ScholarDigital Library
    42. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Proc. Eurographics Symposium on Geometry Processing 32, 5, 125–135. Google ScholarDigital Library
    43. Shoemake, K. 1985. Animating rotation with quaternion curves. SIGGRAPH Comput. Graph. 19, 3 (July), 245–254. Google ScholarDigital Library
    44. Singer, A. 2011. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis 30, 1, 20–36.Google ScholarCross Ref
    45. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. Eurographics Symposium on Geometry Processing, 109–116. Google ScholarDigital Library
    46. Sorkine, O., Cohen-Or, D., Goldenthal, R., and Lischinski, D. 2002. Bounded-distortion piecewise mesh parameterization. In Proc. Conference on Visualization ’02, VIS ’02, 355–362. Google ScholarDigital Library
    47. Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
    48. Sun, J., Ovsjanikov, M., and Guibas, L. 2009. A concise and provably informative multi-scale signature based on heat diffusion. In Proc. Eurographics Symposium on Geometry Processing, 1383–1392. Google ScholarDigital Library
    49. Vandenberghe, L., and Boyd, S. 1994. Semidefinite programming. SIAM Review 38, 49–95. Google ScholarDigital Library
    50. Wang, H., O’Brien, J., and Ramamoorthi, R. 2010. Multi-resolution isotropic strain limiting. In ACM SIGGRAPH Asia 2010, 156:1–156:10. Google ScholarDigital Library
    51. Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. Computer Graphics Forum 31, 5, 1679–1689. Google ScholarDigital Library
    52. Weinberger, K. Q., and Saul, L. K. 2009. Distance metric learning for large margin nearest neighbor classification. J. Mach. Learn. Res. 10 (June), 207–244. Google ScholarCross Ref

ACM Digital Library Publication: