Controlling singular values with semidefinite programming
Controlling singular values with semidefinite programming
复制标题
DOI：
10.1145/2601097.2601142
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
S. Kovalsky;Noam Aigerman;R. Basri;Y. Lipman
中科院分区：
文献类型：
--
作者：
S. Kovalsky;Noam Aigerman;R. Basri;Y. Lipman
在图形和工程中的几何算法中，经常需要控制n维矩阵的奇异值。本文给出了涉及奇异值问题的一个凸框架。具体地说，它使得用矩阵的极值奇异值表示的泛函和约束的最优化成为可能。为此，我们引入了一族奇异值有界的凸矩阵集。这些集合使用线性矩阵不等式(LMI)表示，允许使用标准的凸半定规划(SDP)求解器进行优化。我们进一步证明了这些集是最优的，因为不存在约束奇异值的更大的凸集。许多几何处理问题自然是用奇异值来描述的。我们采用提议的框架来优化和改进标准方法。我们在几个应用中对这个新框架进行了实验：体积网格变形、三维极值准保角映射、非刚性形状配准和旋转平均。我们表明，在所有的应用中，所提出的方法导致的算法比最先进的算法更好。
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.