A Fast Algorithm for Multidimensional Ellipsoid-Specific Fitting by Minimizing a New Defined Vector Norm of Residuals Using Semidefinite Programming

作者：Ying, Xianghua^*; Yang, Li; Zha, Hongbin

来源：IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(9): 1856-1863.

DOI：10.1109/TPAMI.2012.109

• Multidimensional ellipsoid
• ellipsoid-specific fitting
• semidefinite programming
• new defined vector norm

A quadratic surface in n-dimensional space is defined as the locus of zeros of a quadratic polynomial. The quadratic polynomial may be compactly written in notation by an (n + 1)-vector and a real symmetric matrix of order n + 1, where the vector represents homogenous coordinates of an n-D point, and the symmetric matrix is constructed from the quadratic coefficients. If an n-D quadratic surface is an n-D ellipsoid, the leading n x n principal submatrix of the symmetric matrix would be positive or opposite definite. As we know, to impose a matrix being positive or opposite definite, perhaps the best choice may be to employ semidefinite programming (SDP). From such straightforward and intuitive knowledge, in the literature until 2002, Calafiore first proposed a feasible method for multidimensional ellipsoid-specific fitting using SDP, which minimizes the 2-norm of the algebraic residual vector. However, the runtime of the method is significantly long and memory is often out when the number of fitted points is greater than several thousand. In this paper, we propose a fast and easily implemented algorithm for multidimensional ellipsoid-specific fitting by minimizing a new defined vector norm of the algebraic residual vector using SDP, which drastically decreases the size of the SDP problem while preserving accuracy. The proposed fast method can handle several million fitted points without any difficulty.

• 出版日期2012-9
• 单位北京大学