Polynomial-dimensional embedding conjecture for finite subsets of
Polynomial-dimensional embedding conjecture for finite subsets of
Let be a subset with . An embedding of into a normed space has distortion if distances are preserved up to a multiplicative factor with ratio . Embedding conjecture. Every -point subset of embeds with distortion into some normed space of dimension . This would improve the known lower-bound framework for dimensionality reduction into general normed spaces and would show that the lower bound of Matoušek cannot occur for subsets of ; the conjecture is presented as open.
Sources & referencesView supporting material
Primary source
Assaf Naor, “A spectral gap precludes low-dimensional embeddings”, arXiv:1611.08861 (2016).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.