Near-Optimal Sensor Placement for Linear Inverse Problems

Abstract

A classic problem is the estimation of a set of parameters from measurements collected by only a few sensors. The number of sensors is often limited by physical or economical constraints and their placement is of fundamental importance to obtain accurate estimates. Unfortunately, the selection of the optimal sensor locations is intrinsically combinatorial and the available approximation algorithms are not guaranteed to generate good solutions in all cases of interest. We propose FrameSense, a greedy algorithm for the selection of optimal sensor locations. The core cost function of the algorithm is the frame potential, a scalar property of matrices that measures the orthogonality of its rows. Notably, FrameSense is the first algorithm that is near-optimal in terms of mean square error, meaning that its solution is always guaranteed to be close to the optimal one. Moreover, we show with an extensive set of numerical experiments that FrameSense achieves state-of-the-art performance while having the lowest computational cost, when compared to other greedy methods.

13 pages, accepted for publication on IEEE TSP

References in corpus (2)

• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Frame completions for optimally robust reconstruction

Cited by in corpus (23)

• Signals on Graphs: Uncertainty Principle and Sampling
• Sampling Signals on Graphs: From Theory to Applications
• Greedy Sampling of Graph Signals
• Sensor placement by maximal projection on minimum eigenspace for linear inverse problems
• Sparse Antenna and Pulse Placement for Colocated MIMO Radar
• Low-complexity Graph Sampling with Noise and Signal Reconstruction via Neumann Series
• Sparse Sampling for Inverse Problems with Tensors
• Sensor scheduling with time, energy and communication constraints
• Approximate Supermodularity of Kalman Filter Sensor Selection
• Nondominated-Solution-based Multi-objective Greedy Sensor Selection for Optimal Design of Experiments
• Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
• Near-Optimal Sparse Sensing for Gaussian Detection with Correlated Observations
• Randomized Group-Greedy Method for Large-Scale Sensor Selection Problems
• Perception Entropy: A Metric for Multiple Sensors Configuration Evaluation and Design
• Recovery of Linear Components: Reduced Complexity Autoencoder Designs
• Fast Data-driven Greedy Sensor Selection for Ridge Regression
• Lazy FSCA for Unsupervised Variable Selection
• DASS: Distributed Adaptive Sparse Sensing
• Thermal Source Localization Through Infinite-Dimensional Compressed Sensing
• Insense: Incoherent Sensor Selection for Sparse Signals
• Consistent Sensor, Relay, and Link Selection in Wireless Sensor Networks
• Fast sensor placement by enlarging principle submatrix for large-scale linear inverse problems
• Observable dictionary learning for high-dimensional statistical inference