Tighter bounds for random projections of manifolds

ABSTRACT

The Johnson-Lindenstrauss random projection lemma gives a simple way to reduce the dimensionality of a set of points while approximately preserving their pairwise distances. The most direct application of the lemma applies to a finite set of points, but recent work has extended the technique to affine subspaces, curves, and general smooth manifolds. Here the case of random projection of smooth manifolds is considered, and a previous analysis is sharpened, reducing the dependence on such properties as the manifold's maximum curvature.

REFERENCES

• 1: Pankaj K. Agarwal , Sariel Har-Peled , Hai Yu, Embeddings of surfaces, curves, and moving points in euclidean space, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247135]
• 2: Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132597]
• 3: R. Baraniuk and M. Wakin. Random projections of smooth manifolds. to appear, Foundations of Computational Mathematics, 2006.
• 4: Kenneth L. Clarkson, Building triangulations using ε-nets, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132564]
• 5: R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approximation Theory, 10:227--236, 1974.
• 6: Alan Edelman , Tomás A. Arias , Steven T. Smith, The Geometry of Algorithms with Orthogonality Constraints, SIAM Journal on Matrix Analysis and Applications, v.20 n.2, p.303-353, April 1999 [doi>10.1137/S0895479895290954]
• 7: P. M. Gruber. Asymptotic estimates for best and stepwise approximation of convex bodies I. Forum Math., 5:281--297, 1993.
• 8: C. Hegde, M. B. Wakin, and R. G. Baraniuk. Random projections for manifold learning. In Neural Information Processing Systems (NIPS), December 2007.
• 9: Piotr Indyk, Dimensionality reduction techniques for proximity problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.371-378, January 09-11, 2000, San Francisco, California, United States
• 10: P. Indyk and J. Matoušek. Low-distortion embeddings of finite metric spaces, pages 177--196. CRC Press, 2004.
• 11: Piotr Indyk , Assaf Naor, Nearest-neighbor-preserving embeddings, ACM Transactions on Algorithms (TALG), v.3 n.3, p.31-es, August 2007 [doi>10.1145/1273340.1273347]
• 12: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mapping into Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 13: N. Linial. Finite metric spaces: combinatorics, geometry, and algorithms. In International Congress of Mathematicians III, pages 573--586, 2002.
• 14: Avner Magen, Dimensionality Reductions That Preserve Volumes and Distance to Affine Spaces, and Their Algorithmic Applications, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.239-253, September 13-15, 2002
• 15: H. Pottmann, T. Steiner, M. Hofer, C. Haider, and A. Hanbury. The isophotic metric and its application to feature sensitive morphology on surfaces. In T. Pajdla and J. Matas, editors, Computer Vision - ECCV 2004, Part IV, volume 3024 of Lecture Notes in Computer Science, pages 560--572. Springer, 2004.
• 16: Tamas Sarlos, Improved Approximation Algorithms for Large Matrices via Random Projections, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.143-152, October 21-24, 2006 [doi>10.1109/FOCS.2006.37]
• 17: S. Vempala. The Random Projection Method, volume 65 of Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2004.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
johnson-lindenstrauss random projection