  Oversampled adaptive sensing (OAS) is a recently proposed Bayesian framework
which sequentially adapts the sensing basis. In OAS, estimation quality is, in
each step, measured by conditional mean squared errors (MSEs), and the basis
for the next sensing step is adapted accordingly. For given average sensing
time, OAS reduces the MSE compared to non-adaptive schemes, when the signal is
sparse. This paper studies the asymptotic performance of Bayesian OAS, for
unitarily invariant random projections. For sparse signals, it is shown that
OAS with Bayesian recovery and hard adaptation significantly outperforms the
minimum MSE bound for non-adaptive sensing. To address implementational
aspects, two computationally tractable algorithms are proposed, and their
performances are compared against the state-of-the-art non-adaptive algorithms
via numerical simulations. Investigations depict that these low-complexity OAS
algorithms, despite their suboptimality, outperform well-known non-adaptive
schemes for sparse recovery, such as LASSO, with rather small oversampling
factors. This gain grows, as the compression rate increases.
