CSpace  > 应用数学研究所
Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
Ding, Chao1; Qi, Hou-Duo2
2017-07-01
Source PublicationMATHEMATICAL PROGRAMMING
ISSN0025-5610
Volume164Issue:1-2Pages:341-381
AbstractClassical multidimensional scaling only works well when the noisy distances observed in a high dimensional space can be faithfully represented by Euclidean distances in a low dimensional space. Advanced models such as Maximum Variance Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite Programming (SDP) to reconstruct such faithful representations. While those SDP models are capable of producing high quality configuration numerically, they suffer two major drawbacks. One is that there exist no theoretically guaranteed bounds on the quality of the configuration. The other is that they are slow in computation when the data points are beyond moderate size. In this paper, we propose a convex optimization model of Euclidean distance matrices. We establish a non-asymptotic error bound for the random graph model with sub-Gaussian noise, and prove that our model produces a matrix estimator of high accuracy when the order of the uniform sample size is roughly the degree of freedom of a low-rank matrix up to a logarithmic factor. Our results partially explain why MVU and MVE often work well. Moreover, the convex optimization model can be efficiently solved by a recently proposed 3-block alternating direction method of multipliers. Numerical experiments show that the model can produce configurations of high quality on large data points that the SDP approach would struggle to cope with.
KeywordEuclidean distance matrix Convex matrix optimization Multidimensional scaling Nonlinear dimensionality reduction Low-rank matrix Error bounds Random graph models
DOI10.1007/s10107-016-1090-7
Language英语
Funding ProjectEngineering and Physical Science Research Council (UK)[EP/K007645/1] ; National Natural Science Foundation of China[11671387]
WOS Research AreaComputer Science ; Operations Research & Management Science ; Mathematics
WOS SubjectComputer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000403450600014
PublisherSPRINGER HEIDELBERG
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/25685
Collection应用数学研究所
Corresponding AuthorQi, Hou-Duo
Affiliation1.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China
2.Univ Southampton, Sch Math, Southampton SO17 1BJ, Hants, England
Recommended Citation
GB/T 7714
Ding, Chao,Qi, Hou-Duo. Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction[J]. MATHEMATICAL PROGRAMMING,2017,164(1-2):341-381.
APA Ding, Chao,&Qi, Hou-Duo.(2017).Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction.MATHEMATICAL PROGRAMMING,164(1-2),341-381.
MLA Ding, Chao,et al."Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction".MATHEMATICAL PROGRAMMING 164.1-2(2017):341-381.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Ding, Chao]'s Articles
[Qi, Hou-Duo]'s Articles
Baidu academic
Similar articles in Baidu academic
[Ding, Chao]'s Articles
[Qi, Hou-Duo]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Ding, Chao]'s Articles
[Qi, Hou-Duo]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.