BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Fast Algorithms for Linear Algebraic Computation
DTSTART:20220617T140000
DTEND:20220617T160000
DTSTAMP:20260407T055549Z
UID:9ca4db0598696e1784dce6d36c1bd00f4807a239c74dad0f6af98036
CATEGORIES:Conferences - Seminars
DESCRIPTION:Kshiteej Sheth\nEDIC candidacy exam\nExam president: Prof. Mik
 a Göös\nThesis advisor: Prof. Michael Kapralov\nCo-examiner: Prof. Ola S
 vensson\n\nAbstract\nLinear algebraic objects and computation are at the c
 ore of modern machine learning and data science. Large and high-dimensiona
 l datasets are represented in terms of matrices and modern computational t
 asks require fast primitives to quickly manipulate them. In this report\, 
 we focus on two main paradigms in linear algebraic computation in modern s
 ettings. First\, we discuss a fundamental work in linear sketching and mat
 rix compression which obtains embeddings for large data matrices that appr
 oximately preserve the norm of every vector in their column space with hig
 h probability and applying the embedding takes input-sparsity time. This l
 eads to input-sparsity time algorithms for various problems such as approx
 imate regression and low-rank approximation. Secondly\, we discuss a recen
 t result that obtains linear and sublinear time algorithms for computing c
 oarse information about the full eigenspectrum of an $n\\times n$ hermitia
 n matrix. This employs fast algorithms for approximating the trace of a ma
 trix and we also discuss another recent work that obtains tight bounds for
  this problem. Finally we discuss future research directions concerning th
 ese two paradigms and the progress we have made so far.\n\nBackground pape
 rs\n\n	OSNAP: Faster numerical linear algebra algorithms via sparser subsp
 ace embeddings\, FOCS 2013 - https://arxiv.org/pdf/1211.1002.pdf\n	Linear
  and Sublinear Time Spectral Density Estimation\, STOC 2022 - https://arx
 iv.org/pdf/2104.03461.pdf\n	Hutch++: Optimal Stochastic Trace Estimation\,
  SOSA 2021 - https://arxiv.org/pdf/2010.09649.pdf \n
LOCATION:BC 02 https://plan.epfl.ch/?room==BC%2002
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR