research-article

Public Access

Optimal terminal dimensionality reduction in Euclidean space

Authors:

Shyam Narayanan,

Jelani NelsonAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 1064 - 1069

https://doi.org/10.1145/3313276.3316307

Published: 23 June 2019 Publication History

PDF eReader

Abstract

Let ε∈(0,1) and X⊂^d be arbitrary with |X| having size n>1. The Johnson-Lindenstrauss lemma states there exists f:X→^m with m = O(ε⁻²logn) such that <table><tr><td> ∀ x∈ X ∀ y∈ X, ||x−y||₂ ≤ ||f(x)−f(y)||₂ ≤ (1+ε)||x−y||₂ . </td></tr></table> We show that a strictly stronger version of this statement holds, answering one of the main open questions posed by Mahabadi et al. in STOC 2018: “∀ y∈ X” in the above statement may be replaced with “∀ y∈^d”, so that f not only preserves distances within X, but also distances to X from the rest of space. Previously this stronger version was only known with the worse bound m = O(ε⁻⁴logn). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of Mahabadi et al.

References

[1]

{AK17} Noga Alon and Bo’az Klartag. Optimal compression of approximate inner products and dimension reduction. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 639–650, 2017.

Crossref

Google Scholar

[2]

{BLM13} Stephane Boucheron, Gabor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 1st edition, 2013.

Google Scholar

[3]

{Dir15} Sjoerd Dirksen. Tail bounds via generic chaining. Electron. J. Probab., 20(53):1–29, 2015.

Google Scholar

[4]

{Dir16} Sjoerd Dirksen. Dimensionality reduction with subgaussian matrices: a unified theory. Found. Comp. Math., 16(5):1367–1396, 2016.

Digital Library

Google Scholar

[5]

{EFN17} Michael Elkin, Arnold Filtser, and Ofer Neiman. Terminal embeddings. Theoretical Computer Science, 697:1–36, 2017.

Crossref

Google Scholar

[6]

{ JL84} William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189–206, 1984.

Crossref

Google Scholar

[7]

STOC ’19, June 23–26, 2019, Phoenix, AZ, USA Shyam Narayanan and Jelani Nelson

Google Scholar

[8]

{LN17} Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson-Lindenstrauss lemma. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2017.

Crossref

Google Scholar

[9]

{MMMR18} Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya P. Razenshteyn. Nonlinear dimension reduction via outer Bi-Lipschitz extensions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1088–1101, 2018.

Digital Library

Google Scholar

[10]

{Tal14} Michel Talagrand. Upper and lower bounds for stochastic processes: modern methods and classical problems. Springer, 2014.

Google Scholar

[11]

{Ver18} Roman Vershynin. High-dimensional probability: an introduction with applications in data science. Cambridge University Press, 2018.

Crossref

Google Scholar

[12]

{vN28} John von Neumann. Zur theorie der Gesellschaftsspiele. Math. Ann., 100:295–320, 1928.

Crossref

Google Scholar

Cited By

View all

Huang LLi JWu XMohar BShinkar IO'Donnell R(2024)On Optimal Coreset Construction for Euclidean (k,z)-ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649707(1594-1604)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649707
Zhang ZHuang ZTian ZLiu LXu XFeng Q(2024)On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean SpacesJournal of the Operations Research Society of China10.1007/s40305-023-00533-wOnline publication date: 22-Mar-2024
https://doi.org/10.1007/s40305-023-00533-w
Psarros IRohde D(2024)Random Projections for Curves in High DimensionsDiscrete & Computational Geometry10.1007/s00454-024-00710-5Online publication date: 11-Dec-2024
https://doi.org/10.1007/s00454-024-00710-5
Show More Cited By

Index Terms

Optimal terminal dimensionality reduction in Euclidean space
1. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Dimensionality reduction
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry
    2. Random projections and metric embeddings

Recommendations

Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma
STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

We show that for n points in d-dimensional Euclidean space, a data oblivious random projection of the columns onto m∈ O((logk+loglogn)ε⁻⁶log1/ε) dimensions is sufficient to approximate the cost of all k-means clusterings up to a multiplicative (1±ε) ...
Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Dimension reduction of metric data has become a useful technique with numerous applications. The celebrated Johnson-Lindenstrauss lemma states that any n-point subset of Euclidean space can be embedded in O(ε⁻² log n)-dimension with (1 + ε)-distortion. ...
Geometrically local embedding in manifolds for dimension reduction

In this paper, geometrically local embedding (GLE) is presented to discover the intrinsic structure of manifolds as a method in nonlinear dimension reduction. GLE is able to reveal the inner features of the input data in the lower dimension space while ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
594
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)10

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Huang LLi JWu XMohar BShinkar IO'Donnell R(2024)On Optimal Coreset Construction for Euclidean (k,z)-ClusteringProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649707(1594-1604)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649707
Zhang ZHuang ZTian ZLiu LXu XFeng Q(2024)On the Budgeted Priority p-Median Problem in High-Dimensional Euclidean SpacesJournal of the Operations Research Society of China10.1007/s40305-023-00533-wOnline publication date: 22-Mar-2024
https://doi.org/10.1007/s40305-023-00533-w
Psarros IRohde D(2024)Random Projections for Curves in High DimensionsDiscrete & Computational Geometry10.1007/s00454-024-00710-5Online publication date: 11-Dec-2024
https://doi.org/10.1007/s00454-024-00710-5
Chiclana RIwen MRoach M(2024)On outer bi-Lipschitz extensions of linear Johnson-Lindenstrauss embeddings of subsets of $$\mathbb {R}^N$$Numerische Mathematik10.1007/s00211-024-01437-4156:6(2111-2130)Online publication date: 4-Nov-2024
https://doi.org/10.1007/s00211-024-01437-4
Bucarelli MLarsen MSchwiegelshohn CToftrup MOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)On generalization bounds for projective clusteringProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669262(71723-71754)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3669262
Woodruff DZhong PZhou SOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Near-optimal k-clustering in the sliding window modelProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667116(22934-22960)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667116
Huang LJiang SLou JKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)The power of uniform sampling for k-medianProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618974(13933-13956)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618974
Cohen-Addad VSaulpic DSchwiegelshohn C(2023)Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00066(1105-1130)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00066
Filtser AGottlieb LKrauthgamer R(2023)Labelings vs. Embeddings: On Distributed and Prioritized Representations of DistancesDiscrete & Computational Geometry10.1007/s00454-023-00565-2Online publication date: 15-Sep-2023
https://doi.org/10.1007/s00454-023-00565-2
Schwiegelshohn C(2023)Fitting Data on a Grain of RiceAlgorithmic Aspects of Cloud Computing10.1007/978-3-031-49361-4_13(1-8)Online publication date: 5-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-49361-4_13
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound

Geometrically local embedding in manifolds for dimension reduction