Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.14018 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909295785803776 |
|---|---|
| author | Li, Xiaoyu Song, Zhao Yu, Junwei |
| author_facet | Li, Xiaoyu Song, Zhao Yu, Junwei |
| contents | In 1948, Fritz John proposed a theorem stating that every convex body has a unique maximal volume inscribed ellipsoid, known as the John ellipsoid. The John ellipsoid has become fundamental in mathematics, with extensive applications in high-dimensional sampling, linear programming, and machine learning. Designing faster algorithms to compute the John ellipsoid is therefore an important and emerging problem. In [Cohen, Cousins, Lee, Yang COLT 2019], they established an algorithm for approximating the John ellipsoid for a symmetric convex polytope defined by a matrix $A \in \mathbb{R}^{n \times d}$ with a time complexity of $O(nd^2)$. This was later improved to $O(\text{nnz}(A) + d^ω)$ by [Song, Yang, Yang, Zhou 2022], where $\text{nnz}(A)$ is the number of nonzero entries of $A$ and $ω$ is the matrix multiplication exponent. Currently $ω\approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024]. In this work, we present the first quantum algorithm that computes the John ellipsoid utilizing recent advances in quantum algorithms for spectral approximation and leverage score approximation, running in $O(\sqrt{n}d^{1.5} + d^ω)$ time. In the tall matrix regime, our algorithm achieves quadratic speedup, resulting in a sublinear running time and significantly outperforming the current best classical algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_14018 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Speedups for Approximating the John Ellipsoid Li, Xiaoyu Song, Zhao Yu, Junwei Data Structures and Algorithms In 1948, Fritz John proposed a theorem stating that every convex body has a unique maximal volume inscribed ellipsoid, known as the John ellipsoid. The John ellipsoid has become fundamental in mathematics, with extensive applications in high-dimensional sampling, linear programming, and machine learning. Designing faster algorithms to compute the John ellipsoid is therefore an important and emerging problem. In [Cohen, Cousins, Lee, Yang COLT 2019], they established an algorithm for approximating the John ellipsoid for a symmetric convex polytope defined by a matrix $A \in \mathbb{R}^{n \times d}$ with a time complexity of $O(nd^2)$. This was later improved to $O(\text{nnz}(A) + d^ω)$ by [Song, Yang, Yang, Zhou 2022], where $\text{nnz}(A)$ is the number of nonzero entries of $A$ and $ω$ is the matrix multiplication exponent. Currently $ω\approx 2.371$ [Alman, Duan, Williams, Xu, Xu, Zhou 2024]. In this work, we present the first quantum algorithm that computes the John ellipsoid utilizing recent advances in quantum algorithms for spectral approximation and leverage score approximation, running in $O(\sqrt{n}d^{1.5} + d^ω)$ time. In the tall matrix regime, our algorithm achieves quadratic speedup, resulting in a sublinear running time and significantly outperforming the current best classical algorithms. |
| title | Quantum Speedups for Approximating the John Ellipsoid |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.14018 |