Sequential algorithms for observation selection (Q2732787)

The paper considers the signal equation \(y= Ax+ u\), where the signal \(y\) is a linear transformation of \(x\) observed in the presence of the additive noise \(u\), and \(A\in\mathbb{C}^{m\times n}\), with \(m\geq n\). The question is to observe the \(k\) of the \(m\) elements of \(y\) that provide the best possible reconstruction of \(x\) using only the information from the matrix \(A\) to make the selection of observations. This is equivalent to the problem of observation selection, which means choosing the rows of \(A\) that correspond to the best observation to acquire.NEWLINENEWLINENEWLINEThe authors present and analyze two classes of sequential algorithms to select observations: sequential backward selection (SBS), and sequential forward selection (SFS). The SBS strategy sequentially eliminates one \(A\) row at a time until \(k\) rows remain. Although the SBS is suboptimal, it eliminates the combinatory problem and proved to perform consistently well in all the examples tested. SBS raises however some questions: (1) Whether a certain level of performance may be guaranteed. (2) Data acquisition cannot begin until all unwanted candidate observations have been eliminated. To overcome these issues, the authors propose the SFS strategy, which sequentially selects rather than eliminates, as in SBS, one row at a time from the candidate matrix. Since the SFS algorithm is committed to retain the selected observation at each step, data acquisition can begin immediately after the first observation is selected, assuming an initial set of observations can be chosen a priori.NEWLINENEWLINENEWLINEThe paper exposes efficient implementations of the SBS and SFS algorithms and analyzes the computational requirements of these implementations. Upper bounds of the sum of squared errors of the solutions obtained by SBS and SFS algorithms are derived. Simulation results are obtained and discussed on four different candidate matrices in order to illustrate the derived algorithms and bounds.