PaperlayerView exact revision on arXiv

Source-linked AI summary

Sensor Selection for Estimation with Correlated Measurement Noise

Sijia Liu, Sundeep Prabhakar Chepuri, Makan Fardad, Engin Masazade, Geert Leus, Pramod K. Varshney

arXiv:1508.03690v2stat.AP

TL;DR

The paper addresses sensor selection and scheduling for parameter estimation when measurement noise is correlated, a setting where existing information-based formulations are limited. It derives a Fisher-information expression valid for arbitrary correlation, develops convex-relaxation and greedy methods, and extends them to non-myopic scheduling. Numerical results illustrate improved estimation performance and the effect of correlation on sensor selection.

  • Problem

    Correlated measurement noise makes Fisher information nonadditive, limiting existing sensor selection and scheduling formulations based on uncorrelated or weakly correlated noise.

  • Method

    The paper derives a closed-form Fisher information expression for arbitrary noise correlation, then uses convex relaxation, randomization, and greedy optimization for selection and non-myopic scheduling.

  • Results

    The proposed approach yields more accurate sensor selection than prior approximate formulations and better state-tracking estimation performance than.

  • Takeaways & Limitations

    Noise correlation materially affects estimation performance, while the proposed framework supports sensor activations across space and multiple time steps.

Abstract

from arXiv · show

In this paper, we consider the problem of sensor selection for parameter estimation with correlated measurement noise. We seek optimal sensor activations by formulating an optimization problem, in which the estimation error, given by the trace of the inverse of the Bayesian Fisher information matrix, is minimized subject to energy constraints. Fisher information has been widely used as an effective sensor selection criterion. However, existing information-based sensor selection methods are limited to the case of uncorrelated noise or weakly correlated noise due to the use of approximate metrics. By contrast, here we derive the closed form of the Fisher information matrix with respect to sensor selection variables that is valid for any arbitrary noise correlation regime, and develop both a convex relaxation approach and a greedy algorithm to find near-optimal solutions. We further extend our framework of sensor selection to solve the problem of sensor scheduling, where a greedy algorithm is proposed to determine non-myopic (multi-time step ahead) sensor schedules. Lastly, numerical results are provided to illustrate the effectiveness of our approach, and to reveal the effect of noise correlation on estimation performance.

I. INTRODUCTION

Sensor selection and scheduling balance estimation accuracy against limited communication and energy resources, with correlated noise making existing additive-information formulations inadequate. The paper develops a general framework for correlated measurements, optimization algorithms, and non-myopic scheduling.

  • Motivation: Limited bandwidth and battery life motivate selecting or scheduling only some sensor activations while preserving estimation accuracy.The framework targets parameter estimation from spatially distributed sensors.
  • Motivation: Existing sensor selection methods largely assume uncorrelated noise, which makes Fisher information additive and optimization tractable.Correlated environmental measurements violate the conditional-independence assumption underlying these methods.
  • Contributions: The paper derives a closed-form estimation-error expression valid for arbitrary noise correlation and optimizes it using convex relaxation and greedy algorithms.The resulting framework avoids the approximation that treats noise covariance as independent of sensor selection.
  • Contributions: Prior correlated-noise formulations are shown to be valid only in the weak-correlation regime.Their approximate metrics can otherwise produce incorrect sensor selections.
  • Contributions: The framework extends to non-myopic sensor scheduling with multi-step horizons and individual energy constraints.Scheduling uses a greedy approach because Fisher information matrices at consecutive time steps are coupled.

A. Minimum mean-squared estimation error

The paper uses Bayesian MMSE estimation to connect sensor activation choices with estimation error and Bayesian Fisher information. It rewrites the information matrix explicitly in the selection vector despite correlated measurement noise.

  • Minimum mean-squared estimation error: Bayesian MMSE estimation remains well defined even when fewer selected sensors than parameter dimensions make the system underdetermined.The prior covariance supplies the Bayesian regularization needed for the error covariance matrix.
  • Minimum mean-squared estimation error: The MMSE error covariance is the inverse of the Bayesian Fisher information matrix under the Gaussian linear model.The paper therefore works with Fisher information as the optimization representation.
  • Fisher information representation: The selection vector affects Fisher information through the active-sensor matrix, making direct optimization with respect to activations difficult.The paper replaces this implicit dependence by an explicit function of the selection vector.
  • Fisher information representation: A decomposition R = aI + S and matrix-inversion identities isolate the dependence of Fisher information on sensor selections.The scalar a and positive-definite matrix S can be chosen arbitrarily without affecting later algorithm performance.

