Spark-level sparsity and the ℓ1 tail minimization

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 is recoverable by ℓ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 m2m2 in thousands and thousands of random tests. We further show instead that the mere ℓ1-minimization would actually fail if s>m2 even from the same measure theoretical point of view.