  A novel framework of compressed sensing, namely statistical compressed
sensing (SCS), that aims at efficiently sampling a collection of signals that
follow a statistical distribution, and achieving accurate reconstruction on
average, is introduced. SCS based on Gaussian models is investigated in depth.
For signals that follow a single Gaussian model, with Gaussian or Bernoulli
sensing matrices of O(k) measurements, considerably smaller than the O(k
log(N/k)) required by conventional CS based on sparse models, where N is the
signal dimension, and with an optimal decoder implemented via linear filtering,
significantly faster than the pursuit decoders applied in conventional CS, the
error of SCS is shown tightly upper bounded by a constant times the best k-term
approximation error, with overwhelming probability. The failure probability is
also significantly smaller than that of conventional sparsity-oriented CS.
Stronger yet simpler results further show that for any sensing matrix, the
error of Gaussian SCS is upper bounded by a constant times the best k-term
approximation with probability one, and the bound constant can be efficiently
calculated. For Gaussian mixture models (GMMs), that assume multiple Gaussian
distributions and that each signal follows one of them with an unknown index, a
piecewise linear estimator is introduced to decode SCS. The accuracy of model
selection, at the heart of the piecewise linear decoder, is analyzed in terms
of the properties of the Gaussian distributions and the number of sensing
measurements. A maximum a posteriori expectation-maximization algorithm that
iteratively estimates the Gaussian models parameters, the signals model
selection, and decodes the signals, is presented for GMM-based SCS. In real
image sensing applications, GMM-based SCS is shown to lead to improved results
compared to conventional CS, at a considerably lower computational cost.
