Optimization Online


Noisy Euclidean distance realization: robust facial reduction and the Pareto frontier

D. Drusvyatskiy(ddrusv***at***uw.edu)
N. Krislock(nkrislock***at***niu.edu)
Y.-L. Voronin(yuen-lam.voronin***at***colorado.edu)
H. Wolkowicz(hwolkowicz***at***uwaterloo.ca )

Abstract: We present two algorithms for large-scale low-rank Euclidean distance matrix completion problems, based on semidefinite optimization. Our first method works by relating cliques in the graph of the known distances to faces of the positive semidefinite cone, yielding a combinatorial procedure that is provably robust and parallelizable. Our second algorithm is a first order method for maximizing the trace---a popular low-rank inducing regularizer---in the formulation of the problem with a constrained misfit. Both of the methods output a point configuration that can serve as a high-quality initialization for local optimization techniques. Numerical experiments on large-scale sensor localization problems illustrate the two approaches.

Keywords: Euclidean distance matrices, sensor network localization, convex optimization, facial reduction, Frank-Wolfe algorithm, semidefinite programming

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: 08/2015

Download: [PDF]

Entry Submitted: 08/26/2015
Entry Accepted: 08/26/2015
Entry Last Modified: 08/26/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society