Johns Hopkins Algorithms and Complexity
https://www.cs.jhu.edu/~mdinitz/theory
America/New_York
America/New_York
America/New_York
20221106T020000
-0400
-0500
EST
20220313T020000
-0500
-0400
20230312T020000
EDT
ai1ec-332@www.cs.jhu.edu/~mdinitz/theory
20221001T214346Z
Speaker: Aditya Krishnan
Affiliation: Johns Hopkins University
Title: Schatten Norms in Matrix Streams: The Role of Sparsity.
Abstract: Spectral functions of large matrices contain important structural information about the underlying data, and are thus becoming 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 this setting, where space (memory) is the limiting resource, all known algorithms 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 dimension}, assuming the matrix is doubly-sparse and presented in row-order.
In addition, we prove that multiple passes are unavoidable in this setting and show extensions of our primary technique, including a trade-off between space requirements and number of passes. Our algorithms approximate the Schatten p-norms, which we use in turn to approximate other spectral functions, such as logarithm of the determinant, trace of matrix inverse, and Estrada index.
Joint work with Vladimir Braverman, Robert Krauthgamer and Roi Sinoff.
20201007T120000
20201007T130000
https://wse.zoom.us/j/91450299380
0
[Theory Seminar] Aditya Krishnan
free