2026-08-07T04:46:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14075 2024-03-06T10:53:24Z ddc:004 open_access

A Very Sketchy Talk (Invited Talk) Woodruff, David P. dimensionality reduction optimization randomized numerical linear algebra sketching 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik David P. Woodruff 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.6 urn:nbn:de:0030-drops-140755 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.6 eng https://creativecommons.org/licenses/by/4.0/legalcode