BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20//
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Johns Hopkins Algorithms and Complexity
X-WR-CALDESC:
X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:STANDARD
DTSTART:20221106T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20230312T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ai1ec-317@www.cs.jhu.edu/~mdinitz/theory
DTSTAMP:20230201T093438Z
CATEGORIES:
CONTACT:
DESCRIPTION:Speaker: Aditya Krishnan\nAffiliation: Johns Hopkins University
\nTitle: Schatten Norms in Matrix Streams: The Role of Sparsity\nAbstract:
\nSpectral functions of large matrices contain important structural inform
ation about the underlying data\, and are thus becoming increasingly impor
tant to efficiently compute. Many times\, large matrices representing real
-world data are sparse or doubly sparse (i.e.\, sparse in both rows and co
lumns)\, and are accessed as a stream of updates\, typically organized in
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 pro
viding the first algorithms whose space requirement is independent of the
matrix dimension\, assuming the matrix is doubly-sparse and presented in r
ow-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 Braverman\, Robe
rt 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
X-ALT-DESC;FMTTYPE=text/html:\\n\\n\\n\\n\\nSpeaker: Adit
ya Krishnan

\nAffiliation: Johns Hopkins University

\nTitle: Sc
hatten Norms in Matrix Streams: The Role of Sparsity

\nAbstract:

\nSpectral functions of large matrices contain important structural info
rmation about the underlying data\, and are thus becoming increasingly imp
ortant to efficiently compute. Many times\, large matrices representing re
al-world data are *sparse* or *doubly sparse* (i.e.\, sparse
in both rows and columns)\, and are accessed as a *stream* of upda
tes\, typically organized in *row-order*. In this setting\, where s
pace (memory) is the limiting resource\, all known algorithms require spac
e that is polynomial in the dimension of the matrix\, even for sparse matr
ices. We address this challenge by providing the first algorithms whose sp
ace requirement is *independent of the matrix dimension*\, assuming
the matrix is doubly-sparse and presented in row-order.

\nIn additi
on\, we prove that multiple passes are unavoidable in this setting and sho
w extensions of our primary technique\, including a trade-off between spac
e requirements and number of passes. Our algorithms approximate the Schatt
en p-norms\, which we use in turn to approximate other spectral functions\
, such as logarithm of the determinant\, trace of matrix inverse\, and Est
rada index.

\nJoint work with Vladimir Braverman\, Robert Krauthgame
r and Roi Sinoff.

\n
END:VEVENT
END:VCALENDAR