Greedy Sensor Selection: Leveraging Submodularity Based on Volume Ratio of Information Ellipsoid

This article focuses on greedy approaches to select the most informative k sensors from N candidates to maximize the Fisher information, i.e., the determinant of the Fisher information matrix (FIM), which indicates the volume of the information ellipsoid (VIE) constructed by the FIM. However, it is a critical issue for conventional greedy approaches to quantify the Fisher information properly when the FIM of the selected subset is rank-deficient in the first (n - 1) steps, where n is the problem dimension. In this work, we propose a new metric, i.e., the Fisher information intensity (FII), to quantify the Fisher information contained in the subset S with respect to that in the ground set N specifically in the subspace spanned by the vectors associated with S. Based on the FII, we propose to optimize the ratio between VIEs corresponding to S and N. This volume ratio is composed of a nonzero (i.e., the FII) and a zero part. Moreover, the volume ratio can be easily calculated based on a change of basis. A cost function is developed based on the volume ratio and proven monotone submodular. A greedy algorithm and its fast version are proposed accordingly to guarantee a near-optimal solution with a complexity of O(Nkn(3)) and O(Nkn(2)), respectively. Numerical results demonstrate the superiority of the proposed algorithms under various measurement settings.

Automated summary

This article proposes greedy approaches to select informative sensors to maximize the Fisher information, and introduces a new metric called the Fisher information intensity (FII). The volume ratio between the information ellipsoid corresponding to the selected subset and the ground set is optimized. A cost function based on the volume ratio is developed and proven to be monotone submodular. A greedy algorithm and its fast version are proposed to obtain near-optimal solutions. Numerical results demonstrate the superiority of the proposed algorithms.