C. Formulation of the optimal sensor selection problem

The optimal selection problem minimizes trace-based estimation error under a sensor-activation budget, with special formulations for diagonal or weakly correlated noise. For the general case, the paper uses convex relaxations and randomized or greedy optimization methods.

  • C. Formulation of the optimal sensor selection problem: The main problem minimizes estimation error subject to at most s active sensors, where Boolean variables make the formulation nonconvex.The budget s is bounded by the total number of sensors m.
  • D. Formulation for two special cases: For diagonal noise covariance, each sensor contributes additively to Fisher information, enabling convex optimization over selection variables.This is the uncorrelated-noise special case.
  • D. Formulation for two special cases: The weak-correlation formulation uses an approximate Fisher information expression and becomes tractable through convexity in wwT.Its validity is restricted to small off-diagonal entries in the noise covariance.
  • General-case optimization: The general solution strategy combines convex relaxation with randomized rounding and a greedy algorithm for sensor activation.The Boolean problem can be relaxed to an SDP, then converted into a near-optimal Boolean selection.
  • General-case optimization: The convex-relaxation formulation is represented using auxiliary matrix inequalities whose positive-semidefinite constraints encode the inverse-information objective.The Schur-complement reformulation preserves the estimation-error minimization structure.
  • General-case optimization: Semidefinite relaxation introduces an auxiliary matrix W and replaces the rank-one constraint with W ⪰ wwT.Schur complements express the resulting constraints as linear matrix inequalities.
  • General-case optimization: The SDP is solved by an interior-point method, with approximate complexity O(m^4.5), followed by randomization to obtain a near-optimal scheme.A simpler continuous relaxation can instead select the largest entries or use randomized rounding.

B. Greedy algorithm

The greedy algorithm activates sensors iteratively, choosing at each step the inactive sensor that maximizes estimation improvement under correlated noise. Activating a sensor increases Fisher information through a rank-one gain, enabling efficient updates and locally optimal selections.

  • Activating an inactive sensor increases the Fisher information matrix, with the increment represented by a positive rank-one matrix.The gain depends on the newly activated sensor's covariance with active sensors and its measurement row.
  • The greedy method selects the inactive sensor yielding the largest estimation-performance improvement at each iteration until the energy constraint is met.The objective improvement is measured through tr(J^-1) after the candidate activation.
  • Algorithm 3 initializes all sensors as inactive, evaluates candidate activations, updates the selection vector and Fisher information, and repeats for s iterations.Each iteration removes the selected sensor from the inactive set.
  • The greedy algorithm searches O(m) candidates per iteration and has overall complexity O(sm + sn^2.373).When the state dimension is much smaller than the number of sensors, the complexity reduces to O(sm).
  • Numerical experiments show that the greedy algorithm produces good locally optimal sensor-selection schemes.

IV. SPECIAL CASE: SENSOR SELECTION WITH WEAK NOISE CORRELATION

The existing correlated-noise formulation is valid only in the weak-correlation regime, where its approximation agrees with the correct Fisher information to first order.

  • The existing model is valid only when measurement noise is weakly correlated, and then the proposed optimization simplifies to a special case.Using trace of the Fisher information as the criterion yields a convex-quadratic maximization problem over a bounded polyhedron.

A. Drawbacks of existing formulation

The section identifies why prior correlated-noise sensor-selection formulations are inaccurate for arbitrary covariance matrices and establishes their restricted validity under weak correlation. It contrasts the incorrect covariance treatment with the paper's formulation and presents an SDP-based relaxation for the weak-correlation case.

  • A. Drawbacks of existing formulation: Prior formulations approximate the information matrix for correlated-noise sensor selection, rather than using the exact selection-dependent covariance treatment.
  • A. Drawbacks of existing formulation: The prior model keeps its noise covariance independent of sensor selection, unlike the paper's formulation.This difference changes how active-sensor measurements are modeled.
  • A. Drawbacks of existing formulation: Spreading unselected-sensor noise across selected sensors makes an inactive sensor produce y_i = v_i, contradicting the requirement that inactive sensors remain silent.
  • A. Drawbacks of existing formulation: These discrepancies make the existing formulation inaccurate for correlated-noise sensor selection, motivating a condition for when it becomes valid.
  • A. Drawbacks of existing formulation: The prior formulation incorrectly inverts the full covariance matrix before truncation; active-sensor modeling requires truncating R first and then inverting it.
  • B. Validity of existing formulation: weak correlation: Weak correlation is modeled with R = Λ + ϵΥ, where Λ contains diagonal entries and ϵ controls the off-diagonal correlation strength.The off-diagonal terms vanish as ϵ approaches zero.
  • B. Validity of existing formulation: weak correlation: Under weak correlation, the correct Fisher information and the prior expression agree up to first order in ϵ as ϵ approaches zero.Consequently, the simplified problem is valid only in this weak-correlation regime.
  • B. Validity of existing formulation: weak correlation: The weak-correlation formulation is relaxed to an SDP with an auxiliary variable Z, and randomization constructs a near-optimal sensor-selection scheme.Its computational complexity is close to that of the paper's SDP, while trace-based objectives can permit cheaper algorithms.

C. Sensor selection by maximizing trace of Fisher information

Maximizing the trace of Fisher information yields a tractable surrogate for sensor selection, while non-myopic scheduling requires a greedy approach because recursive information matrices are coupled across time.

  • Sensor selection: The trace of Fisher information is used as a lower-bound surrogate for minimizing estimation error under a sensor-activation budget.The resulting binary problem constrains the number of selected sensors by 1T w ≤ s.
  • Sensor selection: The surrogate may not minimize MMSE optimally, but its linear trace objective offers computational benefits.The Boolean formulation is nonconvex even after relaxation, motivating structural analysis and local optimization methods.
  • Sensor selection: The equivalent formulation maximizes a convex quadratic function over a bounded polyhedron, an NP-hard problem addressed with bilinear programming and semidefinite relaxation.Bilinear programming scales favorably but may find only local optima, whereas homogeneous QCQP structure permits a smaller SDP.
  • Non-myopic sensor scheduling: Because consecutive Fisher information matrices are coupled, their closed form is intractable and the scheduling problem is solved greedily.The algorithm activates one sensor at a time until the energy constraints are tight, generalizing the selection procedure to time horizons and per-sensor limits.
  • Non-myopic sensor scheduling: Non-myopic scheduling minimizes recursive estimation objectives over multiple time steps subject to cumulative and individual energy constraints.The individual constraint allows sensor i to report at most s_i measurements over τ time steps.
  • Non-myopic sensor scheduling: The scheduling greedy algorithm evaluates objectives in O(τm) operations and computes Fisher information with complexity O(τm^2.373).Relative to a referenced quadratic-programming approach, its complexity increases by m^0.873 in network size but decreases by τ^3 in horizon length.

VI. NUMERICAL RESULTS

Numerical experiments compare greedy, SDR, exhaustive-search, and Fisher-information-based selection methods under different correlation regimes. Randomized SDR performs best in the reported weak-correlation setting, while correlation changes the relative value of selected sensors and prior information.

  • Experimental setup: The experiments use randomly deployed sensors, linear MMSE estimation for parameters, extended Kalman filtering for state tracking, and empirical MSE averaged over 1000 trials.Parameter experiments use m ∈ {20, 50} sensors and estimate n = 2 parameters on a 50 × 50 lattice.
  • Sensor selection with correlated noise: For ρ = 0.1, randomized SDR outperforms the greedy algorithm and achieves the globally optimal solutions in the small-network comparison.Randomization also substantially improves SDR relative to the nonrandomized version.
  • Sensor selection with correlated noise: When the energy budget reaches s ≥ 20, MSE stops decreasing significantly, indicating that a sensor subset can provide satisfactory estimation performance.The passage attributes this saturation to information redundancy from correlated observations.
  • Weakly correlated noise: Under weak correlation ρ = 0.5, maximizing trace of Fisher information produces worse estimation performance than minimizing the trace of error covariance.The Fisher-information objective ignores prior information Σ.
  • Weakly correlated noise: Bilinear programming has the lowest computational complexity among the compared approaches but yields the worst optimization performance.The comparison includes randomized SDR for both the error-based and Fisher-information-based formulations.
  • Effect of correlation strength: In weak correlation regimes, the two SDR-based formulations have the same estimation performance, whereas in strong correlation regimes, the error-based formulation can perform differently.For fixed correlation, estimation error decreases with energy budget and the gap between the formulations narrows.

