Dickens, Charlie, Cormode, Graham and Woodruff, David P. (2018) Leveraging well-conditioned bases : streaming and distributed summaries in Minkowski p-norms. In: ICML : 2018 Thirty-fifth International Conference on Machine Learning, Stockholm, Sweden, 10-15 Jul 2018. Published in: Proceedings of the 35th International Conference on Machine Learning, 80 pp. 1243-1251. ISSN 1938-7228.
![[thumbnail of WRAP-leveraging-conditioned-streaming-summaries-Minkowski-Cormode-2018.pdf]](https://cdn.statically.io/img/wrap.warwick.ac.uk/103193/7.hassmallThumbnailVersion/WRAP-leveraging-conditioned-streaming-summaries-Minkowski-Cormode-2018.pdf)  Preview |
PDF
WRAP-leveraging-conditioned-streaming-summaries-Minkowski-Cormode-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1MB) | Preview |
Abstract
Work on approximate linear algebra has led to efficient distributed and streaming algorithms for problems such as approximate matrix multiplication, low rank approximation, and regression, primarily for the Euclidean norm ℓ2. We study other ℓp norms, which are more robust for p<2, and can be used to find outliers for p>2. Unlike previous algorithms for such norms, we give algorithms that are (1) deterministic, (2) work simultaneously for every p≥1, including p=∞, and (3) can be implemented in both distributed and streaming environments. We study ℓp-regression, entrywise ℓp-low rank approximation, and versions of approximate matrix multiplication.
| Item Type: | Conference Item (Paper) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Algorithms, Minkowski geometry, Algebras, Linear, Regression analysis |
| Journal or Publication Title: | Proceedings of the 35th International Conference on Machine Learning |
| Publisher: | PMLR |
| ISSN: | 1938-7228 |
| Official Date: | 8 June 2018 |
| Dates: | Date Event 8 June 2018 Accepted |
| Volume: | 80 |
| Page Range: | pp. 1243-1251 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Date of first compliant deposit: | 11 June 2018 |
| Date of first compliant Open Access: | 22 October 2018 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID EP/N510129/1 [EPSRC] Engineering and Physical Sciences Research Council |
| Conference Paper Type: | Paper |
| Title of Event: | ICML : 2018 Thirty-fifth International Conference on Machine Learning |
| Type of Event: | Conference |
| Location of Event: | Stockholm, Sweden |
| Date(s) of Event: | 10-15 Jul 2018 |
| Related URLs: | |
| Persistent URL: | https://wrap.warwick.ac.uk/103193/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |