Sparsity-Promoting Sensor Selection for Non-linear Measurement Models

Sundeep Prabhakar Chepuri; Geert Leus

Source-linked AI summary

Sparsity-Promoting Sensor Selection for Non-linear Measurement Models

Sundeep Prabhakar Chepuri, Geert Leus

arXiv:1310.5251v2Oct 19, 2013cs.ITeess.SP

TL;DR

Sensor selection asks which limited measurements to retain while guaranteeing estimation performance in nonlinear statistical inference. The paper uses CRB-based criteria, convex relaxations, and scalable sparse algorithms, illustrating the framework through localization-oriented sensor placement.

Problem
The paper addresses selecting a sensor subset that guarantees estimation accuracy while limiting network hardware, communication, and processing costs.
Method
It formulates selection as a Boolean ℓ0-(quasi) norm optimization problem, relaxes it convexly, and adds projected subgradient and concave-surrogate algorithms.
Results
The framework is applied to nonlinear localization-related sensor-placement models, where the concave surrogate produces a sparser solution than the ℓ1-norm cost in the illustrated scenario.
Takeaways & Limitations
The framework applies to independent observations with regular likelihoods and supports polynomial-time solution and easy distributed implementation for nonlinear statistical inference.

Abstract

from arXiv · show

Sensor selection is an important design problem in large-scale sensor networks. Sensor selection can be interpreted as the problem of selecting the best subset of sensors that guarantees a certain estimation performance. We focus on observations that are related to a general non-linear model. The proposed framework is valid as long as the observations are independent, and its likelihood satisfies the regularity conditions. We use several functions of the Cramér-Rao bound (CRB) as a performance measure. We formulate the sensor selection problem as the design of a selection vector, which in its original form is a nonconvex l0-(quasi) norm optimization problem. We present relaxed sensor selection solvers that can be efficiently solved in polynomial time. We also propose a projected subgradient algorithm that is attractive for large-scale problems and also show how the algorithm can be easily distributed. The proposed framework is illustrated with a number of examples related to sensor placement design for localization.

I. INTRODUCTION

The paper frames sensor selection for nonlinear statistical inference as choosing informative measurements under resource constraints, then develops tractable sparse optimization methods for large networks.

I. INTRODUCTION: Sensor selection chooses informative measurements while reducing hardware, communication, and processing costs under limited resources.
II. NON-LINEAR MEASUREMENT MODEL: The framework targets general nonlinear measurement models whose observations are collected from spatial or temporal sensors.
B. Contributions: The original selection-vector formulation is a nonconvex Boolean ℓ0-(quasi) norm problem, making direct enumeration impractical for large sensor sets.
B. Contributions: Convex relaxations replace the nonconvex formulation with problems that can be solved efficiently in polynomial time.
B. Contributions: A projected subgradient algorithm addresses large-scale instances and supports easy distributed implementation.
B. Contributions: A sparsity-enhancing concave surrogate is proposed for cases with multiple or nearly identical sensor measurements.

III. PROBLEM FORMULATION

The paper seeks a subset of at least N sensors whose measurements guarantee a specified estimation accuracy for the unknown parameter.

III. PROBLEM FORMULATION: The selection objective is to choose the best subset of available sensor measurements while guaranteeing accuracy for the estimate θ̂.

A. Sensor selection

The paper represents sensor inclusion with a selection vector and uses CRB-derived measures to enforce estimation accuracy across a parameter domain. These constraints yield convex formulations, including minimum-eigenvalue LMIs, and can incorporate prior information in Bayesian settings.

The selection vector uses w_m=1 or 0 to include or exclude the mth measurement.
The CRB is used because a nonsingular FIM supports local identifiability, while lower CRB values typically correspond to lower MSE.
Accuracy is specified by requiring the estimation error to lie within radius R_e with probability exceeding P_e.Reducing R_e or increasing P_e raises the required accuracy level.
A-optimality-related and minimum-eigenvalue performance measures provide sufficient conditions for the accuracy requirement.The minimum-eigenvalue condition imposes a lower bound on every eigenvalue of the information matrix F.
Because the FIM depends on the unknown parameter θ, the framework constrains performance throughout the domain U.In Bayesian settings, prior information contributes a prior information matrix J_p to the information matrix.

C. Problem statement

The sensor-selection problem minimizes the number of informative sensors while satisfying a CRB-based performance constraint. Its binary cardinality formulation is nonconvex and NP-hard, motivating convex relaxations and scalable solution methods.

