  We consider several related problems of estimating the 'sparsity' or number
of nonzero elements $d$ in a length $n$ vector $\mathbf{x}$ by observing only
$\mathbf{b} = M \odot \mathbf{x}$, where $M$ is a predesigned test matrix
independent of $\mathbf{x}$, and the operation $\odot$ varies between problems.
We aim to provide a $\Delta$-approximation of sparsity for some constant
$\Delta$ with a minimal number of measurements (rows of $M$). This framework
generalizes multiple problems, such as estimation of sparsity in group testing
and compressed sensing. We use techniques from coding theory as well as
probabilistic methods to show that $O(D \log D \log n)$ rows are sufficient
when the operation $\odot$ is logical OR (i.e., group testing), and nearly this
many are necessary, where $D$ is a known upper bound on $d$. When instead the
operation $\odot$ is multiplication over $\mathbb{R}$ or a finite field
$\mathbb{F}_q$, we show that respectively $\Theta(D)$ and $\Theta(D \log_q
\frac{n}{D})$ measurements are necessary and sufficient.
