2024/11/06 by Elizabeth A. Harris, Harris, Elizabeth, Ali Eshragh +7
Computer Science · #62-06 #62K05 #90-08 #90C25 #90C59 #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Medical Image Segmentation Techniques #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2411.03617
openalex publication_date 2024/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Minimum Volume Covering Ellipsoid (MVCE) problem, characterised by n observations in d dimensions where n ≫ d, can be computationally very expensive in the big data regime. We apply methods from randomised numerical linear algebra to develop a data-driven leverage score sampling algorithm for solving MVCE, and establish theoretical error bounds and a convergence guarantee. Assuming the leverage scores follow a power law decay, we show that the computational complexity of computing the approximation for MVCE is reduced from O(nd2) to O(nd + poly(d)), which is a significant improvement in big data problems. Numerical experiments demonstrate the efficacy of our new algorithm, showing that it substantially reduces computation time and yields near-optimal solutions.