CaltechAUTHORS
  A Caltech Library Service

Bounds on Dimension Reduction in the Nuclear Norm

Regev, Oded and Vidick, Thomas (2020) Bounds on Dimension Reduction in the Nuclear Norm. In: Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 2017-2019 Volume II. Lecture Notes in Mathematics. No.2266. Springer , Cham, pp. 279-299. ISBN 978-3-030-46761-6. https://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301

[img] PDF - Submitted Version
See Usage Policy.

340Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301

Abstract

For all n ≥ 1, we give an explicit construction of m × m matrices A_1,…,A_n with m = 2^([n/2]) such that for any d and d × d matrices A′_1,…,A′_n that satisfy ∥A_′i−A′_j∥S_1 ≤ ∥A_i−A_j∥S_1 ≤ (1+δ)∥A′_i−A′_j∥S_1 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 ℓ^d_p 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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1007/978-3-030-46762-3_13DOIArticle
https://arxiv.org/abs/1901.09480arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2020 Springer Nature Switzerland AG. First Online: 09 July 2020. The author “Oded Regev” was supported by the Simons Collaboration on Algorithms and Geometry and by the National Science Foundation (NSF) under Grant No. CCF-1814524. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF. The author “Thomas Vidick” was supported by NSF CAREER Grant CCF-1553477, a CIFAR Azrieli Global Scholar award, and the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). We are grateful to IPAM and the organizers of the workshop “Approximation Properties in Operator Algebras and Ergodic Theory” where this work started. We also thank Assaf Naor for useful comments and encouragement.
Group:Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Simons Collaboration on Algorithms and GeometryUNSPECIFIED
NSFCCF-1814524
NSFCCF-1553477
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1733907
Simons FoundationUNSPECIFIED
Series Name:Lecture Notes in Mathematics
Issue or Number:2266
Record Number:CaltechAUTHORS:20190320-095834301
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190320-095834301
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93981
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 17:06
Last Modified:29 Jul 2020 17:59

Repository Staff Only: item control page