The limits of adaptive sensing

      Abstract:
      Suppose we can sequentially acquire arbitrary linear
      measurements of a p-dimensional vector \beta resulting in the
      linear model y = X \beta +z, where z represents measurement
      noise. If the signal is known to be sparse, one would expect the
      following folk theorem to be true: choosing an adaptive strategy
      which cleverly selects the next row of X based on what has been
      previously observed should do far better than a nonadaptive
      strategy which sets the rows of X ahead of time, thus not trying
      to learn anything about the signal in between observations. In
      this talk we will argue that, surprisingly, this folk theorem is
      false. More specifically, we will prove a lower bound on the
      minimax MSE achievable by an arbitrary adaptive
      measurement/estimation procedure. This bound shows that the room
      for improvement of adaptive strategies over classical compressed
      acquisition/recovery schemes is, in general, minimal.