Speaker: Aditya Krishnan

\nAffiliation: Johns Hopkins U
niversity

Title: Schatten Norms in Matrix Streams: The Role of Spa rsity.

\nAbstract: Spectral functions of large matrices contain i mportant structural information about the underlying data\, and are thus b ecoming increasingly important to efficiently compute. Many times\, large matrices representing real-world data are \\emph{sparse} or \\emph{doubly sparse} (i.e.\, sparse in both rows and columns)\, and are accessed as a \ \emph{stream} of updates\, typically organized in \\emph{row-order}. In th is setting\, where space (memory) is the limiting resource\, all known alg orithms require space that is polynomial in the dimension of the matrix\, even for sparse matrices. We address this challenge by providing the first algorithms whose space requirement is \\emph{independent of the matrix di mension}\, assuming the matrix is doubly-sparse and presented in row-order .

\nIn addition\, we prove that multiple passes are unavoidable in this setting and show extensions of our primary technique\, including a tr ade-off between space requirements and number of passes. Our algorithms ap proximate the Schatten p-norms\, which we use in turn to approximate other spectral functions\, such as logarithm of the determinant\, trace of matr ix inverse\, and Estrada index.

\nJoint work with Vladimir Braverma n\, Robert Krauthgamer and Roi Sinoff.

DTSTART;TZID=America/New_York:20201007T120000 DTEND;TZID=America/New_York:20201007T130000 LOCATION:https://wse.zoom.us/j/91450299380 SEQUENCE:0 SUMMARY:[Theory Seminar] Aditya Krishnan URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-aditya-kris hnan-2/ X-COST-TYPE:free END:VEVENT END:VCALENDAR