Estimation of sparsity via simple measurements

We consider several related problems of estimating the `sparsity' or number of nonzero elements d in a length n vector x by observing only b = M ⊙ x, where M is a predesigned test matrix independent of x, and the operation ⊙ varies between problems. We aim to provide a Δ-approximation of sparsity for some constant Δ 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 ⊙ 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 ⊙ is multiplication over R or a finite field, we show that respectively Θ(D) and Θ(D log n/D) measurements are necessary and sufficient.