Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
From MaRDI portal
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.
Recommendations
- Robust Hausdorff distance measure for face recognition
- Robust principal component analysis using facial reduction
- scientific article; zbMATH DE number 1726611
- F-norm distance metric based robust 2DPCA and face recognition
- Facial feature detection using distance vector fields
- Circum-Euclidean distance matrices and faces
- A facial reduction approach for the single source localization problem
Cites work
- (Robust) edge-based semidefinite programming relaxation of sensor network localization
- A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
- A remark on global positioning from local distances
- Algorithm 920: SFSDP: a sparse version of full semidefinite programming relaxation for sensor network localization problems
- Approximate and exact completion problems for Euclidean distance matrices using semidefinite programming
- Block matrices and multispherical structure of distance matrices
- Characterizing generic global rigidity
- Circum-Euclidean distance matrices and faces
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Cuts, matrix completions and graph rigidity
- Equality relating Euclidean distance cone to positive semidefinite cone
- Euclidean distance geometry and applications
- Euclidean distance matrices: new characterization and boundary properties
- Explicit sensor network localization using semidefinite representations and facial reductions
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Faces of the cone of Euclidean distance matrices: characterizations, structure and induced geometry
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Graph rigidity via Euclidean distance matrices
- scientific article; zbMATH DE number 1182568 (Why is no real title available?)
- scientific article; zbMATH DE number 1534304 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3345848 (Why is no real title available?)
- Iterative universal rigidity
- Level-set methods for convex optimization
- Localization from incomplete noisy distance measurements
- Majorization for the eigenvalues of Euclidean distance matrices
- Multispherical Euclidean distance matrices
- Probing the Pareto frontier for basis pursuit solutions
- Randomized Sketches of Convex Programs With Sharp Guarantees
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Some new bounds on perturbation of subspaces
- Sparse Optimization with Least-Squares Constraints
- Sum of squares method for sensor network localization
- The cone of distance matrices
- The rotation of eigenvectors by a perturbation. II
- The Rotation of Eigenvectors by a Perturbation. III
- Theory of semidefinite programming for sensor network localization
- Universal Rigidity and Edge Sparsification for Sensor Network Localization
- Variational properties of value functions
Cited in
(14)- Level-set methods for convex optimization
- Low-rank matrix completion using nuclear norm minimization and facial reduction
- Noisy Euclidean distance matrix completion with a single missing node
- A least-squares approach for discretizable distance geometry problems with inexact distances
- Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints
- Robust principal component analysis using facial reduction
- Robust Euclidean embedding via EDM optimization
- Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs
- Convex optimization learning of faithful Euclidean distance representations in nonlinear dimensionality reduction
- Coordinate shadows of semidefinite and Euclidean distance matrices
- A facial reduction approach for the single source localization problem
- Perturbation analysis of the Euclidean distance matrix optimization problem and its numerical implications
- Multiscale semidefinite programming approach to positioning problems with pairwise structure
- Stability of sequential lateration and of stress minimization in the presence of noise
This page was built for publication: Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4588863)
