Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version

Abstract

This paper addresses the Sensor Network Localization (SNL) problem using received signal strength. The SNL is formulated as an Euclidean Distance Matrix Completion (EDMC) problem under the unit ball sample model. Using the Burer-Monteiro factorization type cost function, the EDMC is solved by Riemannian conjugate gradient with Hager-Zhang line search method on a quotient manifold. A "rank reduction" preprocess is proposed for proper initialization and to achieve global convergence with high probability. Simulations on a synthetic scene show that our approach attains better localization accuracy and is computationally efficient compared to several baseline methods. Characterization of a small local basin of attraction around the global optima of the s-stress function under Bernoulli sampling rule and incoherence matrix completion framework is conducted for the first time. Theoretical result conjectures that the Euclidean distance problem with a structure-less sample mask can be effectively handled using spectral initialization followed by vanilla first-order methods. This preliminary analysis, along with the aforementioned numerical accomplishments, provides insights into revealing the landscape of the s-stress function and may stimulate the design of simpler algorithms to tackle the non-convex formulation of general EDMC problems.

References in corpus (24)

• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Manopt, a Matlab toolbox for optimization on manifolds
• User-friendly tail bounds for sums of random matrices
• Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Guaranteed Matrix Completion via Non-convex Factorization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• A Geometric Analysis of Phase Retrieval
• Incoherence-Optimal Matrix Completion
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• Spectral Methods for Data Science: A Statistical Perspective
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Localization from Incomplete Noisy Distance Measurements
• Low-rank optimization for distance matrix completion
• A Riemannian geometry for low-rank matrix completion
• Localization from Incomplete Euclidean Distance Matrix: Performance Analysis for the SVD-MDS Approach
• Calibration Using Matrix Completion with Application to Ultrasound Tomography
• Perturbation Bounds for Procrustes, Classical Scaling, and Trilateration, with Applications to Manifold Learning
• The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• Riemannian optimization using three different metrics for Hermitian PSD fixed-rank constraints: an extended version

Cited by in corpus (1)

• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version