×
Liu, Hao; Yao, Zhigang; Leung, Shingyu; Chan, Tony F.

A level set based variational principal flow method for nonparametric dimension reduction on Riemannian manifolds. (English) Zbl 1379.65041

SIAM J. Sci. Comput. 39, No. 4, A1616-A1646 (2017).
Summary: We propose a variational formulation for dimension reduction on Riemannian manifolds. The algorithm is developed based on the level set method together with a recently developed principal flow algorithm. The original principal flow algorithm is a Lagrangian technique which extends the principal component analysis (PCA) to dimension reduction on Riemannian manifolds. We propose to incorporate the level set method to obtain a fully implicit formulation so that the overall algorithm can naturally handle various topological changes in the curve evolution. The variational formulation consists of two terms which try to balance the contributions from both the dataset itself and the principal direction by the PCA. We will demonstrate that the method is insensitive to the initial guess and is robust enough for noisy data.

Cited in 4 Documents

MSC:

65K10 Numerical optimization and variational techniques
62H25 Factor analysis and principal components; correspondence analysis
49J20 Existence theories for optimal control problems involving partial differential equations
49J53 Set-valued and variational analysis

Keywords:

partial differential equations; implicit surfaces; level set method; dimensional reduction; variational formulation; Riemannian manifolds; principal flow algorithm; principal component analysis
Cite Review PDF
Full Text: DOI

References:

