Bounds on Dimension Reduction in the Nuclear Norm

Abstract:

e w c o m m a n d s c h s s c r i p t s t y l e {m a t h s f S}_{1}

For all

n g e 1

, we give an explicit construction of

m i m e s m

matrices

A_{1}, l d o t s, A_{n}

with

m = 2^{l f l o o r n / 2 f l o o r}

such that for any

d

and

d i m e s d

matrices

A'_{1}, l d o t s, A'_{n}

that satisfy [ |A'_i-A'_j|_{schs} ,leq, |A_i-A_j|_{schs},leq, (1+delta) |A'_i-A'_j|_{schs} ] for all

i, j i n 1, l d o t s, n

and small enough

d e l t a = O (n^{- c})

, where

c > 0

is a universal constant, it must be the case that

d g e 2^{l f l o o r n / 2 f l o o r - 1}

. This stands in contrast to the metric theory of commutative

e l l_{p}

spaces, as it is known that for any

p g e q 1

, any

n

points in

e l l_{p}

embed exactly in

e l l_{p}^{d}

for

d = n (n - 1) / 2

. Our proof is based on matrices derived from a representation of the Clifford algebra generated by

n

anti-commuting Hermitian matrices that square to identity, and borrows ideas from the analysis of nonlocal games in quantum information theory.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: Bounds on Dimension Reduction in the Nuclear Norm