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 language | English (US) |
|---|---|
| Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |
| Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |
| Publisher | Association for Computing Machinery |
| Pages | 574-586 |
| Number of pages | 13 |
| ISBN (Electronic) | 9781450355599 |
| DOIs | |
| State | Published - Jun 20 2018 |
| Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018 |
Publication series
| Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
|---|---|
| ISSN (Print) | 0737-8017 |
Other
| Other | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
|---|---|
| Country | United States |
| City | Los Angeles |
| Period | 6/25/18 → 6/29/18 |
Keywords
- Bi-lipschitz extension
- Dimension reduction
- Metric embedding
- Near-isometric maps
- Prioritized johnson-lindenstrauss
ASJC Scopus subject areas
- Software
Cite this
}
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 proceeding › Conference 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 -