A remark on global positioning from local distances

Amit Singer

Type: Article

Publication Date: 2008-07-09

Citations: 119

DOI: https://doi.org/10.1073/pnas.0709842104

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.

Locations

Proceedings of the National Academy of Sciences - View
PubMed Central - View
Europe PMC (PubMed Central) - View - PDF
PubMed - View

Similar Works

Action	Title	Year	Authors
+	None	1999	Ming Liao
+	None	2001	I. N. Kostin
+	None	1999	Yong-Gao Chen Imre Z. Ruzsa
+	None	2003	Paul Sablonnière
+	None	2001	Emmanuel Fragnière Jacek Gondzio Robert Sarkissian
+	None	1998	G. Sardanashvily
+	None	1998	Hans Keiding
+	None	2003	Haihua Feng Vincenzo Galdi David A. Castañón
+	None	2003	V. Z. Kanchukoev B. S. Karamurzov В. А. Созаев Vladimir Chernov
+	None	2001	Petr Habala Nicole Tomczak-Jaegermann
+	None	2001	S. E. Kozlov
+ PDF Chat	None	2008	田村直義
+	None	2001	Joaquin Soriano
+	None	2001	Shigetaka Fukuda
+	None	2003	Solomon Friedberg
+	None	2003	Igor Belegradek
+	None	1997	Salih Çelïk
+	None	2001	M. de Montigny Hubert de Guise
+	None	2001	A. Yu. Kolesov Н. Х. Розов
+	None	2002	D. G. Djumbayeva Erlan Nursultanov

Works That Cite This (56)

Action	Title	Year	Authors
+	1-Bit Matrix Completion	2012	Mark A. Davenport Yaniv Plan E. van den Berg Mary Wootters
+	Uniqueness of Low-Rank Matrix Completion by Rigidity Theory	2009	Amit Singer Mihai Cucuringu
+	Matrix estimation by Universal Singular Value Thresholding	2014	Sourav Chatterjee
+ PDF Chat	A tensor-based method for missing traffic data completion	2013	Huachun Tan Guangdong Feng Jianshuai Feng Wuhong Wang Yujin Zhang Feng Li
+ PDF Chat	The Many Faces of Degeneracy in Conic Optimization	2017	Dmitriy Drusvyatskiy Henry Wolkowicz
+ PDF Chat	Typical and generic ranks in matrix completion	2019	Daniel Irving Bernstein Grigoriy Blekherman Rainer Sinn
+	The Noise-sensitivity phase transition in spectral group synchronization over compact groups	2019	Elad Romanov Matan Gavish
+	A modified primal-dual method with applications to some sparse recovery problems	2018	Yongchao Yu Jigen Peng
+ PDF Chat	Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier	2017	Dmitriy Drusvyatskiy Nathan Krislock Yuen-Lam Voronin Henry Wolkowicz
+ PDF Chat	Matrix Completion for Structured Observations	2018	Denali Molitor Deanna Needell

Works Cited by This (9)

Action	Title	Year	Authors
+	Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones	1999	J.F. Sturm
+	Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps	2005	Ronald R. Coifman Stéphane Lafon A. B. Lee Mauro Maggioni Boaz Nadler Frederick Warner Steven W. Zucker
+ PDF Chat	The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem	2006	Jun Sun Stephen Boyd Lin Xiao Persi Diaconis
+ PDF Chat	Global Continuation for Distance Geometry Problems	1997	Jorge J. Morè Zhijun Wu
+	Graph Laplacian Regularization for Large-Scale Semidefinite Programming	2007	Kilian Q. Weinberger Fei Sha Qihui Zhu Lawrence K. Saul
+	Weighted low-rank approximations	2003	Nathan Srebro Tommi Jaakkola
+	Sur La Definition Axiomatique D'Une Classe D'Espaces Vectoriels Distancies Applicables Vectoriellement Sur L'Espace de Hilbert	1935	Maurice Fréchet
+	Remarks to Maurice Frechet's Article ``Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De Hilbert	1935	I. J. Schoenberg
+	Semidefinite Programming	1996	Lieven Vandenberghe Stephen Boyd