HORSESHOES IN MULTIDIMENSIONAL SCALING AND LOCAL KERNEL METHODS

• 成果类型: Article
• 署名作者: Diaconis, Persi; Goel, Sharad; Holmes, Susan
• 署名单位: Stanford University; Yahoo! Inc
• 刊物名称: ANNALS OF APPLIED STATISTICS
• ISSN/ISSBN: 1932-6157
• DOI: 10.1214/08-AOAS165
• 发表日期: 2008
• 页码: 777-807
• 关键词: eigenvalues

摘要

Classical Multidimensional scaling (MDS) is a method for visualizing high-dimensional point clouds by mapping to low-dimensional Euclidean space. This mapping is defined in terms of eigenfunctions of a matrix of inter-point dissimilarities. In this paper we analyze in detail multidimensional scaling applied to a specific dataset: the 2005 United States House of Representatives roll call votes. Certain MDS and kernel projections output horseshoes that are characteristic of dimensionality reduction techniques. We show that, in general, a latent ordering of the data gives rise to these patterns when one only has local information. That is, when only the inter-point distances for nearby points are known accurately. Our results provide a rigorous set of results and insight into manifold learning in the special case where the manifold is a curve.