Regularized principal component analysis

Abstract

Given a set of signals, a classical construction of an optimal truncatable basis for optimally representing the signals, is the principal component analysis (PCA for short) approach. When the information about the signals one would like to represent is a more general property, like smoothness, a different basis should be considered. One example is the Fourier basis which is optimal for representation smooth functions sampled on regular grid. It is derived as the eigenfunctions of the circulant Laplacian operator. In this paper, based on the optimality of the eigenfunctions of the Laplace-Beltrami operator (LBO for short), the construction of PCA for geometric structures is regularized. By assuming smoothness of a given data, one could exploit the intrinsic geometric structure to regularize the construction of a basis by which the observed data is represented. The LBO can be decomposed to provide a representation space optimized for both internal structure and external observations. The proposed model takes the best from both the intrinsic and the extrinsic structures of the data and provides an optimal smooth representation of shapes and forms.

Keywords

Laplace-Beltrami operator / Principal component analysis / Isometry

References

[1] Aflalo Y., Brezis H., Bruckstein A. M., Kimmel R., Sochen N.. Best bases for signal spaces, Comptes Rendus de l’Acadmie des Sciences, 2016

[2] Aflalo Y., Brezis H., Kimmel R.. On the optimality of shape and data representation in the spectral domain. SIAM Journal on Scientific Computing, 2015, 8(2): 1141-1160

[3] Aubry M., Schlickewei U., Cremers D.. The wave kernel signature: A quantum mechanical approach to shape analysis, Computer Vision Workshops (ICCV Workshops). 2011 IEEE International Conference, 2011 1626-1633

[4] Belkin M., Niyogi P.. Convergence of Laplacian eigenmaps. Proceedings of the Twentieth Annual Conference on NIPS, 2006 129-136

[5] Ben-Chen M., Gotsman C.. On the optimality of spectral compression of mesh data. ACM Trans. Graph., 2005, 24(1): 60-80

[6] Bérard P., Besson G., Gallot S.. Embedding Riemannian manifolds by their heat kernel. Geometric and Functional Analysis, 1994, 4(4): 373-398

[7] Borg I., Groenen P.. Modern Multidimensional Scaling: Theory and Applications, 1997, New York: Springer-Verlag

[8] Brezis H.. Functional Analysis, Sobolev Spaces and Partial Differential Equations, 2010, New York: Universitext Series, Springer-Verlag

[9] Bronstein A. M., Bronstein M. M., Kimmel R.. Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences, 2006, 103(5): 1168-1172

[10] Bronstein A. M., Bronstein M. M., Kimmel R.. Rock, paper, and scissors: Extrinsic vs. intrinsic similarity of non-rigid shapes. IEEE 11th International Conference on Computer Vision, 2007

[11] Bronstein A. M., Bronstein M. M., Kimmel R. A Gromov-Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching. International Journal of Computer Vision, 2010, 89(2–3): 266-286

[12] Coifman R. R., Lafon S.. Diffusion maps. Applied and Computational Harmonic Analysis, 2006, 21(1): 5-30

[13] Coifman R. R., Lafon S., Lee A. B. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the National Academy of Sciences, 2005, 102(21): 7426-7431

[14] Coifman R. R., Maggioni M.. Diffusion wavelets. Applied and Computational Harmonic Analysis, 2006, 21(1): 53-94

[15] Gebal K., Bærentzen J. A., Aanæs H., Larsen R.. Shape analysis using the auto diffusion function. Computer Graphics Forum, 2009, 28: 1405-1413

[16] Hammond D. K., Vandergheynst P., Gribonval R.. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150

[17] Jiang B., Ding C., Luo B., Tang J.. Graph-Laplacian PCA: Closed-form solution and robustness. IEEE Conf. Computer Vision and Pattern Recognition (CVPR), 2013 3492-3498

[18] Jolliffe I. T.. Principal Component Analysis, 2002, New York: Springer-Verlag

[19] Kalofolias V., Bresson X., Bronstein M. M., Vandergheynst P.. Matrix completion on graphs. Proc. NIPS, Workshop Out of the Box: Robustness in High Dimension, 2014

[20] Karni Z., Gotsman C.. Spectral compression of mesh geometry, 2000 279-286

[21] Kovnatsky A., Bronstein M. M., Bresson X., Vandergheynst P.. Functional correspondence by matrix completion. Proc. Computer Vision and Pattern Recognition (CVPR), 2015

[22] Kovnatsky A., Bronstein M. M., Bronstein A. M. Coupled quasi-harmonic bases. Computer Graphics Forum, 2013, 32: 439-448

[23] Lévy B.. Laplace-Beltrami eigenfunctions towards an algorithm that “understands” geometry. Shape Modeling and Applications, IEEE International Conference, 2006 13-13

[24] Meyer M., Desbrun M., Schröder P., Barr A. H.. Discrete differential-geometry operators for triangulated 2-manifolds. Visualization and mathematics, 2002, 3(2): 52-58

[25] Pearson K.. On lines and planes of closest fit to systems of points in space. Philosophical Magazine, 1901, 2(11): 559-572

[26] Pinkall U., Polthier K.. Computing discrete minimal surfaces and their conjugates. Experiment. Math., 1993, 2: 15-36

[27] Qiu H., Hancock E. R.. Clustering and embedding using commute times. IEEE Trans. Pattern Anal. Mach. Intell., 2007, 29(11): 1873-1890

[28] Ramsay J. O., Silverman B. W.. Functional data analysis, 2005, New York: Springer-Verlag

[29] Rong G., Cao Y., Guo X.. Spectral mesh deformation. Vis. Comput., 2008, 24(7): 787-796

[30] Rustamov R., Ovsjanikov M., Azencot O. Map-based exploration of intrinsic shape differences and variability, 2013

[31] Shahid N., Bresson X., Bronstein M. M., Vandergheynst P.. Robust principal component analysis on graphs. Int. Conf. Comp. Vision (ICCV), 2015

[32] Shawe-Taylor J., Cristianini N.. Kernel Methods For Pattern Analysis, 2004, Cambridge: Cambridge University Press

[33] Sun J., Ovsjanikov M., Guibas L.. A concise and provably informative multi-scale signature based on heat diffusion. Proceedings of the Symposium on Geometry Processing, Eurographics Association, 2009 1383-1392

[34] Weinberger H.. Variational Methods for Eigenvalue Approximation, 1974

[35] Zaharescu A., Boyer E., Varanasi K., Horaud R.. Surface feature detection and description with applications to mesh matching. Computer Vision and Pattern Recognition, IEEE Conference on CVPR 2009, 2009 373-380

[36] Zhou X., Srebro N.. Error analysis of laplacian eigenmaps for semi-supervised learning. International Conference on Artificial Intelligence and Statistics, 2011 901-908