Fast Multidimensional Ellipsoid-Specific Fitting by Alternating   Direction Method of Multipliers

doi:10.1109/TPAMI.2015.2469283

CORC > 北京大学 > 信息科学技术学院

	Fast Multidimensional Ellipsoid-Specific Fitting by Alternating Direction Method of Multipliers
	Lin, Zhouchen ; Huang, Yameng
刊名	IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
	2016
关键词	Multidimensional ellipsoid ellipsoid-specific fitting alternating direction method of multipliers SURFACES CURVES
DOI	10.1109/TPAMI.2015.2469283
英文摘要	Many problems in computer vision can be formulated as multidimensional ellipsoid-specific fitting, which is to minimize the residual error such that the underlying quadratic surface is a multidimensional ellipsoid. In this paper, we present a fast and robust algorithm for solving ellipsoid-specific fitting directly. Our method is based on the alternating direction method of multipliers, which does not introduce extra positive semi-definiteness constraints. The computation complexity is thus significantly lower than those of semi-definite programming (SDP) based methods. More specifically, to fit n data points into a p dimensional ellipsoid, our complexity is O(p(6) + np(4)) + O(p(3)), where the former O results from preprocessing data once, while that of the state-of-the-art SDP method is O(p(6) + np(4) + n(3/2)p(2)) for each iteration. The storage complexity of our algorithm is about 1/2np(2), which is at most 1/4 of those of SDP methods. Extensive experiments testify to the great speed and accuracy advantages of our method over the state-of-the-art approaches. The implementation of our method is also much simpler than SDP based methods.; 973 Program of China [2015CB352502]; National Natural Science Foundation of China [61272341, 61231002]; Microsoft; SCI(E); EI; ARTICLE; zlin@pku.edu.cn; huangyameng@pku.edu.cn; 5; 1021-1026; 38
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/437360]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Lin, Zhouchen,Huang, Yameng. Fast Multidimensional Ellipsoid-Specific Fitting by Alternating Direction Method of Multipliers[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,2016.
APA	Lin, Zhouchen,&Huang, Yameng.(2016).Fast Multidimensional Ellipsoid-Specific Fitting by Alternating Direction Method of Multipliers.IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE.
MLA	Lin, Zhouchen,et al."Fast Multidimensional Ellipsoid-Specific Fitting by Alternating Direction Method of Multipliers".IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE (2016).