Intrinsic Dimension Estimation Based On Optimal R-covering And Its Application

In recent years, manifold learning has been widely studied and applied. Manifold learning is a class of methods that aims at finding low-dimensional manifold structure of high-dimensional data and obtaining high-dimensional data’s low dimensional embedding coordinates. Intrinsic dimension is a key parameter in manifold learning methods, If the predetermined value of the intrinsic dimension is larger than its true value, then after the dimension reduction, much redundant information of the high-dimensional data will be retained, what’s more, the result obtained may be very unstable. If the true value is larger, some useful information in the high-dimensional data may be removed. As an integral parameter of dimension reduction algorithms, intrinsic dimension plays a crucial role in dimension reduction. Therefore, intrinsic dimension estimation methods have become an important research content in manifold learning research.Previous intrinsic dimension estimation method can be roughly divided into three categories: projection methods, geometric methods and probabilistic methods. The method that uses packing numbers to estimate intrinsic dimension is a typical geometric method, it uses capacity dimension indirectly to estimate intrinsic dimension, because the direct use of capacity dimension will lead to higher computational complexity. Based on the method, for the shortcoming that this method can’t use the capacity dimension directly, we combine it with the minimum set cover algorithm, proposing an improved packing numbers intrinsic dimension estimation method. Firstly, we use the minimum set cover algorithm to find the optimal r-covering number, so as to reduce the computational complexity caused by the capacity dimension, then the capacity dimension can be used directly by the packing numbers method to handle high-dimensional data, without using size-dependent way to redefine the capacity dimension. Finally, experiments verify the effectiveness of the improved algorithm. Then in this paper, we analyze the improved algorithm’s applications in face recognition and manifold learning. Firstly, we combine it with several classic manifold learning algorithms: LLE、ISOMAP、LTSA、LE, obtaining ideal dimension reduction result on Swiss Roll data set. The adaptation of the proposed method is validated. Then we combine this algorithm with the Adaptive neighborhood selection Orthogonal Laplacianface algorithm(AOL), we use the improved algorithm to calculate the intrinsic dimension of the face data, and use this value in AOL algorithm. We conduct experiments in ORL face database and get a good result, improving the efficiency and accuracy of face recognition.