论文标题
在线性估计中用于子集选择的改进的贪婪算法
An Improved Greedy Algorithm for Subset Selection in Linear Estimation
论文作者
论文摘要
在本文中，我们考虑了在空间领域中的子集选择问题，我们试图找到一组K位置，其观测值在一组有限的预测位置提供了对场值的最佳估计。可以在连续场的任何位置进行测量，并且在不同点处的场值之间的协方差由广泛使用的平方指数协方差函数给出。观察选择的一种方法是对空间进行网格离散化，并使用贪婪算法获得近似解决方案。解决方案质量通过更精细的网格分辨率提高，但以增加计算为代价。我们提出了一种通过考虑仅由预测位置形成的预测位置和质心组成的搜索空间来降低贪婪算法的计算复杂性的方法，或者相反，以提高贪婪算法的解决方案质量。在解决方案质量和运行时，我们证明了我们提出的方法在模拟中的有效性。
In this paper, we consider a subset selection problem in a spatial field where we seek to find a set of k locations whose observations provide the best estimate of the field value at a finite set of prediction locations. The measurements can be taken at any location in the continuous field, and the covariance between the field values at different points is given by the widely used squared exponential covariance function. One approach for observation selection is to perform a grid discretization of the space and obtain an approximate solution using the greedy algorithm. The solution quality improves with a finer grid resolution but at the cost of increased computation. We propose a method to reduce the computational complexity, or conversely to increase solution quality, of the greedy algorithm by considering a search space consisting only of prediction locations and centroids of cliques formed by the prediction locations. We demonstrate the effectiveness of our proposed approach in simulation, both in terms of solution quality and runtime.
