Nonlinear dimension reduction via outer Bi-Lipschitz extensions

Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev*, Ilya Razenshteyn

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

Abstract

We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a prioritized variant of the Johnson–Lindenstrauss lemma: given a set of points X ⊂ Rd of size N and a permutation (“priority ranking”) of X, there exists an embedding f of X into RO(log N) with distortion O(log log N) such that the point of rank j has only O(log3+ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(log log j). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in Rd, there exists a terminal dimension reduction embedding of Rd into Rd′, where d = O(log ε4 N), which preserves distances ∥x − ∥ between points x ∈ X and ∈ Rd, up to a multiplicative factor of 1 ± . This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages574-586
Number of pages13
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period6/25/186/29/18

Keywords

  • Bi-lipschitz extension
  • Dimension reduction
  • Metric embedding
  • Near-isometric maps
  • Prioritized johnson-lindenstrauss

ASJC Scopus subject areas

  • Software

Cite this

Mahabadi, S., Makarychev, K., Makarychev, Y., & Razenshteyn, I. (2018). Nonlinear dimension reduction via outer Bi-Lipschitz extensions. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 574-586). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188828
Mahabadi, Sepideh ; Makarychev, Konstantin ; Makarychev, Yury ; Razenshteyn, Ilya. / Nonlinear dimension reduction via outer Bi-Lipschitz extensions. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. editor / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. Association for Computing Machinery, 2018. pp. 574-586 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{7f35232e18994852a7849e66a4b9b849,
title = "Nonlinear dimension reduction via outer Bi-Lipschitz extensions",
abstract = "We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f ′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a prioritized variant of the Johnson–Lindenstrauss lemma: given a set of points X ⊂ Rd of size N and a permutation (“priority ranking”) of X, there exists an embedding f of X into RO(log N) with distortion O(log log N) such that the point of rank j has only O(log3+ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(log log j). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in Rd, there exists a terminal dimension reduction embedding of Rd into Rd′, where d′ = O(log ε4 N), which preserves distances ∥x − ∥ between points x ∈ X and ∈ Rd, up to a multiplicative factor of 1 ± . This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.",
keywords = "Bi-lipschitz extension, Dimension reduction, Metric embedding, Near-isometric maps, Prioritized johnson-lindenstrauss",
author = "Sepideh Mahabadi and Konstantin Makarychev and Yury Makarychev and Ilya Razenshteyn",
year = "2018",
month = "6",
day = "20",
doi = "10.1145/3188745.3188828",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "574--586",
editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",
booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

}

Mahabadi, S, Makarychev, K, Makarychev, Y & Razenshteyn, I 2018, Nonlinear dimension reduction via outer Bi-Lipschitz extensions. in M Henzinger, D Kempe & I Diakonikolas (eds), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 574-586, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 6/25/18. https://doi.org/10.1145/3188745.3188828

Nonlinear dimension reduction via outer Bi-Lipschitz extensions. / Mahabadi, Sepideh; Makarychev, Konstantin; Makarychev, Yury; Razenshteyn, Ilya.

STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. p. 574-586 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Nonlinear dimension reduction via outer Bi-Lipschitz extensions

AU - Mahabadi, Sepideh

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Razenshteyn, Ilya

PY - 2018/6/20

Y1 - 2018/6/20

N2 - We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f ′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a prioritized variant of the Johnson–Lindenstrauss lemma: given a set of points X ⊂ Rd of size N and a permutation (“priority ranking”) of X, there exists an embedding f of X into RO(log N) with distortion O(log log N) such that the point of rank j has only O(log3+ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(log log j). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in Rd, there exists a terminal dimension reduction embedding of Rd into Rd′, where d′ = O(log ε4 N), which preserves distances ∥x − ∥ between points x ∈ X and ∈ Rd, up to a multiplicative factor of 1 ± . This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.

AB - We introduce and study the notion of an outer bi-Lipschitz extension of a map between Euclidean spaces. The notion is a natural analogue of the notion of a Lipschitz extension of a Lipschitz map. We show that for every map f there exists an outer bi-Lipschitz extension f ′ whose distortion is greater than that of f by at most a constant factor. This result can be seen as a counterpart of the classic Kirszbraun theorem for outer bi-Lipschitz extensions. We also study outer bi-Lipschitz extensions of near-isometric maps and show upper and lower bounds for them. Then, we present applications of our results to prioritized and terminal dimension reduction problems, described next. We prove a prioritized variant of the Johnson–Lindenstrauss lemma: given a set of points X ⊂ Rd of size N and a permutation (“priority ranking”) of X, there exists an embedding f of X into RO(log N) with distortion O(log log N) such that the point of rank j has only O(log3+ε j) non-zero coordinates – more specifically, all but the first O(log3+ε j) coordinates are equal to 0; the distortion of f restricted to the first j points (according to the ranking) is at most O(log log j). The result makes a progress towards answering an open question by Elkin, Filtser, and Neiman about prioritized dimension reductions. We prove that given a set X of N points in Rd, there exists a terminal dimension reduction embedding of Rd into Rd′, where d′ = O(log ε4 N), which preserves distances ∥x − ∥ between points x ∈ X and ∈ Rd, up to a multiplicative factor of 1 ± . This improves a recent result by Elkin, Filtser, and Neiman. The dimension reductions that we obtain are nonlinear, and this nonlinearity is necessary.

KW - Bi-lipschitz extension

KW - Dimension reduction

KW - Metric embedding

KW - Near-isometric maps

KW - Prioritized johnson-lindenstrauss

UR - http://www.scopus.com/inward/record.url?scp=85049919796&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049919796&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188828

DO - 10.1145/3188745.3188828

M3 - Conference contribution

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 574

EP - 586

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

ER -

Mahabadi S, Makarychev K, Makarychev Y, Razenshteyn I. Nonlinear dimension reduction via outer Bi-Lipschitz extensions. In Henzinger M, Kempe D, Diakonikolas I, editors, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2018. p. 574-586. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/3188745.3188828