Embeddings of Schatten norms with applications to data streams

DOI10.4230/LIPICS.ICALP.2017.60MaRDI QIDQ5111391zbMATH OpenOpenAlexFDO

Authors Yi Li, David P. Woodruff

Publication date 27 May 2020

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)

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.

Recommendations

• On approximating matrix norms in data streams
• On approximating functions of the singular values in a stream
• On sketching matrix norms and the top singular vector
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• On sketching the \(q\) to \(p\) norms

Cited in

(10)

• On approximating functions of the singular values in a stream
• Querying a Matrix Through Matrix-Vector Products.
• Sketching and embedding are equivalent for norms
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• On sketching matrix norms and the top singular vector
• On approximating matrix norms in data streams
• Streaming symmetric norms via measure concentration
• Smoothness of Schatten norms and sliding-window matrix streams
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• On sketching the \(q\) to \(p\) norms

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)