A minimum volume covering approach with a set of ellipsoids

IEEE Trans Pattern Anal Mach Intell. 2013 Dec;35(12):2997-3009. doi: 10.1109/TPAMI.2013.94.

Abstract

A technique for adjusting a minimum volume set of covering ellipsoids technique is elaborated. Solutions to this problem have potential application in one-class classification and clustering problems. Its main original features are: 1) It avoids the direct evaluation of determinants by using diagonalization properties of the involved matrices, 2) it identifies and removes outliers from the estimation process, 3) it avoids binary variables resulting from the combinatorial character of the assignment problem that are replaced by continuous variables in the range [0,1], 4) the problem can be solved by a bilevel algorithm that in its first level determines the ellipsoids and in its second level reassigns the data points to ellipsoids and identifies outliers based on an algorithm that forces the Karush-Kuhn-Tucker conditions to be satisfied. Two theorems provide rigorous bases for the proposed methods. Finally, a set of examples of application in different fields is given to illustrate the power of the method and its practical performance.

Publication types

  • Research Support, Non-U.S. Gov't