Sensor scheduling for state tracking

The tracking experiment evaluates sensor scheduling under a correlated-noise model using energy-constrained schedules and empirical MSE. The proposed greedy method outperforms the comparison method, while selected sensors balance proximity to the target with spatial diversity.

  • Experimental setup: The experiment tracks a four-dimensional target with 30 sensors over 30 time steps under a white-noise acceleration model.The state contains target location and velocity components.
  • Experimental setup: The measurement-noise covariance uses the specified correlated model with correlation parameter ρ = 0.035.
  • Experimental setup: Schedules are recomputed for τ = 6 future time steps, and an extended Kalman filter updates the target estimate from selected measurements.Performance is measured by empirical MSE averaged over 30 time steps and 1000 simulation trials.
  • Results: The proposed greedy algorithm yields lower MSE than the method in as individual energy budget varies.Figure 4 reports MSE against the individual energy budget.
  • Results: Selected sensors include some near the target but remain spatially distributed because neighboring observations can be strongly correlated and redundant.Schedules at t = 10 and t = 24 are shown in Figure 5.

VII. CONCLUSION

The paper presents a tractable framework for sensor selection and non-myopic scheduling with correlated measurement noise. It combines general sensor-activation design with a greedy scheduling method and reports numerical evidence concerning estimation performance and noise correlation.

  • The framework designs sensor activations for sensor selection and scheduling when measurement noise is correlated.
  • The paper identifies that existing correlated-noise formulations are valid only for the special case of weak noise correlation.
  • A greedy algorithm is developed for non-myopic sensor scheduling, and numerical results illustrate estimation performance and the impact of noise correlation.
  • Future work includes applications, theoretical performance guarantees for the greedy algorithm, and decentralized optimization to reduce fusion-center computation.

APPENDIX A PROOF OF PROPOSITION 1

The appendix derives the estimation-error improvement from activating a sensor under correlated noise. It uses Fisher-information updates, matrix inversion, and a weak-correlation expansion to simplify the objective.

  • Activating a previously inactive sensor increases the Fisher information matrix by a positive semidefinite amount.The proof establishes this through equations (47) and (48), using c_j > 0.
  • The matrix inversion lemma converts the Fisher-information update into an expression for the resulting improvement in estimation error.
  • Under weak noise correlation, the proof simplifies the Fisher information using a Taylor expansion of (I + ϵX)^−1.The expansion is taken as ϵ approaches zero under a spectral condition.
  • The weak-correlation derivation further uses diagonal selection matrices and the first-order approximation R^−1 = Λ^−1 − ϵΛ^−1ΥΛ^−1 + O(ϵ^2).

APPENDIX C PROOF OF PROPOSITION 3

This appendix rewrites the relaxed sensor-selection objective as a quadratic optimization problem. It then shows that the relaxation has binary optimal solutions under the stated cardinality constraint.

  • The objective is simplified into a quadratic form involving the matrix Ω.The construction uses the entries h_ij of Ω and a Kronecker-product representation.
  • The matrix Ω is positive semidefinite because it is derived from R^−1 ⊗ I_n.
  • The resulting optimization is subject to a cardinality constraint 1^T w ≤ s and binary sensor variables w ∈ {0, 1}^m.
  • The relaxation maximizes a convex quadratic function over a bounded polyhedron whose vertices are zero-one vectors, making relaxed optima feasible for the binary problem.
Loading 1508.03690v2…