Performance guarantees for adaptive estimation of sparse signals

This paper studies adaptive sensing for estimating the nonzero amplitudes of a sparse signal with the aim of providing analytical guarantees on the performance gain due to adaptive resource allocation. We consider a previously proposed optimal two-stage policy for allocating sensing resources. For positive powers q, we derive tight upper bounds on the mean q th-power error resulting from the optimal two-stage policy and corresponding lower bounds on the improvement over nonadaptive uniform sensing. It is shown that the adaptation gain is related to the detectability of nonzero signal components as characterized by Chernoff coefficients, thus quantifying analytically the dependence on the sparsity level of the signal, the signal-to-noise ratio (SNR), and the sensing resource budget. For fixed sparsity levels and increasing SNR or sensing budget, we obtain the rate of convergence to oracle performance and the rate at which the fraction of resources spent on the first exploratory stage decreases to zero. For a vanishing fraction of nonzero components, the gain increases without bound as a function of SNR and sensing budget. Numerical simulations demonstrate that the bounds on adaptation gain are quite tight in nonasymptotic regimes as well.