Yinyu Ye (Stanford University, USA)

Semidefinite programming, graph realization, and sensor network localization
Wednesday 27 August 2008 at 15.30, JCMB 5215


We present recent progresses in semidefinite programming (SDP) based model and method for the position estimation problem in Euclidean distance geometry such as graph realization and wireless sensor network localization. The optimization problem is set up so as to minimize the error in sensor positions to fit incomplete and noisy distance measures. We develop an SDP relaxation model and use the duality theory to derive necessary and/or sufficient conditions for whether a network is "localizable" or not, when the distance measures are accurate. We also present probabilistic analyses of the SDP solution when the distance measures are noisy. In all cases, observable gauges are developed to certify the quality of the position estimation of every sensor and to detect possible erroneous sensors. Furthermore, we develop regularization and gradient-based local search methods to round and improve the SDP solution. Computations will be demonstrated to show the effectiveness of the method.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996