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.

Preview

PDF WRAP-leveraging-conditioned-streaming-summaries-Minkowski-Cormode-2018.pdf - Accepted Version - Requires a PDF viewer. Download (1482Kb) | Preview

Request Changes to record.

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 > 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
Date of first compliant deposit:	11 June 2018
Volume:	80
Page Range:	pp. 1243-1251
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
RIOXX Funder/Project Grant:	Project/Grant ID RIOXX Funder Name Funder ID ERC-2014-CoG 647557 European Research Council http://viaf.org/viaf/130022607 EP/N510129/1 [EPSRC] Engineering and Physical Sciences Research Council http://dx.doi.org/10.13039/501100000266 CCF-1815840 National Science Foundation http://dx.doi.org/10.13039/100000001
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:	Related item in WRAP Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads