# Embeddings of Schatten Norms with Applications to Data Streams

arXiv: https://arxiv.org/abs/1702.05626 · HTML: https://mlsanity.com/paper/1702.05626/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2017.

## Built on by (most cited first, 2 of 2)

- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)

## Abstract (arXiv)

Given an n × d matrix A, its Schatten-p norm, p ≥ 1, is defined as |A|p = left (sumi=1^textrmrank(A)σi(A)p right )1/p, where σ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 ℓ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 A1, ldots, A^operatornamepoly(nd) ∈ ℝn × d, suppose we want to construct a linear map L such that L(Ai) ∈ ℝn' × d' for each i, where n' ≤ n and d' ≤ d, and further, |Ai|p ≤ |L(Ai)|q ≤ Dp,q |Ai|p for a given approximation factor Dp,q and real number q ≥ 1. Then how large do n' and d' need to be as a function of Dp,q? We nearly resolve this question for every p, q ≥ 1, for the case where L(Ai) can be expressed as R · Ai · S, where R and S are arbitrary matrices that are allowed to depend on A1, ldots, At, that is, L(Ai) can be implemented by left and right matrix multiplication. Namely, for every p, q ≥ 1, we provide nearly matching upper and lower bounds on the size of n' and d' as a function of Dp,q. Importantly, our upper bounds are it oblivious, meaning that R and S do not depend on the Ai, while our lower bounds hold even if R and S depend on the Ai. 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 D ≥ 1 using tildeO(min(n,d)2/D4) space.