The sensor selection problem arises in many applications ranging from sensor networks for event detection to determining concentrations of bio-markers for disease detection. In this paper, we assume that in addition to noise, there exist interference signals (which can be correlated with the desired signals) corrupting the measurements. We consider two different criteria to measure the performance of the selected sensors; average error and minimax analysis. For each case, the cost function is defined over the reconstruction algorithm (or matrix in the linear case), which in turn, explicitly determines the selected sensors. Therefore, minimizing the cost function with some sparsity constraints on the reconstruction algorithm results in the best subset of sensors and as to how we recover the desired signals from the selected measurements. In this paper, we consider the problem for the linear measurement system in various settings and derive the optimization problems. Finally, we propose various methods to solve these problems, and show the effectiveness of the proposed algorithms through simulations.