File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10107-013-0726-0
- Scopus: eid_2-s2.0-84920259705
- WOS: WOS:000342158300014
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Computing the nearest Euclidean distance matrix with low embedding dimensions
Title | Computing the nearest Euclidean distance matrix with low embedding dimensions |
---|---|
Authors | |
Keywords | Semismooth Newton-CG method Euclidean distance matrix Majorization method Lagrangian duality Low-rank approximation |
Issue Date | 2013 |
Citation | Mathematical Programming, 2013, v. 147, n. 1-2, p. 351-389 How to Cite? |
Abstract | © 2013, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. 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 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 problems in large scale sensor network localization and molecular conformation. |
Persistent Identifier | http://hdl.handle.net/10722/251084 |
ISSN | 2023 Impact Factor: 2.2 2023 SCImago Journal Rankings: 1.982 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Qi, Hou Duo | - |
dc.contributor.author | Yuan, Xiaoming | - |
dc.date.accessioned | 2018-02-01T01:54:31Z | - |
dc.date.available | 2018-02-01T01:54:31Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Mathematical Programming, 2013, v. 147, n. 1-2, p. 351-389 | - |
dc.identifier.issn | 0025-5610 | - |
dc.identifier.uri | http://hdl.handle.net/10722/251084 | - |
dc.description.abstract | © 2013, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society. 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 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 problems in large scale sensor network localization and molecular conformation. | - |
dc.language | eng | - |
dc.relation.ispartof | Mathematical Programming | - |
dc.subject | Semismooth Newton-CG method | - |
dc.subject | Euclidean distance matrix | - |
dc.subject | Majorization method | - |
dc.subject | Lagrangian duality | - |
dc.subject | Low-rank approximation | - |
dc.title | Computing the nearest Euclidean distance matrix with low embedding dimensions | - |
dc.type | Article | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1007/s10107-013-0726-0 | - |
dc.identifier.scopus | eid_2-s2.0-84920259705 | - |
dc.identifier.volume | 147 | - |
dc.identifier.issue | 1-2 | - |
dc.identifier.spage | 351 | - |
dc.identifier.epage | 389 | - |
dc.identifier.eissn | 1436-4646 | - |
dc.identifier.isi | WOS:000342158300014 | - |
dc.identifier.issnl | 0025-5610 | - |