Graph connection Laplacian methods can be made robust to noise. (English) Zbl 1350.60036

Summary: Recently, several data analytic techniques based on graph connection Laplacian (GCL) ideas have appeared in the literature. At this point, the properties of these methods are starting to be understood in the setting where the data is observed without noise. We study the impact of additive noise on these methods and show that they are remarkably robust. As a by-product of our analysis, we propose modifications of the standard algorithms that increase their robustness to noise. We illustrate our results in numerical simulations.


60F99 Limit theorems in probability theory
60B20 Random matrices (probabilistic aspects)
65C60 Computational problems in statistics (MSC2010)
Full Text: DOI arXiv Euclid


[1] Alexeev, B., Bandeira, A. S., Fickus, M. and Mixon, D. G. (2014). Phase retrieval with polarization. SIAM J. Imaging Sci. 7 35-66. · Zbl 1304.49071 · doi:10.1137/12089939X
[2] Bandeira, A. S., Singer, A. and Spielman, D. A. (2013). A Cheeger inequality for the graph connection Laplacian. SIAM J. Matrix Anal. Appl. 34 1611-1630. · Zbl 1134.62023 · doi:10.1016/j.jspi.2007.07.012
[3] Batard, T. and Sochen, N. (2012). Polyakov action on (\(\rho,G\))-equivariant functions application to color image regularization. In Scale Space and Variational Methods in Computer Vision 483-494. Springer, Berlin.
[4] Batard, T. and Sochen, N. (2014). A class of generalized Laplacians on vector bundles devoted to multi-channel image processing. J. Math. Imaging Vision 48 517-543. · Zbl 1378.94003 · doi:10.1007/s10851-013-0426-7
[5] Bhatia, R. (1997). Matrix Analysis. Graduate Texts in Mathematics 169 . Springer, New York. · Zbl 0863.15001
[6] Boyer, D. M., Lipman, Y., Clair, E. S., Puente, J., Patel, B. A., Funkhouser, T., Jernvall, J. and Daubechies, I. (2011). Algorithms to automatically quantify the geometric similarity of anatomical surfaces. Proc. Natl. Acad. Sci. USA 108 18221-18226.
[7] Chen, P., Lin, C.-L. and Chern, I.-L. (2013). A perfect match condition for point-set matching problems using the optimal mass transport approach. SIAM J. Imaging Sci. 6 730-764. · Zbl 1280.49032 · doi:10.1137/12086443X
[8] Chung, F. and Kempton, M. (2013). A local clustering algorithm for connection graphs. In Algorithms and Models for the Web Graph (A. Bonato, M. Mitzenmacher and P. Pralat, eds.). Lecture Notes in Computer Science 8305 26-43. Springer, Berlin. · Zbl 1342.05158 · doi:10.1007/978-3-319-03536-9_3
[9] Chung, F., Zhao, W. and Kempton, M. (2012). Ranking and sparsifying a connection graph. In Algorithms and Models for the Web Graph (A. Bonato and J. Janssen, eds.). Lecture Notes in Computer Science 7323 66-77. Springer, Berlin. · Zbl 1342.05182 · doi:10.1007/978-3-642-30541-2_6
[10] Collins, A., Zomorodian, A., Carlsson, G. and Guibas, L. J. (2004). A barcode shape descriptor for curve point cloud data. Computers & Graphics 28 881-894.
[11] Cucuringu, M., Lipman, Y. and Singer, A. (2012). Sensor network localization by eigenvector synchronization over the Euclidean group. ACM Trans. Sens. Netw. 8 19:1-19:42.
[12] Cucuringu, M., Singer, A. and Cowburn, D. (2012). Eigenvector synchronization, graph rigidity and the molecule problem. Inf. Inference 1 21-67. · Zbl 1278.05231 · doi:10.1093/imaiai/ias002
[13] Diaconis, P. and Freedman, D. (1984). Asymptotics of graphical projection pursuit. Ann. Statist. 12 793-815. · Zbl 0559.62002 · doi:10.1214/aos/1176346703
[14] El Karoui, N. (2008). Operator norm consistent estimation of large-dimensional sparse covariance matrices. Ann. Statist. 36 2717-2756. · Zbl 1196.62064 · doi:10.1214/07-AOS559
[15] El Karoui, N. (2009). Concentration of measure and spectra of random matrices: Applications to correlation matrices, elliptical distributions and beyond. Ann. Appl. Probab. 19 2362-2405. · Zbl 1255.62156 · doi:10.1214/08-AAP548
[16] El Karoui, N. (2010). On information plus noise kernel random matrices. Ann. Statist. 38 3191-3216. · Zbl 1200.62056 · doi:10.1214/10-AOS801
[17] El Karoui, N., Bean, D., Bickel, P. J., Lim, C. and Yu, B. (2013). On robust regression with high-dimensional predictors. Proc. Natl. Acad. Sci. USA 110 14557-14562. · Zbl 1359.62184 · doi:10.1073/pnas.1307842110
[18] El Karoui, N. and Wu, H.-T. (2013). Vector diffusion maps and random matrices with random blocks. Available at . arXiv:1310.0188
[19] El Karoui, N. and Wu, H. (2015). Supplement to “Graph connection Laplacian methods can be made robust to noise.” .
[20] Epstein, C. L. (2008). Introduction to the Mathematics of Medical Imaging , 2nd ed. SIAM, Philadelphia, PA. · Zbl 1305.92002
[21] Fagin, R., Kumar, R. and Sivakumar, D. (2003). Comparing top \(k\) lists. SIAM J. Discrete Math. 17 134-160 (electronic). · Zbl 1057.68075 · doi:10.1137/S0895480102412856
[22] Hadani, R. and Singer, A. (2011). Representation theoretic patterns in three dimensional cryo-electron microscopy I: The intrinsic reconstitution algorithm. Ann. of Math. (2) 174 1219-1241. · Zbl 1227.92036 · doi:10.4007/annals.2011.174.2.11
[23] Hall, P., Marron, J. S. and Neeman, A. (2005). Geometric representation of high dimension, low sample size data. J. R. Stat. Soc. Ser. B Stat. Methodol. 67 427-444. · Zbl 1069.62097 · doi:10.1111/j.1467-9868.2005.00510.x
[24] Huang, Q.-X., Su, H. and Guibas, L. (2013). Fine-grained semi-supervised labeling of large shape collections. ACM Transactions on Graphics ( TOG ) 32 190.
[25] Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89 . Amer. Math. Soc., Providence, RI. · Zbl 0995.60002
[26] Lipman, Y., Al-Aifari, R. and Daubechies, I. (2013). Continuous Procrustes distance between two surfaces. Comm. Pure Appl. Math. 66 934-964. · Zbl 1276.68157 · doi:10.1002/cpa.21444
[27] Marchesini, S., Tu, Y.-C. and Wu, H.-T. (2015). Alternating projection, ptychographic imaging and phase synchronization. Appl. Comput. Harmon. Anal. . Available at arXiv:1402.0550 . arXiv: arXiv:1402.0550 · Zbl 1388.94015
[28] Mémoli, F. and Sapiro, G. (2005). A theoretical and computational framework for isometry invariant recognition of point cloud data. Found. Comput. Math. 5 313-347. · Zbl 1101.53022 · doi:10.1007/s10208-004-0145-y
[29] Niyogi, P., Smale, S. and Weinberger, S. (2009). Finding the homology of submanifolds with high confidence from random samples. In Twentieth Anniversary Volume 1-23. Springer, New York. · Zbl 1177.62003
[30] Singer, A. (2011). Angular synchronization by eigenvectors and semidefinite programming. Appl. Comput. Harmon. Anal. 30 20-36. · Zbl 1206.90116 · doi:10.1016/j.acha.2010.02.001
[31] Singer, A. and Wu, H.-T. (2012). Vector diffusion maps and the connection Laplacian. Comm. Pure Appl. Math. 65 1067-1144. · Zbl 1320.68146 · doi:10.1002/cpa.21395
[32] Singer, A. and Wu, H.-T. (2013). Two-dimensional tomography from noisy projections taken at unknown random directions. SIAM J. Imaging Sci. 6 136-175. · Zbl 1279.68339 · doi:10.1137/090764657
[33] Singer, A. and Wu, H.-T. (2013). Spectral convergence of the connection laplacian from random samples. Submitted.
[34] Singer, A., Zhao, Z., Shkolnisky, Y. and Hadani, R. (2011). Viewing angle classification of cryo-electron microscopy images using eigenvectors. SIAM J. Imaging Sci. 4 723-759. · Zbl 1216.92046 · doi:10.1137/090778390
[35] Stewart, G. W. and Sun, J. G. (1990). Matrix Perturbation Theory . Academic Press, Boston, MA. · Zbl 0706.65013
[36] Sun, J., Ovsjanikov, M. and Guibas, L. (2009). A concise and provably informative multi-scale signature based on heat diffusion. In Proceedings of the Symposium on Geometry Processing , SGP ’ 09 1383-1392. Eurographics Association.
[37] Talmon, R., Cohen, I., Gannot, S. and Coifman, R. (2013). Diffusion maps for signal processing: A deeper look at manifold-learning techniques based on kernels and graphs. IEEE Signal Process. Mag. 30 75-86.
[38] van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge Series in Statistical and Probabilistic Mathematics 3 . Cambridge Univ. Press, Cambridge. · Zbl 0910.62001 · doi:10.1017/CBO9780511802256
[39] Wang, F., Huang, Q. and Guibas, L. J. (2013). Image co-segmentation via consistent functional maps. In The IEEE International Conference on Computer Vision ( ICCV ).
[40] Zhao, Z. and Singer, A. (2013). Rotationally invariant image representation for viewing direction classification in cryo-EM. Available at . arXiv:1309.7643
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.