[1] N. Amenta and M. Bern, {\it Surface reconstruction by Voronoi filtering}, in Proceedings of the 14th ACM Symposium on Computational Geometry, 1998. · Zbl 0939.68138
[2] M. Bertalmio, L.-T. Cheng, S. Osher, and G. Sapiro, {\it Variational problems and partial differential equations on implicit surfaces}, J. Comput. Phys., 174 (2001), pp. 759-780. · Zbl 0991.65055
[3] X. Bresson, S. Esedoglu, P. Vandergheynst, J.-P. Thiran, and S. Osher, {\it Fast global minimization of the active contour/snake model}, J. Math. Imaging Vision, 28 (2007), pp. 151-167. · Zbl 1523.94005
[4] P. Burchard, L.-T. Cheng, B. Merriman, and S. Osher, {\it Motion of curves in three spatial dimensions using a level set approach}, J. Comput. Phys., 170 (2001), pp. 720-741. · Zbl 0991.65077
[5] V. Caselles, R. Kimmel, and G. Sapiro, {\it Geodesic active contours}, Int. J. Comput. Vis., 22 (1997), pp. 61-79. · Zbl 0894.68131
[6] T.F. Chan, S. Esedoḡlu, and M. Nikolova, {\it Algorithms for finding global minimizers of image segmentation and denoising models}, SIAM J. Appl. Math., 66 (2006), pp. 1632-1648. · Zbl 1117.94002
[7] W. Chen, C.S. Chou, and C.Y. Kao, {\it L}ax-Friedrichs fast sweeping methods for steady state problems for hyperbolic conservation laws, J. Comput. Phys., 234 (2013), pp. 452-471. · Zbl 1284.35275
[8] L.-T. Cheng, {\it Efficient level set methods for constructing wavefronts in three spatial dimensions}, J. Comput. Phys., 226 (2007), pp. 2250-2270. · Zbl 1131.78016
[9] L.-T. Cheng, P. Burchard, B. Merriman, and S. Osher, {\it Motion of curves constrained on surfaces using a level-set approach}, J. Comput. Phys., 175 (2002), pp. 604-644. · Zbl 0996.65013
[10] H. Edelsbrunner, {\it Shapre reconstruction with Delaunay complex}, in Proceedings of LATIN ’98: Theoretical Informatics, Vol. 1380, Springer-Verlag, New York, 1998. · Zbl 0905.65014
[11] P.T. Fletcher and S. Joshi, {\it Riemannian Geometry for the Statistical Analysis of Diffusion Tensor Data}, Signal Processing, 87 (2007), pp. 250-262. · Zbl 1186.94126
[12] P.T. Fletcher, C. Lu, S.M. Pizer, and S. Joshi, {\it Principal geodesic analysis for the study of nonlinear statistics of shape}, IEEE Trans. Med. Imag., 23 (2004), pp. 995-1005.
[13] A. Goh and R. Vidal, {\it Clustering and dimensionality reduction on Riemannian manifolds}, in Proceedings of CVPR, 2008.
[14] C.R. Goodall, {\it Procrustes methods in the statistical analysis of shape}, J. Roy. Statist. Soc. Ser. B, 53 (1991), pp. 285-339. · Zbl 0800.62346
[15] T. Hastie and W. Stuetzle, {\it Principal curves}, J. Amer. Statist. Assoc., 84 (1989), pp. 502-516. · Zbl 0679.62048
[16] S. Hauberg, {\it Principal curves on Riemannian manifolds}, IEEE Trans. Pattern Anal. Mach. Intell., 38 (2016), pp. 1915-1921.
[17] S. Huckemann and H. Ziezold, {\it Principal component analysis for Riemannian manifolds, with an application to triangular shape spaces}, Adv. Appl. Probab., 38 (2006), pp. 299-319. · Zbl 1099.62059
[18] G.S. Jiang and D. Peng, {\it Weighted ENO schemes for Hamilton-Jacobi equations}, SIAM J. Sci. Comput., 21 (2000), pp. 2126-2143. · Zbl 0957.35014
[19] S. Jung, I.L. Dryden, and J.S. Marron, {\it Analysis of principal nested spheres}, Biometrika, 99 (2012), pp. 551-568. · Zbl 1437.62507
[20] C.Y. Kao, S.J. Osher, and J. Qian, {\it L}ax-Friedrichs sweeping schemes for static Hamilton-Jacobi equations, J. Comput. Phys., 196 (2004), pp. 367-391. · Zbl 1053.65088
[21] M. Kass, A. Witkin, and D. Terzopoulos, {\it Snakes: Active contour models}, Int. J. Comput. Vis., 1 (1998), pp. 321-331.
[22] K. Kenobi, I.L. Dryden, and H. Le, {\it Shape curves and geodesic modelling}, Biometrika, 97 (2010), pp. 567-584. · Zbl 1195.62110
[23] A. Kume, I.L. Dryden, and H. Le, {\it Shape-space smoothing splines for planar landmark data}, Biometrika, 94 (2007), pp. 513-528. · Zbl 1134.62044
[24] S.-M. Lee, A.L. Abbott, and P.A. Araman, {\it Dimensionality reduction and clustering on statistical manifolds}, in Proceedings of CVPR, 2007.
[25] S. Leung and S. Osher, {\it Fast global minimization of the active contour model with TV-inpainting and two-phase denoising}, in Proceedings of the 3rd IEEE Workshop on Variational, Geometric and Level Set Methods in Computer Vision, 2005, pp. 149-160. · Zbl 1159.68595
[26] S. Leung and J. Qian, {\it An adjoint state method for 3D transmission traveltime tomography using first arrival}, Commun. Math. Sci., 4 (2006), pp. 249-266. · Zbl 1096.65062
[27] W.B. Li and S. Leung, {\it A fast local level set adjoint state method for first arrival transmission traveltime tomography with discontinuous slowness}, Geophys. J. Int., 195 (2013), pp. 582-596.
[28] W.B. Li, S. Leung, and J. Qian, {\it A level-set adjoint-state method for crosswell transmission-reflection traveltime tomography}, Geophys. J. Int., 199 (2014), pp. 348-367.
[29] J. Liang, F. Park, and H. Zhao, {\it Robust and efficient implicit surface reconstruction for point clouds based on convexified image segmentation}, J. Sci. Comput., 54 (2013), pp. 577-602.
[30] T. Lin, H. Zha, and S.U. Lee, {\it Riemannian manifold learning for nonlinear dimensionality reduction}, in Proceedings of ECCV, 2006.
[31] X.D. Liu, S.J. Osher, and T. Chan, {\it Weighted essentially nonoscillatory schemes}, J. Comput. Phys., 115 (1994), pp. 200-212. · Zbl 0811.65076
[32] F. Memoli and G. Sapiro, {\it Fast computation of weighted distance functions and geodesics on implicit hyper-surfaces}, J. Comput. Phys., 173 (2001), pp. 730-764. · Zbl 0991.65018
[33] C. Min, {\it Local level set methods in high dimension and codimension}, J. Comput. Phys., 200 (2004), pp. 368-382. · Zbl 1086.65088
[34] S.J. Osher and R.P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Springer-Verlag, New York, 2003. · Zbl 1026.76001
[35] S.J. Osher and J.A. Sethian, {\it Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations}, J. Comput. Phys., 79 (1988), pp. 12-49. · Zbl 0659.65132
[36] V.M. Panaretoes, T. Pham, and Z. Yao, {\it Principal flows}, J. Amer. Statist. Assoc., 109 (2014), pp. 424-436. · Zbl 1367.62187
[37] D. Peng, B. Merriman, S. Osher, H.K. Zhao, and M. Kang, {\it A PDE-based fast local level set method}, J. Comput. Phys., 155 (1999), pp. 410-438. · Zbl 0964.76069
[38] J.A. Sethian, {\it Level Set Methods}, 2nd ed., Cambridge University Press, Cambridge, 1999. · Zbl 0929.65066
[39] C.W. Shu and S.J. Osher, {\it Efficient implementation of essentially non-oscillatory shock capturing schemes}, J. Comput. Phys., 77 (1988), pp. 439-471. · Zbl 0653.65072
[40] P. Smereka, {\it Spiral crystal growth}, Phys. D, 138 (2000), pp. 282-301. · Zbl 0957.80002
[41] J. Su, I.L. Dryden, E. Klassen, H. Le, and A. Srivastava, {\it Fitting smoothing splines to time-indexed, noisy points on nonlinear manifolds}, Image Vis. Comput., 30 (2012), pp. 428-442.
[42] T. Tasdizen, R. Whitaker, P. Burchard, and S. Osher, {\it Geometric surface processing via anisotropic diffusion of normals}, in Proceedings of IEEE Visualization, 2002, pp. 125-132.
[43] T. Tasdizen, R. Whitaker, P. Burchard, and S. Osher, {\it Geometric surface processing via normal maps}, ACM Trans. Graphics, 22 (2003), pp. 1012-1033.
[44] L.J.P. Van der Maaten, E.O. Postma, and H.J. Van den Herik, {\it Dimensionality reduction: A comparative review}, J. Mach. Learn. Res., 10 (2009), pp. 66-71.
[45] T. Wong and S. Leung, {\it A fast sweeping method for eikonal equations on implicit surfaces}, J. Sci. Comput., 67 (2016), pp. 837-859. · Zbl 1343.65129
[46] Z. Yao and T. Pham, {\it Principal Sub-Manifolds}, manuscript, 2016.
[47] H.K. Zhao, {\it Fast sweeping method for eikonal equations}, Math. Comp., 74 (2005), pp. 603-627. · Zbl 1070.65113
[48] H.-K. Zhao, T. Chan, B. Merriman, and S.J. Osher, {\it A variational level set approach for multiphase motion}, J. Comput. Phys., 127 (1996), pp. 179-195. · Zbl 0860.65050
[49] H.-K. Zhao, S. Osher, and R. Fedkiw, {\it Fast surface reconstruction using the level set method}, in Proceedings of the IEEE Workshop on Variational and Level Set Methods, 2001, pp. 194-202.
[50] H.K. Zhao, S. Osher, B. Merriman, and M. Kang, {\it Implicit and non-parametric shape reconstruction from unorganized points using variational level set method}, Comput. Vis. Image Underst., 80 (2000), pp. 295-319. · Zbl 1011.68538
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.