# Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid

arXiv: https://arxiv.org/abs/1702.06254 · HTML: https://mlsanity.com/paper/1702.06254/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Minimum Volume Conformal Sets for Multivariate Regression](https://mlsanity.com/paper/2503.19068/) (2025)

## Abstract (arXiv)

The minimum volume enclosing ellipsoid (MVEE) problem is an optimization problem in the basis of many practical problems. This paper describes some new properties of this model and proposes a first-order oracle algorithm, the Adjusted Coordinate Descent (ACD) algorithm, to address the MVEE problem. The ACD algorithm is globally linear convergent and has an overwhelming advantage over the other algorithms in cases where the dimension of the data is large. Moreover, as a byproduct of the convergence property of the ACD algorithm, we prove the global linear convergence of the Frank-Wolfe type algorithm (illustrated by the case of Wolfe-Atwood's algorithm), which supports the conjecture of Todd. Furthermore, we provide a new interpretation for the means of choosing the coordinate axis of the Frank-Wolfe type algorithm from the perspective of the smoothness of the coordinate axis, i.e., the algorithm chooses the coordinate axis with the worst smoothness at each iteration. This finding connects the first-order oracle algorithm and the linear optimization oracle algorithm on the MVEE problem. The numerical tests support our theoretical results.