This work describe connections between optimal experiment design (OED) for PDE-based Bayesian linear inverse problems and the column subset selection problem (CSSP) in matrix approximation. We derive bounds, both lower and upper, for the D-optimality criterion via CSSP for the independent and coloured noise cases. Additionally, we describe ways to interpolate “left-out” sensor data using the “selected” sensors along with the errors in the data completion process. We develop and analyse randomised algorithms which achieve these bounds. Finally, we experimentally verify these results on a model advection-diffusion problem.