A remark on global positioning from local distances

  1. Amit Singer*
  1. Department of Mathematics, Program in Applied Mathematics, Yale University, New Haven, CT 06520

  1. Communicated by Ronald R. Coifman, Yale University, New Haven, CT, October 18, 2007 (received for review August 17, 2007)

Abstract

Finding the global positioning of points in Euclidean space from a local or partial set of pairwise distances is a problem in geometry that emerges naturally in sensor networks and NMR spectroscopy of proteins. We observe that the eigenvectors of a certain sparse matrix exactly match the sought coordinates. This translates to a simple and efficient algorithm that is robust to noisy distance data.

Footnotes

  • *E-mail: amit.singer{at}yale.edu

  • Author contributions: A.S. performed research and wrote the paper.

  • The author declares no conflict of interest.

« Previous | Next Article »Table of Contents

This Article

  1. Published online before print July 8, 2008, doi: 10.1073/pnas.0709842104 PNAS July 15, 2008 vol. 105 no. 28 9507-9511
  1. » Abstract
  2. Figures Only
  3. Full Text
  4. Full Text (PDF)

Readers Also Viewed

Classifications

Link: Advanced Search

This Week's Issue

  1. February 9, 2010, 107 (6)
  1. Current Issue
  1. Alert me to new issues of PNAS

Most