John Ellipsoids via Lazy Updates
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916550148096000 |
|---|---|
| author | Woodruff, David P. Yasuda, Taisuke |
| author_facet | Woodruff, David P. Yasuda, Taisuke |
| contents | We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01801 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | John Ellipsoids via Lazy Updates Woodruff, David P. Yasuda, Taisuke Data Structures and Algorithms Machine Learning We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas. |
| title | John Ellipsoids via Lazy Updates |
| topic | Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2501.01801 |