Global and Fast Refinement of Greedy Sensor Selection Algorithms for Linear Models

This letter focuses on greedy approaches to select the most informative <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> sensors from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$N$</tex-math></inline-formula> candidates to form a measurement submatrix that minimizes the estimation error. It is a submatrix selection problem. We refine conventional greedy sensor selection algorithms based on the square maximum-volume (SMV) submatrices finding method, particularly at their <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula>th step, with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> being the problem dimension. Our main idea is to increase the volume of the square measurement submatrix associated with the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> sensors by iteratively swapping the selected and unselected sensors based on the dominant property of the maximum-volume submatrix. This simple refinement method ensures a square measurement matrix with increased volume, facilitating the subsequent greedy steps. It can be easily applied to existing greedy algorithms for performance improvement without increasing their complexity order. Numerical results demonstrate the effectiveness of the proposed refinement method in improving several popular greedy algorithms.