The pre-image problem for Laplacian eigenmaps utilizing \(L_1\) regularization with applications to data fusion. (English) Zbl 1409.68230
Summary: As the popularity of non-linear manifold learning techniques such as kernel PCA and Laplacian eigenmaps grows, vast improvements have been seen in many areas of data processing, including heterogeneous data fusion and integration. One problem with the non-linear techniques, however, is the lack of an easily calculable pre-image. Existence of such pre-image would allow visualization of the fused data not only in the embedded space, but also in the original data space. The ability to make such comparisons can be crucial for data analysts and other subject matter experts who are the end users of novel mathematical algorithms. In this paper, we propose a pre-image algorithm for Laplacian eigenmaps. Our method offers major improvements over existing techniques, which allow us to address the problem of noisy inputs and the issue of how to calculate the pre-image of a point outside the convex hull of training samples; both of which have been overlooked in previous studies in this field. We conclude by showing that our pre-image algorithm, combined with feature space rotations, allows us to recover occluded pixels of an imaging modality based off knowledge of that image measured by heterogeneous modalities. We demonstrate this data recovery on heterogeneous hyperspectral (HS) cameras, as well as by recovering LIDAR measurements from HS data.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 65J22 | Numerical solution to inverse problems in abstract spaces |
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
References:
| [1] | Lee J A and Verleysen M 2007 Nonlinear Dimensionality Reduction (Berlin: Springer) · Zbl 1128.68024 · doi:10.1007/978-0-387-39351-3 |
| [2] | Schölkopf B, Mika S, Burges C, Knirsch P, Müller K-R, Rätsch G and Smola A 1999 Input space versus feature space in kernel-based methods IEEE Trans. Neural Netw.10 1000-17 · doi:10.1109/72.788641 |
| [3] | Coifman R R and Hirn M J 2014 Diffusion maps for changing data Appl. Comput. Harmon. Anal.36 79-107 · Zbl 1302.62122 · doi:10.1016/j.acha.2013.03.001 |
| [4] | Mika S, Schölkopf B, Smola A J, Müller K-R, Scholz M and Gunnar Rätsch 1998 Kernel pca and de-noising in feature spaces NIPSvol 11 pp 536-42 |
| [5] | Arias P, Randall G and Sapiro G 2007 Connecting the out-of-sample and pre-image problems in kernel methods IEEE Conf. on Computer Vision and Pattern Recognition pp 1-8 |
| [6] | Kushnir D, Haddad A and Coifman R R 2012 Anisotropic diffusion on sub-manifolds with application to earth structure classification Appl. Comput. Harmon. Anal.32 280-94 · Zbl 1316.62067 · doi:10.1016/j.acha.2011.06.002 |
| [7] | Kwok J T and Tsang I W 2004 The pre-image problem in kernel methods IEEE Trans. Neural Netw.15 1517-25 · doi:10.1109/TNN.2004.837781 |
| [8] | Schölkopf B, Smola A and Müller K 1998 Nonlinear component analysis as a kernel eigenvalue problem IEEE Trans. Neural Comput.10 1299-319 · doi:10.1162/089976698300017467 |
| [9] | Belkin M and Niyogi P 2003 Laplacian eigenmaps for dimensionality reduction and data representation IEEE Trans. Neural Comput.15 1373-96 · Zbl 1085.68119 · doi:10.1162/089976603321780317 |
| [10] | Thorstensen N, Segonne F and Keriven R 2009 Pre-image as karcher mean using diffusion maps: Application to shape and image denoising Scale Space and Variational Methods in Computer Vision (Berlin: Springer) pp 721-32 · doi:10.1007/978-3-642-02256-2_60 |
| [11] | Monnig N, Fornberg B and Meyer F 2014 Inverting nonlinear dimensionality reduction with scale-free radial basis function interpolation Appl. Comput. Harmon. Anal. · Zbl 1297.65015 |
| [12] | Lee C and Landgrebe D A 1993 Analyzing high-dimensional multispectral data IEEE Trans. Geosci. Remote Sens.31 792-800 · doi:10.1109/36.239901 |
| [13] | Bachmann C M, Ainsworth T L and Fusina R A 2005 Exploiting manifold geometry in hyperspectral imagery IEEE Trans. Geosci. Remote Sens.43 441-54 · doi:10.1109/TGRS.2004.842292 |
| [14] | Chen Y, Crawford M M and Ghosh J 2005 Applying nonlinear manifold learning to hyperspectral data for land cover classification IGARSSvol 5 pp 24-9 |
| [15] | Schlamm A, Messinger D and Basener W 2009 Geometric estimation of the inherent dimensionality of single and multi-material clusters in hyperspectral imagery J. Appl. Remote Sens.3 033527-7 · doi:10.1117/1.3133323 |
| [16] | Belkin M and Niyogi P 2005 Towards a theoretical foundation for Laplacian-based manifold methods COLT pp 486-500 · Zbl 1137.68521 |
| [17] | Belkin M and Niyogi P 2006 Convergence of Laplacian Eigenmaps NIPS pp 129-36 |
| [18] | Fowlkes C, Belongie S and Malik J 2001 Efficient spatiotemporal grouping using the Nyström method Proc. of the IEEE Conf. on Computer Vision and Pattern Recognitionvol 1 pp I-231-I-238 |
| [19] | Bengio Y, Paiement J-F and Vincent P 2003 Out-of-sample extensions for lle, isomap, mds, eigenmaps, and spectral clustering Advances in Neural Information Processing Systems (Cambridge, MA: MIT Press) pp 177-84 |
| [20] | Gower J C 1968 Adding a point to vector diagrams in multivariate analysis Biometrika55 582-5 · Zbl 0167.17802 · doi:10.1093/biomet/55.3.582 |
| [21] | Zheng W-S, Lai J H and Yuen P C 2010 Penalized preimage learning in kernel principal component analysis IEEE Trans. Neural Netw.21 551-70 · doi:10.1109/TNN.2009.2039647 |
| [22] | Honeine P and Richard C 2009 Solving the pre-image problem in kernel machines: a direct method IEEE Int. Workshop on Machine Learning for Signal Processing pp 1-6 |
| [23] | Etyngier P, Segonne F and Keriven R 2007 Shape priors using manifold learning techniques Int. Conf. on Computer Vision pp 1-8 |
| [24] | Bakır G H, Weston J and Schölkopf B 2004 Learning to find pre-images Adv. Neural Inf. Process. Syst.16 449-56 |
| [25] | Bakır G, Zien A and Tsuda K 2004 Learning to find graph pre-images Pattern Recognition (Berlin: Springer) pp 253-61 · doi:10.1007/978-3-540-28649-3_31 |
| [26] | Talmon R, Kushnir D, Coifman R, Cohen I and Gannot S 2012 Parametrization of linear systems using diffusion kernels IEEE Trans. Signal Process.60 1159-73 · Zbl 1391.93278 · doi:10.1109/TSP.2011.2177973 |
| [27] | Pati Y C, Rezaiifar R and Krishnaprasad P S 1993 Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition Proc. of the 27th Annual Asilomar Conf. on Signals, Systems, and Computers pp 40-4 |
| [28] | Candès E and Romberg J 2007 Sparsity and incoherence in compressive sampling Inverse Problems23 969-85 · Zbl 1120.94005 · doi:10.1088/0266-5611/23/3/008 |
| [29] | Liu X, Tanaka M and Okutomi M 2012 Noise level estimation using weak textured patches of a single noisy image IEEE Int. Conf. Image Processing pp 665-8 |
| [30] | Xing Z, Zhou M, Castrodad A, Sapiro G and Carin L 2012 Dictionary learning for noisy and incomplete hyperspectral images SIAM J. Imaging Sci.5 33-56 · Zbl 1316.62094 · doi:10.1137/110837486 |
| [31] | Cloninger A 2014 Exploiting data-dependent structure for improving sensor acquisition and integration PhD Thesis University of Maryland |
| [32] | Meinshausen N 2007 Relaxed lasso Computat. Stat. Data Anal.52 374-93 · Zbl 1452.62522 · doi:10.1016/j.csda.2006.12.019 |
| [33] | Kim J, Kim Y and Kim Y 2008 A gradient-based optimization algorithm for lasso J. Comput. Graph. Stat.17 · doi:10.1198/106186008X386210 |
| [34] | Witten D M, Friedman J H and Simon N 2011 New insights and faster computations for the graphical lasso J. Comput. Graph. Stat.20 892-900 · doi:10.1198/jcgs.2011.11051a |
| [35] | Meier L, De Geer S V and Bühlmann P 2008 The group lasso for logistic regression J. R. Stat. Soc B 70 53-71 · Zbl 1400.62276 · doi:10.1111/j.1467-9868.2007.00627.x |
| [36] | LeCun Y and Cortes C 1998 The MNIST database of handwritten digits |
| [37] | Nguyen N H, Chen J, Richard C, Honeine P and Theys C 2013 Supervised nonlinear unmixing of hyperspectral images using a pre-image methods EAS Publ. Ser.59 417-37 · doi:10.1051/eas/1359019 |
| [38] | Karami A, Yazdi M and Asli A Z 2011 Noise reduction of hyperspectral images using kernel non-negative tucker decomposition IEEE J. Sel. Top. Signal Process.5 487-93 · doi:10.1109/JSTSP.2011.2132692 |
| [39] | Langrebe D 1992 AVIRIS NW Indiana’s Indian Pines 1992 data set (http://dynamo.ecn.purdue.edu/biehl/MultiSpec/documentation.html) |
| [40] | Thenkabail P S, Enclona E A, Ashton M S and Bauke Meer V D 2004 Accuracy assessments of hyperspectral waveband performance for vegetation analysis applications Remote Sens. Environ.91 354-76 · doi:10.1016/j.rse.2004.03.013 |
| [41] | Gader P, Zare A, Close R, Aitken J and Tuell G 2013 MUUFL Gulfport hyperspectral and LiDAR airborne data set Technical Report |
| [42] | Dobrosotskaya J A and Bertozzi A L 2008 A wavelet-laplace variational technique for image deconvolution and inpainting IEEE Trans. Image Process.17 657-63 · doi:10.1109/TIP.2008.919367 |
| [43] | Dobrosotskaya J and Bertozzi A 2013 Analysis of the wavelet Ginzburg-Landau energy in image applications with edges SIAM J. Imaging Sci.6 698-729 · Zbl 1280.42032 · doi:10.1137/100812859 |
| [44] | Chan T F and Shen J 2001 Nontexture inpainting by curvature-driven diffusions J. Vis. Commun. Image Represent.12 436-49 · doi:10.1006/jvci.2001.0487 |
| [45] | Chan T F, Shen J and Zhou H-M 2006 Total variation wavelet inpainting J. Math. Imaging Vis.25 107-25 · Zbl 1478.94019 · doi:10.1007/s10851-006-5257-3 |
| [46] | Shen J, Kang S H and Chan T F 2003 Euler’s elastica and curvature-based inpainting SIAM J. Appl. Math.63 564-92 · Zbl 1028.68185 · doi:10.1137/S0036139901390088 |
| [47] | Cloninger A and Czaja W 2014 Lidar image recovery by incorporating heterogeneous imaging modalities Proc. SPIE9121 91210C · doi:10.1117/12.2050714 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
