Two-Sided Kirszbraun Theorem

Authors Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.13.pdf
  • Filesize: 0.71 MB
  • 14 pages

Document Identifiers

Author Details

Arturs Backurs
  • Toyota Technological Institute at Chicago (TTIC), IL, USA
Sepideh Mahabadi
  • Toyota Technological Institute at Chicago (TTIC), IL, USA
Konstantin Makarychev
  • Northwestern University, Evanston, IL, USA
Yury Makarychev
  • Toyota Technological Institute at Chicago (TTIC), IL, USA

Cite AsGet BibTex

Arturs Backurs, Sepideh Mahabadi, Konstantin Makarychev, and Yury Makarychev. Two-Sided Kirszbraun Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.13

Abstract

In this paper, we prove a two-sided variant of the Kirszbraun theorem. Consider an arbitrary subset X of Euclidean space and its superset Y. Let f be a 1-Lipschitz map from X to ℝ^m. The Kirszbraun theorem states that the map f can be extended to a 1-Lipschitz map ̃ f from Y to ℝ^m. While the extension ̃ f does not increase distances between points, there is no guarantee that it does not decrease distances significantly. In fact, ̃ f may even map distinct points to the same point (that is, it can infinitely decrease some distances). However, we prove that there exists a (1 + ε)-Lipschitz outer extension f̃:Y → ℝ^{m'} that does not decrease distances more than "necessary". Namely, ‖f̃(x) - f̃(y)‖ ≥ c √{ε} min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) for some absolutely constant c > 0. This bound is asymptotically optimal, since no L-Lipschitz extension g can have ‖g(x) - g(y)‖ > L min(‖x-y‖, inf_{a,b ∈ X} (‖x - a‖ + ‖f(a) - f(b)‖ + ‖b-y‖)) even for a single pair of points x and y. In some applications, one is interested in the distances ‖f̃(x) - f̃(y)‖ between images of points x,y ∈ Y rather than in the map f̃ itself. The standard Kirszbraun theorem does not provide any method of computing these distances without computing the entire map ̃ f first. In contrast, our theorem provides a simple approximate formula for distances ‖f̃(x) - f̃(y)‖.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing
Keywords
  • Kirszbraun theorem
  • Lipschitz map
  • Outer-extension
  • Two-sided extension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, Ramamoorthi Ravi, and Anastasios Sidiropoulos. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of the Symposium on Discrete Algorithms, volume 5, pages 119-128, 2005. Google Scholar
  2. Yair Bartal, Ben Recht, and Leonard J Schulman. Dimensionality reduction: beyond the Johnson-Lindenstrauss bound. In Proceedings of the Symposium on Discrete Algorithms, pages 868-887. SIAM, 2011. Google Scholar
  3. Armin Biess, Aryeh Kontorovich, Yury Makarychev, and Hanan Zaichyk. Regression via Kirszbraun extension with applications to imitation learning. CoRR, abs/1905.11930, 2019. URL: http://arxiv.org/abs/1905.11930.
  4. Yair Censor, Aviv Gibali, and Simeon Reich. Strong convergence of subgradient extragradient methods for the variational inequality problem in Hilbert space. Optimization Methods and Software, 26(4-5):827-845, 2011. Google Scholar
  5. Nishant Chandgotia, Igor Pak, and Martin Tassy. Kirszbraun-type theorems for graphs. Journal of Combinatorial Theory, Series B, 137:10-24, 2019. Google Scholar
  6. Timothy Chu, Gary L Miller, and Donald R Sheehy. Exact computation of a manifold metric, via lipschitz embeddings and shortest paths on a graph. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 411-425. SIAM, 2020. Google Scholar
  7. Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient regression in metric spaces via approximate Lipschitz extension. IEEE Transactions on Information Theory, 63(8):4838-4849, 2017. Google Scholar
  8. William Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189-206, 1984. Google Scholar
  9. Mojzesz D. Kirszbraun. Über die zusammenziehende und Lipschitzsche Transformationen. Fundamenta Mathematicae, 22:77-108, 1934. Google Scholar
  10. James R Lee and Assaf Naor. Extending Lipschitz functions via random metric partitions. Inventiones mathematicae, 160(1):59-95, 2005. Google Scholar
  11. Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245, 1995. Google Scholar
  12. Steven H Low. Analytical methods for network congestion control. Synthesis Lectures on Communication Networks, 10(1):1-213, 2017. Google Scholar
  13. Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988. Google Scholar
  14. Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Nonlinear dimension reduction via outer bi-Lipschitz extensions. In Proceedings of the Symposium on Theory of Computing, pages 1088-1101, 2018. Google Scholar
  15. Konstantin Makarychev and Yury Makarychev. A union of Euclidean metric spaces is Euclidean. Discrete Analysis, 14, 2016. Google Scholar
  16. Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of Johnson-Lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the Symposium on Theory of Computing, pages 1027-1038, 2019. Google Scholar
  17. Manor Mendel and Assaf Naor. Euclidean quotients of finite metric spaces. Advances in Mathematics, 189(2):451-494, 2004. Google Scholar
  18. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1–3):1-336, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail