$$\varepsilon $$ -Isometric Dimension Reduction for Incompressible Subsets of $$\ell _p$$
Discrete & Computational Geometry - Trang 1-17 - 2023
Tóm tắt
Fix
$$p\in [1,\infty )$$
,
$$K\in (0,\infty )$$
, and a probability measure
$$\mu $$
. We prove that for every
$$n\in \mathbb {N}$$
,
$$\varepsilon \in (0,1)$$
, and
$$x_1,\ldots ,x_n\in L_p(\mu )$$
with
$$\big \Vert \max _{i\in \{1,\ldots ,n\}} |x_i| \big \Vert _{L_p(\mu )} \le K$$
, there exist
$$d\le \frac{32e^2 (2K)^{2p}\log n}{\varepsilon ^2}$$
and vectors
$$y_1,\ldots , y_n \in \ell _p^d$$
such that
$$\begin{aligned} {\forall }\,\,i,j\in \{1,\ldots ,n\}, \quad \Vert x_i-x_j\Vert ^p_{L_p(\mu )}-\varepsilon\le & {} \Vert y_i-y_j\Vert _{\ell _p^d}^p\le \Vert x_i-x_j\Vert ^p_{L_p(\mu )}+\varepsilon . \end{aligned}$$
Moreover, the argument implies the existence of a greedy algorithm which outputs
$$\{y_i\}_{i=1}^n$$
after receiving
$$\{x_i\}_{i=1}^n$$
as input. The proof relies on a derandomized version of Maurey’s empirical method (1981) combined with a combinatorial idea of Ball (1990) and a suitable change of measure. Motivated by the above embedding, we introduce the notion of
$$\varepsilon $$
-isometric dimension reduction of the unit ball
$${\textbf {B}}_E$$
of a normed space
$$(E,\Vert \cdot \Vert _E)$$
and we prove that
$${\textbf {B}}_{\ell _p}$$
does not admit
$$\varepsilon $$
-isometric dimension reduction by linear operators for any value of
$$p\ne 2$$
.
Tài liệu tham khảo
Achlioptas, D.: Database-friendly random projections: Johnson–Lindenstrauss with binary coins. J. Comput. Syst. Sci. 66, 671–687 (2003)
Ailon, N., Chazelle, B.: The fast Johnson–Lindenstrauss transform and approximate nearest neighbors. SIAM J. Comput. 39(1), 302–322 (2009)
Ailon, N., Liberty, E.: An almost optimal unrestricted fast Johnson–Lindenstrauss transform. ACM Trans. Algorithms 9(3), # 21 (2013)
Arias-de Reyna, J., Ball, K., Villa, R.: Concentration of the distance in finite-dimensional normed spaces. Mathematika 45(2), 245–252 (1998)
Arriaga, R.I., Vempala, S.: An algorithmic theory of learning: robust concepts and random projection. In: 40th Annual Symposium on Foundations of Computer Science (New York 1999), pp. 616–623. IEEE Computer Society, Los Alamitos (1999)
Ball, K.: Isometric embedding in \(l_p\)-spaces. Eur. J. Combin. 11(4), 305–311 (1990)
Barman, S.: Approximating Nash equilibria and dense subgraphs via an approximate version of Carathéodory’s theorem. SIAM J. Comput. 47(3), 960–981 (2018)
Bartal, Y., Gottlieb, L.-A.: Approximate nearest neighbor search for \(\ell _p\)-spaces \((2<p<\infty )\) via embeddings. Theor. Comput. Sci. 757, 27–35 (2019)
Bourgain, J., Dirksen, S., Nelson, J.: Toward a unified theory of sparse dimensionality reduction in Euclidean space. Geom. Funct. Anal. 25(4), 1009–1088 (2015)
Brinkman, B., Charikar, M.: On the impossibility of dimension reduction in \(l_1\). J. ACM 52(5), 766–788 (2005)
Combettes, C.W., Pokutta, S.: Revisiting the approximate Carathéodory problem via the Frank–Wolfe algorithm. Math. Program. 197(1), 191–214 (2023)
Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60–65 (2003)
Dirksen, S.: Dimensionality reduction with subgaussian matrices: a unified theory. Found. Comput. Math. 16(5), 1367–1396 (2016)
Frankl, P., Maehara, H.: The Johnson–Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B 44(3), 355–362 (1988)
Gordon, Y.: On Milman’s inequality and random subspaces which escape through a mesh in \({R}^n\). In: Geometric Aspects of Functional Analysis (1986/1987). Lecture Notes in Mathematics, vol. 1317, pp. 84–106. Springer, Berlin (1988)
Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: 30th Annual ACM Symposiumon Theory of Computing (Dallas 1998), pp. 604–613. ACM, New York (1999)
Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), # 31 (2007)
Ivanov, G.: Approximate Carathéodory’s theorem in uniformly smooth Banach spaces. Discrete Comput. Geom. 66(1), 273–280 (2021)
Jacques, L.: A quantized Johnson–Lindenstrauss lemma: the finding of Buffon’s needle. IEEE Trans. Inf. Theory 61(9), 5012–5027 (2015)
Jacques, L.: Small width, low distortions: quantized random embeddings of low-complexity sets. IEEE Trans. Inf. Theory 63(9), 5477–5495 (2017)
Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability (New Haven 1982). Contemporary Mathematics, vol. 26, pp. 189–206. American Mathematical Society, Providence (1984)
Johnson, W.B., Naor, A.: The Johnson–Lindenstrauss lemma almost characterizes Hilbert space, but not quite. Discrete Comput. Geom. 43(3), 542–553 (2010)
Johnson, W.B., Schechtman, G.: Finite dimensional subspaces of \(L_p\). In: Handbook of the Geometry of Banach Spaces, vol. I, pp. 837–870. North-Holland, Amsterdam (2001)
Kane, D.M., Nelson, J.: Sparser Johnson–Lindenstrauss transforms. J. ACM 61(1), # 4 (2014)
Kashin, B., Kosov, E., Limonova, I., Temlyakov, V.: Sampling discretization and related problems. J. Complex. 71, # 101653 (2022)
Klartag, B., Mendelson, S.: Empirical processes and random projections. J. Funct. Anal. 225(1), 229–245 (2005)
Krahmer, F., Ward, R.: New and improved Johnson–Lindenstrauss embeddings via the restricted isometry property. SIAM J. Math. Anal. 43(3), 1269–1281 (2011)
Ledoux, M., Talagrand, M.: Probability in Banach Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 23. Springer, Berlin (1991)
Lee, J.R., Mendel, M., Naor, A.: Metric structures in \(L_1\): dimension, snowflakes, and average distortion. Eur. J. Combin. 26(8), 1180–1190 (2005)
Lee, J.R., Naor, A.: Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\). Geom. Funct. Anal. 14(4), 745–747 (2004)
Liaw, C., Mehrabian, A., Plan, Y., Vershynin, R.: A simple tool for bounding the deviation of random matrices on geometric sets. In: Geometric Aspects of Functional Analysis. Lecture Notes in Mathematics, vol. 2169, pp. 277–299. Springer, Cham (2017)
Matoušek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math. 93, 333–344 (1996)
Matoušek, J.: On variants of the Johnson–Lindenstrauss lemma. Random Struct. Algorithms 33(2), 142–156 (2008)
Maurey, B.: Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces \(L^{p}\). Astérisque, vol. 11. Société Mathématique de France, Paris (1974)
Mirrokni, V., Leme, R.P., Vladu, A., Wong, S.-C.: Tight bounds for approximate Carathéodory and beyond. In: 34th International Conference on Machine Learning (Sydney 2017). Proceedings of Machine Learning Research, vol. 70, pp. 2440–2448 (2017). http://JMLR.org
Naor, A.: Metric dimension reduction: a snapshot of the Ribe program. In: International Congress of Mathematicians (Rio de Janeiro 2018), vol. I. Plenary Lectures, pp. 759–837. World Scientific, Hackensack (2018)
Naor, A., Pisier, G., Schechtman, G.: Impossibility of dimension reduction in the nuclear norm. Discrete Comput. Geom. 63(2), 319–345 (2020)
Ostrovskii, M.I.: Metric Embeddings: Bilipschitz and Coarse Embeddings into Banach Spaces. De Gruyter Studies in Mathematics, vol. 49. De Gruyter, Berlin (2013)
Pisier, G.: Remarques sur un résultat non publié de B. Maurey. In: Seminar on Functional Analysis, 1980–1981, # 5. École Polytech., Palaiseau (1981)
Plan, Y., Vershynin, R.: Dimension reduction by random hyperplane tessellations. Discrete Comput. Geom. 51(2), 438–461 (2014)
Regev, O., Vidick, T.: Bounds on dimension reduction in the nuclear norm. In: Geometric Aspects of Functional Analysis, vol. II. Lecture Notes in Mathematics, vol. 2266, pp. 279–299. Springer, Cham (2020)
Schechtman, G.: Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200(1), 125–135 (2006)
Schechtman, G., Zinn, J.: On the volume of the intersection of two \(L^n_p\) balls. Proc. Am. Math. Soc. 110(1), 217–224 (1990)
Vershynin, R.: High-Dimensional Probability. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 47. Cambridge University Press, Cambridge (2018)