2016/10/20 by Chun‐Kit Lai, Lai, Chun-Kit, Shidong Li +3 · 1 citation
Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #Ultrasonics and Acoustic Wave Propagation
paper · pdf · doi:10.48550/arxiv.1610.06853
openalex publication_date 2016/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℓ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 (m)/(2) < s < m. Then the solution to Ax = b is unique for x with ‖x‖0 ≤ s up to a set of measure 0 in every s-sparse plane. This phenomenon is observed and confirmed by an ℓ1-tail minimization procedure, which recovers sparse signals uniquely with s > (m)/(2) in thousands and thousands of random tests. We further show instead that the mere ℓ1-minimization would actually fail if s > (m)/(2) even from the same measure theoretical point of view.