時(shí)　間: 2013年1月17日(周四)15:30-16:30

地　點(diǎn):研究生樓106

報(bào)告人: Houduo Qi （戚厚鐸），University of Southampton, UK

報(bào)告人簡(jiǎn)介:

戚厚鐸, http://www.personal.soton.ac.uk/hdqi
　　現(xiàn)為英國(guó)南安普敦大學(xué)高級(jí)講師，博士生導(dǎo)師。1990年畢業(yè)于北京大學(xué)統(tǒng)計(jì)學(xué)專(zhuān)業(yè)，1993年獲曲阜師范大學(xué)碩士學(xué)位, 1996年中國(guó)科學(xué)研究院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所博士畢業(yè)。曾在香港理工大學(xué)、新南威爾士大學(xué)等做博士后研究，獲澳大利亞研究委員會(huì)（ARC）資助，以及ARC和享有全球盛譽(yù)的Queen Elizabeth II Fellowship獎(jiǎng)勵(lì)?，F(xiàn)為亞太運(yùn)籌學(xué)雜志（APJOR）副主編。研究方向有：約束優(yōu)化、矩陣優(yōu)化、變分不等式、數(shù)值分析等。在國(guó)際頂級(jí)期刊SIAM on Optimization, Mathematical Programming 等雜志發(fā)表高水平研究論文十余篇。

Title: Computing the Nearest Euclidean Distance Matrix with Low Embedding Dimensions

Abstract: Euclidean distance embedding appears in many high-profile applications including wireless sensor network localization, where not all pairwise distances among sensors are known or accurate. The classical Multi-Dimensional Scaling (cMDS) generally works well when the partial or contaminated Euclidean Distance Matrix (EDM) is close to the true EDM, but otherwise performs poorly. A natural step preceding cMDS would be to calculate the nearest EDM to the known matrix. A crucial condition on the desired nearest EDM is for it to have a low embedding dimension and this makes the problem nonconvex.
　　There exists a large body of publications that deal with this problem. Some try to solve the problem directly and some are the type of convex relaxations of it. In this paper, we propose a numerical method that aims to solve this problem directly. Our method is strongly motivated by the majorized penalty method of Gao and Sun for low-rank positive semi-definite matrix optimization problems. The basic geometric object in our study is the set of EDMs having a low embedding dimension. We establish a {/em zero} duality gap result between the problem and its Lagrangian dual problem, which also motivates the majorization approach adopted. Numerical results show that the method works well for the Euclidean embedding of Network coordinate systems and for a class of large scale sensor network localization problems. This is a joint work with Dr Yuan Xiaoming of Hong Kong Baptist University.