×

Perturbation bounds for procrustes, classical scaling, and trilateration, with applications to manifold learning. (English) Zbl 1498.68221

Summary: One of the common tasks in unsupervised learning is dimensionality reduction, where the goal is to find meaningful low-dimensional structures hidden in high-dimensional data. Sometimes referred to as manifold learning, this problem is closely related to the problem of localization, which aims at embedding a weighted graph into a low-dimensional Euclidean space. Several methods have been proposed for localization, and also manifold learning. Nonetheless, the robustness property of most of them is little understood. In this paper, we obtain perturbation bounds for classical scaling and trilateration, which are then applied to derive performance bounds for Isomap, Landmark Isomap, and Maximum Variance Unfolding. A new perturbation bound for procrustes analysis plays a key role.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62R30 Statistics on manifolds
68T10 Pattern recognition, speech recognition

Software:

kappa_SQ
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] Ery Arias-Castro and Thibaut Le Gouic. Unconstrained and curvature-constrained shortestpath distances and their approximation.arXiv preprint arXiv:1706.09441, 2017. · Zbl 1418.53045
[2] Ery Arias-Castro and Bruno Pelletier. On the convergence of maximum variance unfolding. The Journal of Machine Learning Research, 14(1):1747-1770, 2013. · Zbl 1318.62125
[3] Mikhail Belkin and Partha Niyogi. Towards a theoretical foundation for Laplacian-based manifold methods.Journal of Computer and System Sciences, 74(8):1289-1308, 2008. · Zbl 1157.68056
[4] M. Bernstein, V. De Silva, J.C. Langford, and J.B. Tenenbaum. Graph approximations to geodesics on embedded manifolds. Technical report, Technical report, Department of Psychology, Stanford University, 2000.
[5] Rajendra Bhatia.Matrix analysis, volume 169. Springer Science & Business Media, 2013. · Zbl 0863.15001
[6] Pratik Biswas, Tzu-Chen Liang, Kim-Chuan Toh, Yinyu Ye, and Ta-Chung Wang. Semidefinite programming approaches for sensor network localization with noisy distance measurements.Transactions on Automation Science and Engineering, 3(4):360-371, 2006.
[7] R.R. Coifman and S. Lafon. Diffusion maps.Applied and Computational Harmonic Analysis, 21(1):5-30, 2006. · Zbl 1095.68094
[8] V. de Silva and J.B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction.Advances in Neural Information Processing Systems (NIPS), 15:705-712, 2003.
[9] Vin de Silva and Joshua B Tenenbaum. Sparse multidimensional scaling using landmark points. Technical report, Technical report, Stanford University, 2004.
[10] David L Donoho and Carrie Grimes. Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data.Proceedings of the National Academy of Sciences, 100 (10):5591-5596, 2003. · Zbl 1130.62337
[11] Christos Faloutsos and King-Ip Lin. Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. InACM SIGMOD International Conference on Management of Data, volume 24, pages 163-174, 1995.
[12] Herbert Federer. Curvature measures.Transactions of the American Mathematical Society, 93:418-491, 1959. · Zbl 0089.38402
[13] Christopher R Genovese, Marco Perone-Pacifico, Isabella Verdinelli, and Larry Wasserman. Manifold estimation and singular deconvolution under hausdorff loss.The Annals of Statistics, 40(2):941-963, 2012. · Zbl 1274.62237
[14] Evarist Gin´e and Vladimir Koltchinskii.Empirical graph Laplacian approximation of laplace-beltrami operators: Large sample results. InHigh dimensional probability, pages 238-259. Institute of Mathematical Statistics, 2006. · Zbl 1124.60030
[15] Yair Goldberg, Alon Zakai, Dan Kushnir, and Ya’acov Ritov. Manifold learning: The price of normalization.Journal of Machine Learning Research, 9(Aug):1909-1939, 2008. · Zbl 1225.68181
[16] John C Gower. Some distance properties of latent root and vector methods used in multivariate analysis.Biometrika, 53(3-4):325-338, 1966. · Zbl 0192.26003
[17] Matthias Hein, Jean-Yves Audibert, and Ulrike Von Luxburg. From graphs to manifolds: Weak and strong pointwise consistency of graph Laplacians. InConference on Computational Learning Theory (COLT), pages 470-485. Springer, 2005. · Zbl 1095.68097
[18] John T Holodnak and Ilse CF Ipsen. Randomized approximation of the gram matrix: Exact computation and probabilistic bounds.SIAM Journal on Matrix Analysis and Applications, 36(1):110-137, 2015. · Zbl 1330.65061
[19] Ilse CF Ipsen and Thomas Wentworth. The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems.SIAM Journal on Matrix Analysis and Applications, 35(4):1490-1520, 2014. · Zbl 1359.65063
[20] Adel Javanmard and Andrea Montanari. Localization from incomplete noisy distance measurements.Foundations of Computational Mathematics, 13(3):297-345, 2013. · Zbl 1269.05098
[21] Arlene KH Kim and Harrison H Zhou. Tight minimax rates for manifold estimation under hausdorff loss.Electronic Journal of Statistics, 9(1):1562-1582, 2015. · Zbl 1325.62111
[22] Joseph B Kruskal and Judith B Seery. Designing network diagrams. InGeneral Conference on Social Graphics, pages 22-50, 1980.
[23] Drago¸s Niculescu and Badri Nath. DV based positioning in ad hoc networks.Telecommunication Systems, 22(1-4):267-280, 2003.
[24] Alexander Paprotny and Jochen Garcke. On a connection between maximum variance unfolding, shortest path problems and isomap. InConference on Artificial Intelligence and Statistics (AISTATS), pages 859-867, 2012.
[25] John Platt. Fastmap, MetricMap, and Landmark MDS are all Nystrom algorithms. In Conference on Artificial Intelligence and Statistics (AISTATS), 2005.
[26] George AF Seber.Multivariate observations. John Wiley & Sons, 2004.
[27] Yi Shang, Wheeler Ruml, Ying Zhang, and Markus PJ Fromherz. Localization from mere connectivity. InSymposium on Mobile Ad Hoc Networking & Computing, pages 201-212, 2003.
[28] Robin Sibson. Studies in the robustness of multidimensional scaling: Perturbational analysis of classical scaling.Journal of the Royal Statistical Society. Series B (Methodological), pages 217-229, 1979. · Zbl 0413.62046
[29] A. Singer. From graph to manifold Laplacian: The convergence rate.Applied and Computational Harmonic Analysis, 21(1):128-134, 2006. · Zbl 1095.68102
[30] A.K. Smith, X. Huo, and H. Zha. Convergence and rate of convergence of a manifold-based dimension reduction algorithm. InAdvances in Neural Information Processing Systems (NIPS), pages 1529-1536, 2008.
[31] Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network localization.Mathematical Programming, 109(2-3):367-384, 2007. · Zbl 1278.90482
[32] Inge S¨oderkvist. Perturbation analysis of the orthogonal procrustes problem.BIT Numerical Mathematics, 33(4):687-694, 1993. · Zbl 0795.65021
[33] G. W. Stewart and Ji Guang Sun.Matrix perturbation theory. Computer Science and Scientific Computing. Academic Press Inc., Boston, MA, 1990. ISBN 0-12-670230-6. · Zbl 0706.65013
[34] J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction.Science, 290(5500):2319-2323, 2000.
[35] Warren S Torgerson.Theory and methods of scaling. Wiley, 1958. · Zbl 0049.37603
[36] Joel A Tropp. User-friendly tail bounds for sums of random matrices.Foundations of Computational Mathematics, 12(4):389-434, 2012. · Zbl 1259.60008
[37] U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering.The Annals of Statistics, 36(2):555-586, 2008. · Zbl 1133.62045
[38] Jason Tsong-Li Wang, Xiong Wang, King-Ip Lin, Dennis Shasha, Bruce A Shapiro, and Kaizhong Zhang. Evaluating a class of distance-mapping algorithms for data mining and clustering. InConference on Knowledge Discovery and Data Mining (SIGKDD), pages 307-311, 1999.
[39] GA Watson. The solution of orthogonal procrustes problems for a family of orthogonally invariant norms.Advances in Computational Mathematics, 2(4):393-405, 1994. · Zbl 0831.65048
[40] Kilian Q Weinberger and Lawrence K Saul. Unsupervised learning of image manifolds by semidefinite programming.International Journal of Computer Vision, 70(1):77-90, 2006a.
[41] Kilian Q Weinberger, Fei Sha, Qihui Zhu, and Lawrence K Saul. Graph Laplacian regularization for large-scale semidefinite programming. InAdvances in Neural Information Processing Systems (NIPS), pages 1489-1496, 2006.
[42] Killan Q. Weinberger and Lawrence K. Saul. An introduction to nonlinear dimensionality reduction by maximum variance unfolding. InConference on Artificial Intelligence, volume 2, pages 1683-1686. AAAI, 2006b.
[43] Qiang Ye and Weifeng Zhi. Discrete hessian eigenmaps method for dimensionality reduction. Journal of Computational and Applied Mathematics, 278:197-212, 2015. · Zbl 1304.65110
[44] Forrest W Young.Multidimensional scaling: History, theory, and applications. Psychology Press, 2013.
[45] H. Zha and Z. Zhang. Continuum isomap for manifold learnings.Computational Statistics & Data Analysis, 52(1):184-200, 2007. · Zbl 1452.62144
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.