Recovering Jointly Sparse Signals via Joint Basis Pursuit

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 ${\mathrm{\ell }}_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 ${\mathrm{\ell }}_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 $k_1,k_2$ respectively, we show that, for a general class of signals, using this approach, one requires as small as $O(\max \{k_1,k_2\}\log \log n)$ measurements for successful recovery hence overcoming the classical requirement of $\mathrm{\Theta }(\min \{k_1,k_2\}\log (\frac{n}{\min \{k_1,k_2\}}))$ for ${\mathrm{\ell }}_1$ minimization when $k_1\approx k_2$. Extensive simulations show that, our analysis is approximately tight.