Sensor Selection for Estimation with Correlated Measurement Noise

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.Source: §I · p. 1
• 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.Source: §I · p. 1

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.Source: §I · p. 2
• Prior correlated-noise formulations are shown to be valid only in the weak-correlation regime.Their approximate metrics can otherwise produce incorrect sensor selections.Source: §I · p. 2
• 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.Source: §I · p. 2

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.Source: A. Minimum mean-squared estimation error · p. 3
• 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.Source: A. Minimum mean-squared estimation error · p. 3

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.Source: A. Minimum mean-squared estimation error · p. 3
• 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.Source: B. Fisher information Jw as an… · p. 3

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.Source: C. Formulation of the optimal sensor… · p. 3

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.Source: C. Formulation of the optimal sensor… · p. 3, D. Formulation for two special cases · pp. 3–4
• 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.Source: D. Formulation for two special cases · p. 4

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.Source: §III · p. 4, A. Convex relaxation · pp. 4–5
• 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.Source: A. Convex relaxation · p. 4
• 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.Source: A. Convex relaxation · p. 5
• 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.Source: A. Convex relaxation · pp. 4–5

• 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.Source: B. Greedy algorithm · p. 5
• 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.Source: B. Greedy algorithm · p. 5
• 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.Source: B. Greedy algorithm · p. 6
• 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).Source: B. Greedy algorithm · p. 6
• Numerical experiments show that the greedy algorithm produces good locally optimal sensor-selection schemes.Source: B. Greedy algorithm · p. 6

• 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.Source: §IV · p. 6

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.Source: A. Drawbacks of existing formulation · p. 6
• 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.Source: A. Drawbacks of existing formulation · p. 6
• Spreading unselected-sensor noise across selected sensors makes an inactive sensor produce y_i = v_i, contradicting the requirement that inactive sensors remain silent.Source: A. Drawbacks of existing formulation · p. 6
• These discrepancies make the existing formulation inaccurate for correlated-noise sensor selection, motivating a condition for when it becomes valid.Source: A. Drawbacks of existing formulation · p. 6
• The prior formulation incorrectly inverts the full covariance matrix before truncation; active-sensor modeling requires truncating R first and then inverting it.Source: A. Drawbacks of existing formulation · p. 6

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.Source: B. Validity of existing formulation:… · p. 6
• 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.Source: B. Validity of existing formulation:… · p. 6
• 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.Source: B. Validity of existing formulation:… · p. 7

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.Source: C. Sensor selection by maximizing… · p. 7
• 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.Source: C. Sensor selection by maximizing… · p. 7
• 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.Source: C. Sensor selection by maximizing… · p. 7

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.Source: §V · p. 8
• 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.Source: §V · pp. 7–8
• 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.Source: §V · pp. 8–9

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.Source: §VI · p. 9, Sensor selection for parameter… · p. 9

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.Source: Sensor selection for parameter… · p. 9
• 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.Source: Sensor selection for parameter… · p. 9

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 Σ.Source: Sensor selection for parameter… · pp. 9–10
• 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.Source: Sensor selection for parameter… · pp. 9–10

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.Source: Sensor selection for parameter… · p. 10

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.Source: Sensor scheduling for state tracking · p. 10
• The measurement-noise covariance uses the specified correlated model with correlation parameter ρ = 0.035.Source: Sensor scheduling for state tracking · p. 10
• 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.Source: Sensor scheduling for state tracking · pp. 10–11

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.Source: Figure 4 · p. 10, Sensor scheduling for state tracking · p. 11
• 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.Source: Sensor scheduling for state tracking · p. 11, Figure 5 · p. 11

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

• 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.Source: Appendix A · p. 11
• The matrix inversion lemma converts the Fisher-information update into an expression for the resulting improvement in estimation error.Source: Appendix A · pp. 11–12
• 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.Source: Appendix B · p. 12
• The weak-correlation derivation further uses diagonal selection matrices and the first-order approximation R^−1 = Λ^−1 − ϵΛ^−1ΥΛ^−1 + O(ϵ^2).Source: Appendix B · p. 12

• The objective is simplified into a quadratic form involving the matrix Ω.The construction uses the entries h_ij of Ω and a Kronecker-product representation.Source: Appendix C · p. 12
• The matrix Ω is positive semidefinite because it is derived from R^−1 ⊗ I_n.Source: Appendix C · p. 12
• The resulting optimization is subject to a cardinality constraint 1^T w ≤ s and binary sensor variables w ∈ {0, 1}^m.Source: Appendix C · p. 12
• 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.Source: Appendix C · p. 12