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

• Published in: IEEE transactions on pattern analysis and machine intelligence 2012-09, Vol.34 (9), p.1856-1863
• Main Authors: Ying, Xianghua, Yang, Li, Zha, Hongbin
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Applied sciences; Artificial intelligence; Computer science; control theory; systems; Eigenvalues and eigenfunctions; ellipsoid-specific fitting; Ellipsoids; Exact sciences and technology; Fitting; Fittings; Mathematical analysis; Minimization; Multidimensional ellipsoid; new defined vector norm; Norms; Pattern recognition. Digital image processing. Computational geometry; Programming; semidefinite programming; Studies; Surface fitting; Symmetric matrices; Vectors; Vectors (mathematics)
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2012.109

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 \times 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.