nips nips2010 nips2010-220 nips2010-220-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Aman Dhesi, Purushottam Kar
Abstract: The Random Projection Tree (RPT REE) structures proposed in [1] are space partitioning data structures that automatically adapt to various notions of intrinsic dimensionality of data. We prove new results for both the RPT REE -M AX and the RPT REE -M EAN data structures. Our result for RPT REE -M AX gives a nearoptimal bound on the number of levels required by this data structure to reduce the size of its cells by a factor s ≥ 2. We also prove a packing lemma for this data structure. Our final result shows that low-dimensional manifolds have bounded Local Covariance Dimension. As a consequence we show that RPT REE -M EAN adapts to manifold dimension as well.
[1] Sanjoy Dasgupta and Yoav Freund. Random Projection Trees and Low dimensional Manifolds. In 40th Annual ACM Symposium on Theory of Computing, pages 537–546, 2008.
[2] Piotr Indyk and Rajeev Motwani. Approximate Nearest Neighbors : Towards Removing the Curse of Dimensionality. In 30th Annual ACM Symposium on Theory of Computing, pages 604–613, 1998.
[3] Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(22):2319–2323, 2000.
[4] Piotr Indyk and Assaf Naor. Nearest-Neighbor-Preserving Embeddings. ACM Transactions on Algorithms, 3, 2007.
[5] Richard G. Baraniuk and Michael B. Wakin. Random Projections of Smooth Manifolds. Foundations of Computational Mathematics, 9(1):51–77, 2009.
[6] Yoav Freund, Sanjoy Dasgupta, Mayank Kabra, and Nakul Verma. Learning the structure of manifolds using random projections. In Twenty-First Annual Conference on Neural Information Processing Systems, 2007.
[7] Samory Kpotufe. Escaping the curse of dimensionality with a tree-based regressor. In 22nd Annual Conference on Learning Theory, 2009.
[8] Donghui Yan, Ling Huang, and Michael I. Jordan. Fast Approximate Spectral Clustering. In 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 907–916, 2009.
[9] John Wright and Gang Hua. Implicit Elastic Matching with Random Projections for Pose-Variant Face Recognition. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 1502–1509, 2009.
[10] Jian Pu, Junping Zhang, Peihong Guo, and Xiaoru Yuan. Interactive Super-Resolution through Neighbor Embedding. In 9th Asian Conference on Computer Vision, pages 496–505, 2009.
[11] Jon Louis Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Communications of the ACM, 18(9):509–517, 1975.
[12] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions. Journal of the ACM, 45(6):891–923, 1998.
[13] Christian A. Duncan, Michael T. Goodrich, and Stephen G. Kobourov. Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees. Journal of Algorithms, 38(1):303–333, 2001.
[14] Hanan Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers, 2005.
[15] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Computational Geometry, 28(2-3):89–112, 2004.
[16] Partha Niyogi, Stephen Smale, and Shmuel Weinberger. Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete & Computational Geometry, 39(1-3):419–441, 2008.
[17] Sebasti´ n Montiel and Antonio Ros. Curves and Surfaces, volume 69 of Graduate Studies in Mathemata ics. American Mathematical Society and Real Sociedad Matem´ tica Epa˜ ola, 2005. a n 9