Sensor selection is an NP-hard problem involving the selection of S out of N sensors such that optimal (in some predefined sense) filtering performance is attained. We present a novel approach for sensor selection that utilizes a measure quantifying the incoherence of the vector space spanned by the sensors with respect to the system's principal directions. This approach provides a formulation of a convex relaxation problem that can be efficiently modeled and solved using compressed sensing (CS) algorithms. One of the key requirements in the theory of CS is that of a sufficiently incoherent sensing matrix. Such matrices are normally neither encountered in the sensor selection problem nor in many other engineering and scientific problems, which, to some extent, limits the applicability of the theory. In this work, this requirement is alleviated via the concept of semi-random sensing, where the standard sensing matrix pertaining to the problem at hand is deliberately contaminated by noise. We provide relations between the noise intensity and the incoherence properties of the contaminated sensing matrix. The viability of this concept is demonstrated and analyzed in the context of the sensor selection problem. (C) 2013 Elsevier Ltd. All rights reserved.