Impossibility of dimension reduction in the nuclear norm

DOI10.1007/s00454-019-00162-2zbMath1442.46017arXiv1710.08896OpenAlexW2996404163WikidataQ101411134 ScholiaQ101411134MaRDI QIDQ2291451

Gideon Schechtman, Assaf Naor, Gilles Pisier

Publication date: 31 January 2020

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1710.08896

zbMATH Keywords

dimension reductionLipschitz quotientnuclear normmetric embeddingbi-Lipschitz distortionMarkov convexitySchatten-von Neumannquantum dimension reductionSchatten-von Neumann trace class

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Nonlinear classification of Banach spaces; nonlinear quotients (46B80) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Geometric embeddings of metric spaces (30L05) Lipschitz and coarse geometry of metric spaces (51F30) Metric embeddings as related to computational problems and algorithms (68R12)

Related Items

Estimates on the Markov convexity of Carnot groups and quantitative nonembeddability, \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\), Bounds on Dimension Reduction in the Nuclear Norm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discrete Riesz transforms and sharp metric \(X_p\) inequalities
• Entropy-based bounds on dimension reduction in \(L^1\)
• Vertical versus horizontal Poincaré inequalities on the Heisenberg group
• Cuts, trees and \(\ell_1\)-embeddings of graphs
• The energy of graphs and matrices
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Markov chains, Riesz transforms and Lipschitz maps
• A trace inequality of John von Neumann
• Martingales with values in uniformly convex spaces
• The dimension of almost spherical sections of convex bodies
• Sharp uniform convexity and smoothness inequalities for trace norms
• Problems and results in extremal combinatorics. I.
• Lectures on analysis on metric spaces
• Vertical perimeter versus horizontal perimeter
• Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)
• Euclidean quotients of finite metric spaces
• Approximation of zonoids by zonotopes
• Proportional concentration phenomena on the sphere
• The geometry of graphs and some of its algorithmic applications
• On the distortion required for embedding finite metric spaces into normed spaces
• Markov convexity and local rigidity of distorted metrics
• An introduction to the Ribe program
• Affine approximation of Lipschitz functions and nonlinear quotients
• Ahlfors \(Q\)-regular spaces with arbitrary \(Q>1\) admitting weak Poincaré inequality
• Heat flow and quantitative differentiation
• Weighted nuclear norm minimization and its applications to low level vision
• Nonlinear spectral calculus and super-expanders
• The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
• On metric Ramsey-type phenomena
• Vector-valued Littlewood--Paley--Stein theory for semigroups
• \(c_ p\)
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion
• Exact matrix completion via convex optimization
• Handbook of Robust Low-Rank and Sparse Matrix Decomposition
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• Graph Energy
• Limitations on Quantum Dimensionality Reduction
• Embedding Subspaces of L 1 into l N 1
• METRIC DIMENSION REDUCTION: A SNAPSHOT OF THE RIBE PROGRAM
• Extensions of Lipschitz mappings into a Hilbert space
• DIAMOND GRAPHS AND SUPER-REFLEXIVITY
• Markov Type of Alexandrov Spaces of Non‐Negative Curvature Shin‐Ichi Ohta
• METRIC INEQUALITIES
• On the impossibility of dimension reduction in l ₁
• Nearest-neighbor-preserving embeddings
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Almost Euclidean Quotient Spaces of Subspaces of a Finite-Dimensional Normed Space
• On the Dimension of Almost Hilbertian Subspaces of Quotient Spaces
• Finite dimensional subspaces of $L_{p}$
• Littlewood-Paley theory for functions with values in uniformly convex spaces
• A spectral gap precludes low-dimensional embeddings
• On Type of Metric Spaces
• Embeddings of Schatten Norms with Applications to Data Streams
• Bounds on Dimension Reduction in the Nuclear Norm
• Data-dependent hashing via nonlinear spectral gaps
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Simpler Approach to Matrix Completion
• Near Linear Lower Bound for Dimension Reduction in L1
• Uniformly Convex Spaces
• Formes linéaires sur un anneau d'opérateurs
• Trees and Markov convexity
• Finite-dimensional subspaces of uniformly convex and uniformly smooth Banach lattices and trace classes $S_{p}$
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Bilipschitz embeddings of metric spaces into space forms