Bounds on Dimension Reduction in the Nuclear Norm

Oded Regev, Thomas Vidick

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Mathematics
PublisherSpringer
Pages279-299
Number of pages21
DOIs
StatePublished - 2020

Publication series

NameLecture Notes in Mathematics
Volume2266
ISSN (Print)0075-8434
ISSN (Electronic)1617-9692

ASJC Scopus subject areas

  • Algebra and Number Theory

Fingerprint Dive into the research topics of 'Bounds on Dimension Reduction in the Nuclear Norm'. Together they form a unique fingerprint.

Cite this