  This paper tackles optimal sensor placement for Bayesian linear inverse
problems, a popular version of the more general Optimal Experiment Design (OED)
problem, using the D-optimality criterion. This is done by establishing
connections between sensor placement and Column Subset Selection Problem
(CSSP), which is a well-studied problem in Numerical Linear Algebra (NLA). In
particular, we use the Golub-Klema-Stewart (GKS) approach which involves
computing the truncated Singular Value Decomposition (SVD) followed by a
pivoted QR factorization on the right singular vectors. The algorithms are
further accelerated by using randomization to compute the low-rank
approximation as well as for sampling the indices. The resulting algorithms are
robust, computationally efficient, amenable to parallelization, require
virtually no parameter tuning, and come with strong theoretical guarantees. One
of the proposed algorithms is also adjoint-free which is beneficial in
situations, where the adjoint is expensive to evaluate or is not available.
Additionally, we develop a method for data completion without solving the
inverse problem. Numerical experiments on model inverse problems involving the
heat equation and seismic tomography in two spatial dimensions demonstrate the
performance of our approaches.
