Speaker: Aditya Krishnan

\nAffiliation: Johns Hopkins U
niversity

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

\nAbstract:

\nSpectral functions of large matrices contai
n important structural information about the underlying data\, and are thu
s becoming increasingly important to efficiently compute. Many times\, lar
ge matrices representing real-world data are *sparse* or *doubly
sparse* (i.e.\, sparse in both rows and columns)\, and are accessed a
s a *stream* of updates\, typically organized in *row-order*
. In this setting\, where space (memory) is the limiting resource\, all kn
own algorithms require space that is polynomial in the dimension of the ma
trix\, even for sparse matrices. We address this challenge by providing th
e first algorithms whose space requirement is *independent of the matri
x dimension*\, assuming the matrix is doubly-sparse and presented in r
ow-order.

In addition\, we prove that multiple passes are unavoida ble in this setting and show extensions of our primary technique\, includi ng a trade-off between space requirements and number of passes. Our algori thms approximate the Schatten p-norms\, which we use in turn to approximat e other spectral functions\, such as logarithm of the determinant\, trace of matrix inverse\, and Estrada index.

\nJoint work with Vladimir Br averman\, Robert Krauthgamer and Roi Sinoff.

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