Name
Abstract | ||
|---|---|---|
Solving compressed sensing problems relies on the properties of sparse signals. It is commonly assumed that the sparsity s needs to be less than one half of the spark of the sensing matrix A, and then the unique sparsest solution exists, and recoverable by $\ell_1$-minimization or related procedures. We discover, however, a measure theoretical uniqueness exists for nearly spark-level sparsity from compressed measurements Ax = b. Specifically, suppose A is of full spark with m rows, and suppose $\frac{m}{2}$ < s < m. Then the solution to Ax = b is unique for x with $\|x\|_0 \leq s$ up to a set of measure 0 in every s-sparse plane. This phenomenon is observed and confirmed by an $\ell_1$-tail minimization procedure, which recovers sparse signals uniquely with s > $\frac{m}{2}$ in thousands and thousands of random tests. We further show instead that the mere $\ell_1$-minimization would actually fail if s > $\frac{m}{2}$ even from the same measure theoretical point of view. |
Year | Venue | DocType |
|---|---|---|
2016 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1610.06853 | 0 | 0.34 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chun-Kit Lai | 1 | 0 | 0.68 |
| Shidong Li | 2 | 17 | 5.07 |
| Daniel Mondo | 3 | 0 | 0.34 |