How to sample if you must: on optimal functional sampling
This work addresses a fundamental problem in active sampling, such as network tomography, but is incremental as it builds on existing optimal design theory.
The paper tackles the problem of optimally selecting linear functionals to sample from a multivariate normal distribution to minimize estimation error, addressing a gap in optimal design for cases with many functionals. It presents bounds and an efficient sub-optimal solution for structured sets like binary functionals from graph walks.
We examine a fundamental problem that models various active sampling setups, such as network tomography. We analyze sampling of a multivariate normal distribution with an unknown expectation that needs to be estimated: in our setup it is possible to sample the distribution from a given set of linear functionals, and the difficulty addressed is how to optimally select the combinations to achieve low estimation error. Although this problem is in the heart of the field of optimal design, no efficient solutions for the case with many functionals exist. We present some bounds and an efficient sub-optimal solution for this problem for more structured sets such as binary functionals that are induced by graph walks.