A Note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids

Abstract

We study the problem of computing the minimum volume enclosing ellipsoid (MVEE) containing a given set of ellipsoids S = {E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> , <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">hellip</sub> , E <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> } sube Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> . We show how to efficiently compute a small set X sube S of size at most a = |X| = O(d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> /epsi ) whose minimum volume ellipsoid is an (1 + epsi)-approximation to the minimum volume ellipsoid of S. We use an augmented real num ber model of computation to achieve a running time of O(alpha(nd <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">omega</sup> + d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> )) where omega < 2.376 is the exponent of square matrix multiplication. This is the best known complexity for solving the MVEE problem when n Gt d and e is large. The algorithm is built on the previous work by Kumar and Yrfdirim [17].