Compressed Data Separation via ℓ_q-Split Analysis with ℓ_∞-Constraint

In this paper, we study compressed data separation (CDS) problem, i.e., sparse data separation from a few linear random measurements. We propose the nonconvex ℓ_q-split analysis with ℓ_∞-constraint and 0 < q ≤ 1. We call the algorithm ℓ_q-split-analysis Dantzig selector (ℓ_q-split-analysis DS). We show that the two distinct subcomponents that are approximately sparse in terms of two different dictionaries could be stably approximated via the ℓ_q-split-analysis DS, provided that the measurement matrix satisfies either a classical D-RIP (Restricted Isometry Property with respect to Dictionaries and ℓ₂ norm) or a relatively new (D, q)-RIP (RIP with respect to Dictionaries and ℓ_q-quasi norm) condition and the two different dictionaries satisfy a mutual coherence condition between them. For the Gaussian random measurements, the measurement number needed for the (D, q)-RIP condition is far less than those needed for the D-RIP condition and the (D, 1)-RIP condition when q is small enough.