Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/ISIT.2017.8006569 | 2017 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | Volume |
sparsity estimation,simple measurements,nonzero elements,matrix independent,Δ-approximation,group testing,compressed sensing,coding theory,probabilistic methods,upper bound,finite field | Conference | abs/1707.06664 |
ISBN | Citations | PageRank |
978-1-5090-4097-1 | 0 | 0.34 |
References | Authors | |
10 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Abhishek Agarwal | 1 | 8 | 1.53 |
| Larkin Flodin | 2 | 0 | 1.35 |
| Arya Mazumdar | 3 | 307 | 41.81 |