The Johnson-Lindenstrauss lemma and the sphericity of some graphs

DOI10.1016/0095-8956(88)90043-3zbMath0675.05049OpenAlexW2983923309MaRDI QIDQ1121912

Hiroshi Maehara, Peter Frankl

Publication date: 1988

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(88)90043-3

zbMATH Keywords

smallest eigenvaluesphericityJohnson-Lindenstrauss lemma

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (37)

Johnson–Lindenstrauss Embeddings with Kronecker Structure ⋮ The geometry of graphs and some of its algorithmic applications ⋮ Fast Phase Retrieval from Local Correlation Measurements ⋮ Algebraic Distance Graphs and Rigidity ⋮ Embedding of trees in Euclidean spaces ⋮ An algorithmic theory of learning: robust concepts and random projection ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ The perfect marriage and much more: combining dimension reduction, distance measures and covariance ⋮ Efficient clustering on Riemannian manifolds: a kernelised random projection approach ⋮ Database-friendly random projections: Johnson-Lindenstrauss with binary coins. ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Dense fast random projections and Lean Walsh transforms ⋮ On variants of the Johnson–Lindenstrauss lemma ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Near-optimal encoding for sigma-delta quantization of finite frame expansions ⋮ Dimensionality reduction with subgaussian matrices: a unified theory ⋮ On embedding of graphs into Euclidean spaces of small dimension ⋮ Fast, linear time, \(m\)-adic hierarchical clustering for search and retrieval using the Baire metric, with linkages to generalized ultrametrics, hashing, formal concept analysis, and precision of data measurement ⋮ Sphericity, cubicity, and edge clique covers of graphs ⋮ Unnamed Item ⋮ An algorithmic theory of learning: Robust concepts and random projection ⋮ Random Projection RBF Nets for Multidimensional Density Estimation ⋮ R3P-Loc: a compact multi-label predictor using ridge regression and random projection for protein subcellular localization ⋮ Optimal Bounds for Johnson-Lindenstrauss Transformations ⋮ Certifying smoothness of discrete functions and measuring legitimacy of images ⋮ Embeddings of graphs in Euclidean spaces ⋮ A simple proof of the restricted isometry property for random matrices ⋮ Approximating the bandwidth via volume respecting embeddings ⋮ Fast dimension reduction using Rademacher series on dual BCH codes ⋮ Monotone maps, sphericity and bounded second eigenvalue ⋮ Latent semantic indexing: A probabilistic analysis ⋮ On computing the diameter of a point set in high dimensional Euclidean space. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Some geometric applications of the beta distribution ⋮ Random projections and Hotelling’s T2 statistics for change detection in high-dimensional data streams ⋮ On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes

Cites Work

• Unnamed Item
• On the contact dimensions of graphs
• Embedding the n-cube in lower dimensions
• Space graphs and sphericity
• On the sphericity for the join of many graphs
• On the sphericity of the graphs of semiregular polyhedra
• Sphericity exceeds cubicity for almost all complete bipartite graphs
• Embedding of trees in Euclidean spaces
• Extensions of Lipschitz mappings into a Hilbert space
• On the dimension of trees

This page was built for publication: The Johnson-Lindenstrauss lemma and the sphericity of some graphs