Shahar Z. Kovalsky
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
- Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3d. ACM Trans. Graph. 32, 4, 106--120. Google Scholar
Digital Library
- Alexa, M., Cohen-Or, D., and Levin, D. 2000. As-rigid-as-possible shape interpolation. Proc. SIGGRAPH, 157--164. Google ScholarDigital Library
- Alexa, M. 2002. Linear combination of transformations. ACM Trans. Graph. 21, 3 (July), 380--387. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, New York, NY, USA. Google ScholarDigital Library
- 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
- Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3 (July). Google ScholarDigital Library
- 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
- 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
- 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
- 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
- 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
- Giorgi, D., Biasotti, S., and Paraboschi, L., 2007. Shape retrieval contest 2007: Watertight models track.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Karcher, H. 1977. Riemannian center of mass and mollifier smoothing. Comm. pure and applied mathematics 30, 5, 509--541.Google Scholar
- 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
- 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
- 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
- Lipman, Y. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4, 108. Google ScholarDigital Library
- Lipman, Y. 2014. Bijective mappings of meshes with boundary and the degree in mesh processing. SIAM J. Imaging Sci., to appear.Google Scholar
- 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
- Löfberg, J. 2004. Yalmip: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference.Google ScholarCross Ref
- 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
- Maréchal, P., and Ye, J. J. 2009. Optimizing condition numbers. SIAM Journal on Optimization 20, 2, 935--947. Google ScholarDigital Library
- Paillé, G.-P., and Poulin, P. 2012. As-conformal-as-possible discrete volumetric mapping. Computers & Graphics 36, 5, 427--433. Google ScholarDigital Library
- 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
- 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
- Rossignac, J., and Vinacua, A. 2011. Steady affine motions and morphs. ACM Trans. Graph. 30, 5 (Oct.), 116:1--116:16. Google ScholarDigital Library
- Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In Int. Conf. 3D Digital Imaging and Modeling.Google Scholar
- Sander, P. V., Snyder, J., Gortler, S. J., and Hoppe, H. 2001. Texture mapping progressive meshes. Proc. SIGGRAPH, 409--416. Google ScholarDigital Library
- 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
- Shoemake, K. 1985. Animating rotation with quaternion curves. SIGGRAPH Comput. Graph. 19, 3 (July), 245--254. Google ScholarDigital Library
- Singer, A. 2011. Angular synchronization by eigenvectors and semidefinite programming. Applied and Computational Harmonic Analysis 30, 1, 20--36.Google ScholarCross Ref
- Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. Eurographics Symposium on Geometry Processing, 109--116. Google ScholarDigital Library
- 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
- Sumner, R. W., Schmid, J., and Pauly, M. 2007. Embedded deformation for shape manipulation. ACM Trans. Graph. 26, 3. Google ScholarDigital Library
- 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
- Vandenberghe, L., and Boyd, S. 1994. Semidefinite programming. SIAM Review 38, 49--95. Google ScholarDigital Library
- 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
- Weber, O., Myles, A., and Zorin, D. 2012. Computing extremal quasiconformal maps. Computer Graphics Forum 31, 5, 1679--1689. Google ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
- Controlling singular values with semidefinite programming
Recommendations
Nonnegative matrices with prescribed extremal singular values
We consider the problem of constructing nonnegative matrices with prescribed extremal singular values. In particular, given 2n-1 real numbers @s"1^(^j^) and @s"j^(^j^),j=1,...,n, we construct an nxn nonnegative bidiagonal matrix B and an nxn nonnegative ...
Bounds on Singular Values Revealed by QR Factorizations
AbstractWe introduce a pair of dual concepts: pivoted blocks and reverse pivoted blocks. These blocks are the outcome of a special column pivoting strategy in QR factorization. Our main result is that under such a column pivoting strategy, the QR ...
Accurately Counting Singular Values of Bidiagonal Matrices and Eigenvalues of Skew-Symmetric Tridiagonal Matrices
We have developed algorithms to count singular values of a real bidiagonal matrix which are greater than a specified value. This requires the transformation of the singular value problem to an equivalent symmetric eigenvalue problem. The counting of ...
Comments