Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Woodruff, David P. https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-140755
URL:

A Very Sketchy Talk (Invited Talk)

pdf-format:


Abstract

We give an overview of dimensionality reduction methods, or sketching, for a number of problems in optimization, first surveying work using these methods for classical problems, which gives near optimal algorithms for regression, low rank approximation, and natural variants. We then survey recent work applying sketching to column subset selection, kernel methods, sublinear algorithms for structured matrices, tensors, trace estimation, and so on. The focus is on fast algorithms. This is a short survey accompanying an invited talk at ICALP, 2021.

BibTeX - Entry

@InProceedings{woodruff:LIPIcs.ICALP.2021.6,
  author =	{Woodruff, David P.},
  title =	{{A Very Sketchy Talk}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{6:1--6:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14075},
  URN =		{urn:nbn:de:0030-drops-140755},
  doi =		{10.4230/LIPIcs.ICALP.2021.6},
  annote =	{Keywords: dimensionality reduction, optimization, randomized numerical linear algebra, sketching}
}

Keywords: dimensionality reduction, optimization, randomized numerical linear algebra, sketching
Seminar: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue date: 2021
Date of publication: 02.07.2021


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