Prime Rigid Graphs and Multidimensional Scaling with Missing Data
Oskarsson, Magnus LU
; Åström, Karl
LU
and Torstensson, Anna
LU
(2014)
22nd International Conference on Pattern Recognition (ICPR 2014)
p.750-755
- Abstract
- In this paper we investigate the problem of embedding a number of points given certain (but typically not all) inter-pair distance measurements. This problem is relevant for multi-dimensional scaling problems with missing data, and is applicable within anchor-free sensor network node calibration and anchor-free node localization using radio or sound TOA measurements. There are also applications within chemistry for deducing molecular 3D structure given inter-atom distance measurements and within machine learning and visualization of data, where only similarity measures between sample points are provided. The problem has been studied previously within the field of rigid graph theory. Our aim is here to construct numerically stable and... (More)
- In this paper we investigate the problem of embedding a number of points given certain (but typically not all) inter-pair distance measurements. This problem is relevant for multi-dimensional scaling problems with missing data, and is applicable within anchor-free sensor network node calibration and anchor-free node localization using radio or sound TOA measurements. There are also applications within chemistry for deducing molecular 3D structure given inter-atom distance measurements and within machine learning and visualization of data, where only similarity measures between sample points are provided. The problem has been studied previously within the field of rigid graph theory. Our aim is here to construct numerically stable and efficient solvers for finding all embeddings of such minimal rigid graphs. The method is based on the observation that all graphs are either irreducibly rigid, here called prime rigid graphs, or contain smaller rigid graphs. By solving the embedding problem for the prime rigid graphs and for ways of assembling such graphs to other minimal rigid graphs, we show how to (i) calculate the number of embeddings and (ii) construct numerically stable and efficient algorithms for obtaining all embeddings given inter-node measurements. The solvers are verified with experiments on simulated data. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5052497
- author
- Oskarsson, Magnus
LU
; Åström, Karl
LU
and Torstensson, Anna
LU
- organization
- publishing date
- 2014
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Pattern Recognition (ICPR), 2014 22nd International Conference on
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 22nd International Conference on Pattern Recognition (ICPR 2014)
- conference location
- Stockholm, Sweden
- conference dates
- 2014-08-24 - 2014-08-28
- external identifiers
-
- wos:000359818000127
- scopus:84919941117
- ISSN
- 1051-4651
- DOI
- 10.1109/ICPR.2014.139
- language
- English
- LU publication?
- yes
- id
- b96bb484-340b-4fb1-b113-b1096d820dbc (old id 5052497)
- date added to LUP
- 2016-04-01 12:53:02
- date last changed
- 2022-03-29 03:52:30
@inproceedings{b96bb484-340b-4fb1-b113-b1096d820dbc,
abstract = {{In this paper we investigate the problem of embedding a number of points given certain (but typically not all) inter-pair distance measurements. This problem is relevant for multi-dimensional scaling problems with missing data, and is applicable within anchor-free sensor network node calibration and anchor-free node localization using radio or sound TOA measurements. There are also applications within chemistry for deducing molecular 3D structure given inter-atom distance measurements and within machine learning and visualization of data, where only similarity measures between sample points are provided. The problem has been studied previously within the field of rigid graph theory. Our aim is here to construct numerically stable and efficient solvers for finding all embeddings of such minimal rigid graphs. The method is based on the observation that all graphs are either irreducibly rigid, here called prime rigid graphs, or contain smaller rigid graphs. By solving the embedding problem for the prime rigid graphs and for ways of assembling such graphs to other minimal rigid graphs, we show how to (i) calculate the number of embeddings and (ii) construct numerically stable and efficient algorithms for obtaining all embeddings given inter-node measurements. The solvers are verified with experiments on simulated data.}},
author = {{Oskarsson, Magnus and Åström, Karl and Torstensson, Anna}},
booktitle = {{Pattern Recognition (ICPR), 2014 22nd International Conference on}},
issn = {{1051-4651}},
language = {{eng}},
pages = {{750--755}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Prime Rigid Graphs and Multidimensional Scaling with Missing Data}},
url = {{http://dx.doi.org/10.1109/ICPR.2014.139}},
doi = {{10.1109/ICPR.2014.139}},
year = {{2014}},
}