Article

Intrinsic dimensionality estimation of submanifolds in R^d

Authors:

Matthias Hein,

Jean-Yves AudibertAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 289 - 296

https://doi.org/10.1145/1102351.1102388

Published: 07 August 2005 Publication History

Get Access

Abstract

We present a new method to estimate the intrinsic dimensionality of a submanifold M in R^d from random samples. The method is based on the convergence rates of a certain U-statistic on the manifold. We solve at least partially the question of the choice of the scale of the data. Moreover the proposed method is easy to implement, can handle large data sets and performs very well even for small sample sizes. We compare the proposed method to two standard estimators on several artificial as well as real data sets.

References

[1]

Costa, J. A., & Hero, A. O. (2004). Learning intrinsic dimension and intrinsic entropy of high-dimensional datasets. Proc. of European Sig. Proc. Conference (EUSIPCO).

Google Scholar

[2]

Falconer, K. (2003). Fractal geometry. Wiley. 2nd edition.

Google Scholar

[3]

Fukunaga, K. (1971). An algorithm for finding intrinsic dimensionality of data. IEEE Transactions on Computers, 20, 176--183.

Digital Library

Google Scholar

[4]

Grassberger, P., & Procaccia, I. (1983). Measuring the strangeness of strange attractors. Physica D, 9, 189--208.

Crossref

Google Scholar

[5]

Hein, M., Audibert, J.-Y., & von Luxburg, U. (2005). From graphs to manifolds - weak and strong pointwise consistency of graph Laplacians. Proceedings of the 18th Conference on Learning Theory (COLT).

Digital Library

Google Scholar

[6]

Hocffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58, 13--30.

Crossref

Google Scholar

[7]

Lee, J. M. (1997). Riemannian manifolds. Springer.

Google Scholar

[8]

Serfling, R. (1980). Approximation theorem in mathematical statistics. Wiley.

Google Scholar

[9]

Smolyanov, O. G., von Weizsäcker, H., & Wittich, O. (2004). Chernoff's theorem and discrete time approximations of Brownian motion on manifolds. Preprint, available at http://lanl.arxiv.org/abs/math.PR/0409155.

Google Scholar

[10]

Takens, F. (1985). On the numerical determination of the dimension of an attractor. Dynamical systems and bifurcations (pp. 99--106).

Google Scholar

[11]

Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319--2323.

Crossref

Google Scholar

Cited By

View all

Grindrod PHigham Dde Kergorlay H(2024)Estimating network dimension when the spectrum strugglesRoyal Society Open Science10.1098/rsos.23089811:5Online publication date: 22-May-2024
https://doi.org/10.1098/rsos.230898
Tulchinskii EKuznetsov KKushnareva LCherniavskii DNikolenko SBurnaev EBarannikov SPiontkovskaya IOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Intrinsic dimension estimation for robust detection of AI-generated textsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667828(39257-39276)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667828
Horvat CPfister J(2023)Density estimation on low-dimensional manifoldsThe Journal of Machine Learning Research10.5555/3648699.364876024:1(2604-2640)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.5555/3648699.3648760
Show More Cited By

Recommendations

Intrinsic Dimensionality Estimation With Optimally Topology Preserving Maps

A new method for analyzing the intrinsic dimensionality (ID) of low-dimensional manifolds in high-dimensional feature spaces is presented. Compared to a previous approach by Fukunaga and Olsen, the method has only linear instead of cubic time complexity ...
On Intrinsic Cramér-Rao Bounds for Riemannian Submanifolds and Quotient Manifolds

We study Cramér-Rao bounds (CRB's) for estimation problems on Riemannian manifolds. In [S. T. Smith, “Covariance, Subspace, and Intrinsic Cramér-Rao bounds,” IEEE Trans. Signal Process., vol. 53, no. 5, 1610–1630, 2005], the author gives intrinsic CRB's ...
Relative Intrinsic Dimensionality Is Intrinsic to Learning
Artificial Neural Networks and Machine Learning – ICANN 2023
Abstract
High dimensional data can have a surprising property: pairs of data points may be easily separated from each other, or even from arbitrary subsets, with high probability using just simple linear classifiers. However, this is more of a rule of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

113
Total Citations
View Citations
585
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)5

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Grindrod PHigham Dde Kergorlay H(2024)Estimating network dimension when the spectrum strugglesRoyal Society Open Science10.1098/rsos.23089811:5Online publication date: 22-May-2024
https://doi.org/10.1098/rsos.230898
Tulchinskii EKuznetsov KKushnareva LCherniavskii DNikolenko SBurnaev EBarannikov SPiontkovskaya IOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Intrinsic dimension estimation for robust detection of AI-generated textsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667828(39257-39276)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667828
Horvat CPfister J(2023)Density estimation on low-dimensional manifoldsThe Journal of Machine Learning Research10.5555/3648699.364876024:1(2604-2640)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.5555/3648699.3648760
Dyballa LZucker S(2023)IAN: Iterated Adaptive Neighborhoods for Manifold Learning and Dimensionality EstimationNeural Computation10.1162/neco_a_0156635:3(453-524)Online publication date: 17-Feb-2023
https://doi.org/10.1162/neco_a_01566
Liu DSimeone O(2023)Wireless Federated Langevin Monte Carlo: Repurposing Channel Noise for Bayesian Sampling and PrivacyIEEE Transactions on Wireless Communications10.1109/TWC.2022.321566322:5(2946-2961)Online publication date: May-2023
https://doi.org/10.1109/TWC.2022.3215663
Asokan SSeelamantula C(2023)Spider GAN: Leveraging Friendly Neighbors to Accelerate GAN Training2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52729.2023.00378(3883-3893)Online publication date: Jun-2023
https://doi.org/10.1109/CVPR52729.2023.00378
Bailey JHoule MMa X(2023)Relationships between tail entropies and local intrinsic dimensionality and their use for estimation and feature representationInformation Systems10.1016/j.is.2023.102245118(102245)Online publication date: Sep-2023
https://doi.org/10.1016/j.is.2023.102245
Mézard M(2023)Spin glass theory and its new challenge: structured disorderIndian Journal of Physics10.1007/s12648-023-03029-898:11(3757-3768)Online publication date: 10-Dec-2023
https://doi.org/10.1007/s12648-023-03029-8
Camastra FCasolaro AIannuzzo G(2023)Manifold learning by a deep Gaussian process autoencoderNeural Computing and Applications10.1007/s00521-023-08536-735:21(15573-15582)Online publication date: 15-Apr-2023
https://doi.org/10.1007/s00521-023-08536-7
Camastra FCasolaro AIannuzzo G(2023)Manifold Learning by a Deep Gaussian Process Variational AutoencoderApplications of Artificial Intelligence and Neural Systems to Data Science10.1007/978-981-99-3592-5_3(29-36)Online publication date: 2-Aug-2023
https://doi.org/10.1007/978-981-99-3592-5_3
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Recommendations

Intrinsic Dimensionality Estimation With Optimally Topology Preserving Maps

On Intrinsic Cramér-Rao Bounds for Riemannian Submanifolds and Quotient Manifolds

Relative Intrinsic Dimensionality Is Intrinsic to Learning

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations