One of common reasons for poor performance of algorithms working on high dimensional data is the dimension of the data. In many settings running time of an algorithm depends exponentially on the dimension, hence the phenomenon curse of high dimension. But it has been observed in practice that the actual dimensionality of the data may not be as high as ambient dimension. This dimension is known as intrinsic dimension of data. Often the intrinsic dimension of data is much less and the algorithms are tuned accordingly. There are many notions of measuring intrinsic dimension of the data such as doubling dimension and covariance dimension.
D^2-sampling has been very popular in practice for k-means clustering. In this work we show that D^2-sampling can be used to estimate the doubling dimension and covariance dimension of the data.