License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.1
URN: urn:nbn:de:0030-drops-78848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7884/
Go to the corresponding LIPIcs Volume Portal

Woodruff, David P.

Sketching for Geometric Problems (Invited Talk)

pdf-format:
LIPIcs-ESA-2017-1.pdf (0.3 MB)

Abstract

In this invited talk at the European Symposium on Algorithms (ESA), 2017, I will discuss a tool called sketching, which is a form of data dimensionality reduction, and its applications to several problems in high dimensional geometry. In particular, I will show how to obtain the fastest possible algorithms for fundamental problems such as projection onto a flat, and also study generalizations of projection onto more complicated objects such as the union of flats or subspaces. Some of these problems are just least squares regression problems, with many applications in machine learning, numerical linear algebra, and optimization. I will also discuss low rank approximation, with applications to clustering. Finally I will mention a number of other applications of sketching in machine learning, numerical linear algebra, and optimization.

BibTeX - Entry

@InProceedings{woodruff:LIPIcs:2017:7884,
  author =	{David P. Woodruff},
  title =	{{Sketching for Geometric Problems (Invited Talk)}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{1:1--1:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7884},
  URN =		{urn:nbn:de:0030-drops-78848},
  doi =		{10.4230/LIPIcs.ESA.2017.1},
  annote =	{Keywords: dimensionality reduction, low rank approximation, projection, regression, sketching}
}

Keywords: dimensionality reduction, low rank approximation, projection, regression, sketching
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI