KMS Of Academy of mathematics and systems sciences, CAS
Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction | |
Ding, Chao1; Qi, Hou-Duo2 | |
2017-07-01 | |
发表期刊 | MATHEMATICAL PROGRAMMING |
ISSN | 0025-5610 |
卷号 | 164期号:1-2页码:341-381 |
摘要 | Classical 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. |
关键词 | Euclidean distance matrix Convex matrix optimization Multidimensional scaling Nonlinear dimensionality reduction Low-rank matrix Error bounds Random graph models |
DOI | 10.1007/s10107-016-1090-7 |
语种 | 英语 |
资助项目 | Engineering and Physical Science Research Council (UK)[EP/K007645/1] ; National Natural Science Foundation of China[11671387] |
WOS研究方向 | Computer Science ; Operations Research & Management Science ; Mathematics |
WOS类目 | Computer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied |
WOS记录号 | WOS:000403450600014 |
出版者 | SPRINGER HEIDELBERG |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/25685 |
专题 | 应用数学研究所 |
通讯作者 | Qi, Hou-Duo |
作者单位 | 1.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 2.Univ Southampton, Sch Math, Southampton SO17 1BJ, Hants, England |
推荐引用方式 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. |
条目包含的文件 | 条目无相关文件。 |
个性服务 |
推荐该条目 |
保存到收藏夹 |
查看访问统计 |
导出为Endnote文件 |
谷歌学术 |
谷歌学术中相似的文章 |
[Ding, Chao]的文章 |
[Qi, Hou-Duo]的文章 |
百度学术 |
百度学术中相似的文章 |
[Ding, Chao]的文章 |
[Qi, Hou-Duo]的文章 |
必应学术 |
必应学术中相似的文章 |
[Ding, Chao]的文章 |
[Qi, Hou-Duo]的文章 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论