  We introduce the concept of average best $m$-term approximation widths with
respect to a probability measure on the unit ball of $\ell_p^n$. We estimate
these quantities for the embedding $id:\ell_p^n\to\ell_q^n$ with $0<p\le q\le
\infty$ for the normalized cone and surface measure. Furthermore, we consider
certain tensor product weights and show that a typical vector with respect to
such a measure exhibits a strong compressible (i.e. nearly sparse) structure.
