Embeddings of Schatten Norms with Applications to Data Streams

DOI10.4230/LIPICS.ICALP.2017.60zbMATH Open1455.46025arXiv1702.05626OpenAlexW2593931896MaRDI QIDQ5111391FDOQ5111391

David P. Woodruff, Yi Li

Publication date: 27 May 2020

Abstract: Given an $nimesd$ matrix $A$, its Schatten-$p$ norm, $pgeq1$, is defined as $|A{|}_p=left(su{m}_{i=1}^{extrmrank(A)}sigm{a}_i(A{)}^{p}ight{)}^{1/p}$, where $sigm{a}_i(A)$ is the $i$-th largest singular value of $A$. These norms have been studied in functional analysis in the context of non-commutative $el{l}_p$-spaces, and recently in data stream and linear sketching models of computation. Basic questions on the relations between these norms, such as their embeddability, are still open. Specifically, given a set of matrices $A^1,ldots,A^{operatornamepoly(nd)}inmathbb{R}^{nimesd}$, suppose we want to construct a linear map $L$ such that $L(A^i)inmathbb{R}^{n^{\prime }imes{d}^{\prime }}$ for each $i$, where $n^{\prime }leqn$ and $d^{\prime }leqd$, and further, $|A^i{|}_{p}leq|L(A^i){|}_{q}leq{D}_{p,q}|A^i{|}_p$ for a given approximation factor $D_{p,q}$ and real number $qgeq1$. Then how large do $n^{\prime }$ and $d^{\prime }$ need to be as a function of $D_{p,q}$? We nearly resolve this question for every $p,qgeq1$, for the case where $L(A^i)$ can be expressed as $Rcdot{A}^{i}cdotS$, where $R$ and $S$ are arbitrary matrices that are allowed to depend on $A^1,ldots,A^t$, that is, $L(A^i)$ can be implemented by left and right matrix multiplication. Namely, for every $p,qgeq1$, we provide nearly matching upper and lower bounds on the size of $n^{\prime }$ and $d^{\prime }$ as a function of $D_{p,q}$. Importantly, our upper bounds are {it oblivious}, meaning that $R$ and $S$ do not depend on the $A^i$, while our lower bounds hold even if $R$ and $S$ depend on the $A^i$. As an application of our upper bounds, we answer a recent open question of Blasiok et al. about space-approximation trade-offs for the Schatten $1$-norm, showing in a data stream it is possible to estimate the Schatten-$1$ norm up to a factor of $Dgeq1$ using $ildeO(min(n,d{)}^2/D^4)$ space.

Full work available at URL: https://arxiv.org/abs/1702.05626

zbMATH Keywords

sketchingembeddingsmatrix normsdata stream algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85)

Cited In (5)

• Querying a Matrix Through Matrix-Vector Products.
• Title not available (Why is that?)
• Smoothness of Schatten norms and sliding-window matrix streams
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Impossibility of dimension reduction in the nuclear norm

This page was built for publication: Embeddings of Schatten Norms with Applications to Data Streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111391)