nips nips2007 nips2007-161 nips2007-161-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chinmay Hegde, Michael Wakin, Richard Baraniuk
Abstract: We propose a novel method for linear dimensionality reduction of manifold modeled data. First, we show that with a small number M of random projections of sample points in RN belonging to an unknown K-dimensional Euclidean manifold, the intrinsic dimension (ID) of the sample set can be estimated to high accuracy. Second, we rigorously prove that using only this set of random projections, we can estimate the structure of the underlying manifold. In both cases, the number of random projections required is linear in K and logarithmic in N , meaning that K < M ≪ N . To handle practical situations, we develop a greedy algorithm to estimate the smallest size of the projection space required to perform manifold learning. Our method is particularly relevant in distributed sensing systems and leads to significant potential savings in data acquisition, storage and transmission costs.
[1] R. G. Baraniuk and M. B. Wakin. Random projections of smooth manifolds. 2007. To appear in Foundations of Computational Mathematics.
[2] M. B. Wakin, J. N. Laska, M. F. Duarte, D. Baron, S. Sarvotham, D. Takhar, K. F. Kelly, and R. G. Baraniuk. An architecture for compressive imaging. In IEEE International Conference on Image Processing (ICIP), pages 1273–1276, Oct. 2006.
[3] S. Kirolos, J.N. Laska, M.B. Wakin, M.F. Duarte, D.Baron, T. Ragheb, Y. Massoud, and R.G. Baraniuk. Analog-to-information conversion via random demodulation. In Proc. IEEE Dallas Circuits and Systems Workshop (DCAS), 2006.
[4] E. J. Cand` s, J. Romberg, and T. Tao. Robust uncertainty principles: Exact signal reconstruce tion from highly incomplete frequency information. IEEE Trans. Info. Theory, 52(2):489–509, Feb. 2006.
[5] D. L. Donoho. Compressed sensing. IEEE Trans. Info. Theory, 52(4):1289–1306, September 2006.
[6] J. B. Tenenbaum, V.de Silva, and J. C. Landford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000.
[7] P. Grassberger and I. Procaccia. Measuring the strangeness of strange attractors. Physica D Nonlinear Phenomena, 9:189–208, 1983.
[8] J. Theiler. Statistical precision of dimension estimators. Physical Review A, 41(6):3038–3051, 1990.
[9] F. Camastra. Data dimensionality estimation methods: a survey. Pattern Recognition, 36:2945– 2954, 2003.
[10] J. A. Costa and A. O. Hero. Geodesic entropic graphs for dimension and entropy estimation in manifold learning. IEEE Trans. Signal Processing, 52(8):2210–2221, August 2004.
[11] E. Levina and P. J. Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in NIPS, volume 17. MIT Press, 2005.
[12] S. Roweis and L. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, 2000.
[13] D. Donoho and C. Grimes. Hessian eigenmaps: locally linear embedding techniques for high dimensional data. Proc. of National Academy of Sciences, 100(10):5591–5596, 2003.
[14] Sanjoy Dasgupta and Anupam Gupta. An elementary proof of the JL lemma. Technical Report TR-99-006, University of California, Berkeley, 1999.
[15] C. Hegde, M. B. Wakin, and R. G. Baraniuk. Random projections for manifold learning proofs and analysis. Technical Report TREE 0710, Rice University, 2007.
[16] M. Bernstein, V. de Silva, J. Langford, and J. Tenenbaum. Graph approximations to geodesics on embedded manifolds, 2000. Technical report, Stanford University.
[17] B. K´ gl. Intrinsic dimension estimation using packing numbers. In Advances in NIPS, vole ume 14. MIT Press, 2002.