Randomized anisotropic transform for nonlinear dimensionality reduction

被引：15

作者：

Chui C.K. ^{[1
,2
]}

Wang J. ^{[3
]}

机构：

[1] Department of Statistics, Stanford University, Stanford

[2] Department of Mathematics and Computer Science, University of Missouri, St. Louis

[3] Department of Mathematics and Statistics, Sam Houston State University, Huntsville

来源：

GEM - International Journal on Geomathematics | 2010年 / 1卷 / 01期

基金：

美国国家科学基金会;

关键词：

Anisotropic transform; Data geometry preservation; Kernel size reduction; Nonlinear dimensionality reduction; Random projection; Randomized algorithms;

D O I：

10.1007/s13137-010-0004-8

中图分类号：

学科分类号：

摘要：

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 theMathematics and Computer Science communities. The common theme of the current nonlinear DRapproaches 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 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. © Springer-Verlag 2010.

引用

页码：23 / 50

页数：27

共 26 条

[1]

Achlioptas D., Database friendly random projections, Proc 20th PODS, pp. 274-281, (2001)

[2]

Arriaga R.I., Vempala S., An algorithmic theory of learning: robust concepts and random projection, Proc 40th FOCS, pp. 616-623, (1999)

[3]

Bachmann C.M., Ainsworth T.L., Fusina R.A., Exploiting manifold geometry in hyperspectral imagery, IEEE Trans. Geosci. Remote Sens., 43, pp. 441-454, (2005)

[4]

Bachmann C.M., Ainsworth T.L., Fusina R.A., Improved manifold coordinate representations of largescale hyperspectral scenes, IEEE Trans Geosci. Remote Sens., 44, pp. 2786-2803, (2006)

[5]

Bachmann C.M., Ainsworth T.L., Fusina R.A., Montes M.J., Bowles J.H., Korwan D.R., Gillis L., Bathymetric retrieval from hyperspectral imagery using manifold coordinate representations, IEEE Trans. Geosci. Remote Sens., 47, pp. 884-897, (2009)

[6]

Barasubramanian M., Schwaartz E.L., Tenenbaum J.B., de Silva V., Langford J.C., The isomap algorithm and topological staility, Science, 295, (2002)

[7]

Belkin M., Niyogi P., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Comput, 15, pp. 1373-1396, (2003)

[8]

Chui C.K., Wang J.Z., Methods and algorithms for dimensionality reduction of HSI data, The 2ndWorkshop on Advancing the Automation of Image Analysis, pp. 29-31, (2008)

[9]

Chui C.K., Wang J.Z., Dimensionality reduction of hyper-spectral imagery data for feature classification, Handbook of Geomathematics, (2010)

[10]

Coifman R.R., Lafon S., Diffusion maps, Appl. Comput. Harmon. Anal., 21, pp. 5-30, (2006)

← 1 2 3 →