2012/02/16 by Samet Oymak, Babak Hassibi, Oymak, Samet +1 · 1 citation
Computer Science · Engineering · Mathematics · Medicine · #Advanced MRI Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques #cs.IT #math.IT #math.OC
paper · pdf · doi:10.48550/arxiv.1202.3531
8 pages, 1 figure, submitted to ISIT 2012
arxiv created 2012/02/16 · openalex publication_date 2012/02/16 · arxiv updated 2012/02/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work considers recovery of signals that are sparse over two bases. For instance, a signal might be sparse in both time and frequency, or a matrix can be low rank and sparse simultaneously. To facilitate recovery, we consider minimizing the sum of the ℓ1-norms that correspond to each basis, which is a tractable convex approach. We find novel optimality conditions which indicates a gain over traditional approaches where ℓ1 minimization is done over only one basis. Next, we analyze these optimality conditions for the particular case of time-frequency bases. Denoting sparsity in the first and second bases by k1,k2 respectively, we show that, for a general class of signals, using this approach, one requires as small as O(max\k1,k2\loglog n) measurements for successful recovery hence overcoming the classical requirement of Θ(min\k1,k2\log(\fracnmin\k1,k2\)) for ℓ1 minimization when k1≈ k2. Extensive simulations show that, our analysis is approximately tight.