The formal problem selects the minimum number of informative sensors subject to the performance measure for all θ∈U.
Minimizing the ℓ0-(quasi) norm minimizes the number of nonzero selection-vector entries and reduces hardware, storage, processing, and communication overhead.
The threshold λ_eig imposes the accuracy requirement and also acts as a sparsity-inducing parameter, with λ_eig→0 implying a sparser solution.
Gridding U at D points stacks the multiple parameter-dependent LMIs into one block-diagonal LMI.After gridding, the FIM is represented by block-diagonal matrices F_m.
The original binary ℓ0 problem is NP-hard and nonconvex, whereas the ℓ1-relaxed semidefinite program can be solved in polynomial time by interior-point methods.The positivity constraint makes the ℓ1 objective affine in the selection vector.

B. Projected subgradient algorithm

The projected subgradient algorithm replaces computationally expensive Newton iterations with a cheaper first-order method for large-scale relaxed selection problems. It updates feasible and infeasible iterates differently, projects them onto box constraints, and admits a distributed implementation.

The projected subgradient method is proposed because Newton’s method becomes intractable when the sensor count is very large, such as M≫1000.Each first-order iteration is cheaper to process.
The constraint subgradient is obtained from the minimum eigenvalue and its associated eigenvector, computable with the power method or eigenvalue decomposition.
When an iterate is feasible, the algorithm moves along the negative objective subgradient; when infeasible, it moves using a constraint subgradient before projection.
The matrix sum can be computed by distributed averaging, while eigenvalue, update, subgradient, and projection computations are distributed across nodes.
Subgradient methods typically need a few hundred iterations, whereas Newton’s method typically needs about ten but is harder to distribute and more expensive per iteration.

C. Concave surrogate: sparsity-enhancing iterative algorithm

The paper introduces a concave surrogate and iterative weighted ℓ1 optimization to address nonuniqueness and weak sparsity from the standard ℓ1 relaxation. Weight updates suppress small entries while preserving larger ones, followed by randomized Boolean rounding.

The ℓ1 relaxation is not always unique because its objective is not strictly convex and the LMI constraint set is linear.
With identical observations, infinitely many relaxed solutions can occur, and the ℓ1 relaxation typically fails to produce a sparse solution.
A nonconvex surrogate is proposed to improve the ℓ1 solution and obtain fewer selected sensors.
The surrogate uses the logarithm of the geometric mean of the selection-vector elements, with δ>0 preventing the cost from tending to −∞.
Iterative linearization produces weighted ℓ1 problems whose weight updates drive small entries toward zero without inappropriately suppressing larger entries.
The sparsity-enhancing method can use projected subgradient iterations inside each outer weighted-ℓ1 iteration.
Randomized rounding generates Boolean candidates with probabilities based on the relaxed entries and retains candidates satisfying the eigenvalue constraints.

D. Randomized rounding

The paper replaces simple rounding with randomized rounding because nearest-integer estimates are not guaranteed to satisfy the LMI constraint. Random experiments are guided by the SDP solution or its iterative counterpart.

Simple rounding converts each relaxed variable into a Boolean estimate by rounding it toward the nearest integer.
Nearest-integer rounding provides no guarantee that the resulting Boolean estimates satisfy the LMI constraint.
Randomized rounding computes suboptimal Boolean estimates through random experiments guided by the SDP solution or its iterative version.

A. The dual problem

The relaxed sensor-selection formulations include dual, trace, and determinant-based designs for controlling estimation performance. These convex formulations can be solved computationally, although alternative formulations may require substantially more constraints.

The dual problem: The dual formulation is related to the diameter of confidence ellipsoids and to the dual of E-optimal design.With µ_m = 0, its solution maximizes the diameter of the confidence ellipsoid centered around the origin.
The dual problem: The dual problem has only M inequality constraints and can be solved using Yalmip, SeDuMi, or CVX.
Scalar constraints: The trace-constrained relaxed problem is convex and can be cast as a semidefinite program using an LMI representation.
Scalar constraints: A formulation with N LMI constraints for every point in U is computationally more intensive than the formulation with one LMI constraint per point.
Scalar constraints: The determinant constraint is related to D-optimality, while its threshold specifies the mean radius of a confidence ellipsoid.The log-determinant constraint is concave for nonnegative selection variables but is not sufficient for the stated accuracy condition.
Scalar constraints: Relaxed sensor-selection problems with scalar trace or determinant constraints can use either an ℓ1-norm cost or a log-based concave surrogate.

A. Distance measurements

The localization examples instantiate the framework with nonlinear distance, RSS, bearing, and energy measurements. They derive Fisher information contributions for these sensing models and also extend selection to active sensing with resource-allocation weights.

