“Controlling singular values with semidefinite programming” by Kovalsky, Aigerman, Basri and Lipman
Conference:
Type:
Session Title:
- Geometry Processing
Title:
- Controlling singular values with semidefinite programming
Moderator(s):
Presenter(s)/Author(s):
Abstract:
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.
References:
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
