SensorSelection.jl

This package implements sequential forward selection and sequential backwards selection algorithms for solving sensor-selection problems in julia.

Introduction

Consider a signal , which is related to a set of measured data via a linear model

with zero-mean Gaussian measurement noise with covariance matrix . Here each row of the measurement matrix is a measurement vector from the set . Moreover, the set contains the indices associated with the measurements performed by . These types of models arise in a large variety of contexts such as imaging or the placement of physical sensors.

The fundamental task at hand is to estimate from the measurements . Sensor selection aims to determine a measurement set containing measurements, such that the uncertainty associated with the estimation of the parameter is minimized. To do so, we look for a set of measurements minimizing a cost function of the form

Here we assume a prior distribution for the parameter . In the special case the matrix expression inside the trace reduces to the estimation theoretic Cramer-Rao bound. If is finite, it corresponds to the covariance matrix (in the Bayesian sense) of the minimum mean squared error estimator.

The sensor selection problem is a non-convex integer programming problem. Thus, one often uses greedy approaches for its solution. Sequential forward selection starts with and iteratively adds the measurements which lead to the largest decrease of the cost function. Conversely, sequential backwards selection starts with and iteratively removes the measurements leading to the smalles increase of the cost function.

This packags provides implementations of the greedy algorithms for the solution of the sensor selection problem described so far.

Installation

Install SensorSelection.jl within julia using

import Pkg
Pkg.add("https://github.com/migrosser/SensorSelection.jl")

Example

Consider the measurement set and a diagonal noise covariance matrix with variances in increasing order. Moreover, let us consider a diagonal prior covariance matrix of the form . For this example, sequential forward selection can be performed using the following code

using SensorSelection, LinearAlgebra, Random

N=128
# measurement matrix
Ht = collect( reshape( (1.0*I(N)),N,N,1 ) )
# prior variances
σx = 0.01*ones(N,1)
# measurement noise variances
σy = reshape( sort(rand(N).+eps()), N, 1)

# build experiment object
exp1 = Experiment(Ht, σy, σx, zeros(Bool, N))

# sequential forward selection
numMeas = rand(1:N) # target number of measurements in the experiment
wlog1 = optSamplingFW!(exp1, numMeas, 1, N)

Here the prior variances and the noise variances are specified in the form of matrices. The second dimension of these matrices can be used to describe multiple sets of variances associated to different "training examples".

Analogously to the above example, the following code performes sequential backwards selection

# same setup as before

# build experiment object
exp2 = Experiment(Ht, σy, σx, ones(Bool, N))

# sequential forward selection
wlog2 = optSamplingBW!(exp2, numMeas, 1, N)