Distance measurements: Distance-based localization uses noisy pairwise ranges between an unknown target and anchors at known grid-point locations.The range model is y_m = d_m + n_m, with d_m = ||θ − a_m||_2.
RSS measurements: RSS measurements model received power as Gaussian in decibels because shadowing is represented by a log-normal process.
Bearing measurements: Bearing measurements provide another localization model using direction-finding sensors and noisy angular observations.
Energy measurements: For energy measurements from a point source, the framework computes the Fisher information matrix contribution associated with each measurement.
Active sensing: In active sensing, w_m is a normalized soft resource parameter, and the relaxed problem retains the form of the passive formulation.Minimizing the ℓ1-norm minimizes overall network resource use.

E. Simulations

Simulations apply the sensor-selection framework to localization under range, bearing, RSS, and other measurement models, comparing sparsity relaxations and optimization methods. The results show sparse selections, distance-based placement patterns, and a practical gap between CRB-based constraints and estimator RMSE.

Simulation setup: M = 80 candidate sensors are used to evaluate localization sensor placement under specified accuracy thresholds.The target area is discretized into a 15 × 15 m2 grid with 1.75 m resolution.
Range measurements: The ℓ1-norm and concave-surrogate relaxations produce feasible selections, with the concave surrogate yielding a sparser solution under minimum eigenvalue constraints.Randomized rounding recovers an approximate Boolean solution for the sparsity-enhancing approach.
Range measurements: Larger Pe increases ∥w∥1 and selects more sensors, while the minimum eigenvalue constraint requires a slightly larger ℓ1-norm than the trace constraint in the considered scenario.The trace constraint has a larger feasible set than the stronger minimum eigenvalue constraint.
Projected subgradient method: The projected subgradient method converges slowly, but its estimated support after a few hundred iterations can be refined using randomized rounding.For 1000 iterations, it takes around 8.84 seconds, compared with around 4.03 seconds for SeDuMi on the same computer.
Estimator performance: The selected-sensor solution path varies with Re, while maximum RMSE can violate the specified accuracy requirement even when maximum and average root-CRB satisfy the constraint.The authors account for the estimator–CRB gap by choosing Re appropriately; in the considered scenario, the average RMSE remains reasonably close to the performance constraint.
Other measurement models: Across range, bearing, RSS, and related measurement models, the FIM decreases with sensor-to-target distance, producing selections close to the target area.The rate of decrease differs across measurement models, while the distance-based selection pattern is common.

APPENDIX A PERFORMANCE THRESHOLDS

The appendix derives sufficient CRB-based performance thresholds from estimation accuracy requirements and relates determinant constraints to confidence-ellipsoid geometry. It then formulates a semidefinite dual problem for the relaxed sensor-selection optimization.

Performance thresholds: Chebyshev’s inequality links the estimation-error accuracy requirement to a sufficient trace constraint on the CRB matrix.The derivation combines an upper bound on Pr(∥ε∥2 ≤ Re) with the required probability Pe.
Performance thresholds: A minimum-eigenvalue constraint provides a stronger sufficient condition than the trace bound, at the cost of a smaller feasible set.The bound follows because each eigenvalue of C^-1 is at least λmin(F), yielding tr{C} ≤ Nλmin^-1(F).
Confidence-ellipsoid criteria: The determinant constraint measures the volume or geometric-mean radius of a confidence ellipsoid containing the estimation error with probability Pe.The ellipsoid’s semi-axis lengths depend on the ordered eigenvalues of F, and its geometric mean provides an informativeness measure related to D-optimality.
Confidence-ellipsoid criteria: The accuracy constant ξ is assumed known and may be chosen from chi-squared quantiles determined by the target confidence probability.This choice connects the confidence-ellipsoid constraint to a specified probability level.
Semidefinite dual formulation: The relaxed optimization is paired with an SDP dual whose variables include Z, μ, and ν under semidefinite, nonnegativity, and trace constraints.Eliminating νm yields a simplified dual formulation.

APPENDIX C PROJECTED NEWTON’S METHOD

The appendix approximates the sensor-selection optimization with a log-determinant barrier and solves the resulting constrained problem using projected Newton updates. Power iterations provide the minimum eigenvalue and corresponding eigenvector needed by the algorithm.

Projected Newton’s method: The projected Newton method is introduced to analyze and solve the semidefinite optimization problem in inequality form.The method is adapted specifically to the problem’s SDP constraints.
Projected Newton’s method: A log-determinant barrier function approximates the original optimization, with t controlling the approximation.The projected Newton update, Hessian, gradient, and line-search step length define the numerical iteration.
Minimum-eigenvalue computation: Power iterations converge to the maximum eigenvalue and eigenvector of a matrix, enabling minimum-eigenvalue computation through a spectral transformation.Applying the iterations to F̄ = λmaxI_N − F makes λmax − λmin dominant and recovers vmin and λmin of F.