Randomized anisotropic transform for nonlinear dimensionality reduction
- PDF / 2,015,594 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 92 Downloads / 163 Views
Randomized anisotropic transform for nonlinear dimensionality reduction Charles K. Chui · Jianzhong Wang
Received: 10 April 2010 / Accepted: 11 May 2010 / Published online: 22 June 2010 © Springer-Verlag 2010
Abstract An innovative method is introduced in this paper to significantly increase computational speed and to reduce memory usage, when applied to nonlinear methods and algorithms for dimensionality reduction (DR). Due to the incapability of linear DR methods in the preservation of data geometry, the need of effective nonlinear approaches has recently attracted the attention of many researchers, particularly from the Mathematics and Computer Science communities. The common theme of the current nonlinear DR approaches is formulation of certain matrices, called dimensionality reduction kernels (DRK) in terms of the data points, followed by performing spectral decomposition. Hence, for datasets of large size with data points that lie in some high dimensional space, the matrix dimension of the DRK is very large. Typical examples for the need of very high dimensional DRK arise from such applications as processing multispectral imagery data, searching desired text documentary data in the internet, and recognizing human faces from given libraries. For such and many other applications, the matrix dimension of the DRK is so large that computation for carrying
The research of Charles K. Chui was supported by ARO Grant W911NF-07-1-0525. The research of Jianzhong Wang was supported by NSF Grant DMS-07-12925. C. K. Chui Department of Statistics, Stanford University, Stanford, CA 94305, USA e-mail: [email protected] Present Address: C. K. Chui Department of Mathematics and Computer Science, University of Missouri, St. Louis, MO 63121, USA J. Wang (B) Department of Mathematics and Statistics, Sam Houston State University, Huntsville, TX 77341, USA e-mail: [email protected]; [email protected]
123
24
Int J Geomath (2010) 1:23–50
out spectral decomposition of the DRK often encounters various difficulties, not only due to the need of significantly large read-only memory (ROM), but also due to computational instability. The main objective of this paper is to introduce the notion of the anisotropic transform (AT) and to develop its corresponding effective and efficient computational algorithms by integrating random embedding with the AT to formulate the randomized anisotropic transform (RAT), in order to reduce the size of the DRK significantly, while preserving local geometries of the given datasets. Illustrations with various examples will also be given in this paper to demonstrate that RAT algorithms dramatically reduce the ROM and CPU requirement, and thus allow fast processing, even on PC and potentially for handhold devices as well. Keywords Nonlinear dimensionality reduction · Randomized algorithms · Anisotropic transform · Data geometry preservation · Kernel size reduction · Random projection Mathematics Subject Classification (2000)
68W20 · 74N25 · 62-07 · 97R50
1 Introduction With the rapid technological adva
Data Loading...
