nips nips2005 nips2005-66 nips2005-66-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Maxim Raginsky, Svetlana Lazebnik
Abstract: We introduce a technique for dimensionality estimation based on the notion of quantization dimension, which connects the asymptotic optimal quantization error for a probability distribution on a manifold to its intrinsic dimension. The definition of quantization dimension yields a family of estimation algorithms, whose limiting case is equivalent to a recent method based on packing numbers. Using the formalism of high-rate vector quantization, we address issues of statistical consistency and analyze the behavior of our scheme in the presence of noise.
[1] S.T. Roweis and L.K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323–2326, December 2000.
[2] J.B. Tenenbaum, V. de Silva, and J.C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, December 2000.
[3] M. Brand. Charting a manifold. In NIPS 15, pages 977–984, Cambridge, MA, 2003. MIT Press.
[4] B. K´ gl. Intrinsic dimension estimation using packing numbers. In NIPS 15, volume 15, e Cambridge, MA, 2003. MIT Press.
[5] E. Levina and P.J. Bickel. Maximum likelihood estimation of intrinsic dimension. In NIPS 17, Cambridge, MA, 2005. MIT Press.
[6] S. Graf and H. Luschgy. Foundations of Quantization for Probability Distributions. SpringerVerlag, Berlin, 2000.
[7] P.L. Zador. Asymptotic quantization error of continuous signals and the quantization dimension. IEEE Trans. Inform. Theory, IT-28:139–149, March 1982.
[8] T. Linder. Learning-theoretic methods in vector quantization. In L. Gy¨ rfi, editor, Principles of o Nonparametric Learning. Springer-Verlag, New York, 2001.
[9] R.M. Gray and L.D. Davisson. Quantizer mismatch. IEEE Trans. Commun., 23:439–443, 1975.
[10] E. Welzl. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science, volume 555 of LNCS, pages 359–370. Springer, 1991.
[11] M. Raginsky. A complexity-regularized quantization approach to nonlinear dimensionality reduction. Proc. 2005 IEEE Int. Symp. Inform. Theory, pages 352–356. 4 Interestingly, Brand [3] reports an intrinsic dimension estimate of 3 for this data set. However, he used only a 500-frame subsequence and introduced additional mirror symmetry.