TY - CHAP

T1 - Bounds on Dimension Reduction in the Nuclear Norm

AU - Regev, Oded

AU - Vidick, Thomas

N1 - Publisher Copyright:
© 2020, Springer Nature Switzerland AG.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - For all n ≥ 1, we give an explicit construction of m × m matrices A1, …, An with m = 2⌊n∕2⌋ such that for any d and d × d matrices A1′,…,An′ that satisfy∥Ai′−Aj′∥S1≤∥Ai−Aj∥S1≤(1+δ)∥Ai′−Aj′∥S1 (Formula presented) for all i, j ∈{1, …, n} and small enough δ = O(n−c), where c > 0 is a universal constant, it must be the case that d ≥ 2⌊n∕2⌋−1. This stands in contrast to the metric theory of commutative ℓp spaces, as it is known that for any p ≥ 1, any n points in ℓp embed exactly in ℓpd 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.

AB - For all n ≥ 1, we give an explicit construction of m × m matrices A1, …, An with m = 2⌊n∕2⌋ such that for any d and d × d matrices A1′,…,An′ that satisfy∥Ai′−Aj′∥S1≤∥Ai−Aj∥S1≤(1+δ)∥Ai′−Aj′∥S1 (Formula presented) for all i, j ∈{1, …, n} and small enough δ = O(n−c), where c > 0 is a universal constant, it must be the case that d ≥ 2⌊n∕2⌋−1. This stands in contrast to the metric theory of commutative ℓp spaces, as it is known that for any p ≥ 1, any n points in ℓp embed exactly in ℓpd 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.

UR - http://www.scopus.com/inward/record.url?scp=85088496496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85088496496&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-46762-3_13

DO - 10.1007/978-3-030-46762-3_13

M3 - Chapter

AN - SCOPUS:85088496496

T3 - Lecture Notes in Mathematics

SP - 279

EP - 299

BT - Lecture Notes in Mathematics

PB - Springer

ER -