Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension

摘要: Spectral functions of large matrices contains important structural information about the underlying data, and is thus becoming increasingly important. Many times, representing real-world data are \emph{sparse} or \emph{doubly sparse} (i.e., sparse in both rows columns), accessed as a \emph{stream} updates, typically organized \emph{row-order}. In this setting, where space (memory) limiting resource, all known algorithms require that polynomial dimension matrix, even for matrices. We address challenge by providing first whose requirement \emph{independent matrix dimension}, assuming doubly-sparse presented row-order. Our approximate Schatten $p$-norms, which we use turn to other spectral functions, such logarithm determinant, trace inverse, Estrada index. validate these theoretical performance bounds numerical experiments on social networks. further prove multiple passes unavoidable show extensions our primary technique, including trade-off between requirements number passes.