Advanced

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) In Pattern Recognition (ICPR), 2014 22nd International Conference on 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
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)
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
2015-07-07 12:07:26
date last changed
2017-03-15 09:56:08
@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},
  year         = {2014},
}