Piecewise Sparse Recovery in Union of Bases

Abstract:

      Sparse recovery (or sparse representation) is a widely studied issue in the fields of signal processing, image processing, computer vision, machine learning and so on, since signals such as videos and images, can be sparsely represented under some frames. Most of fast algorithms at present are based on solving $l^0$ or $l^1$ minimization problems and they are efficient in sparse recovery. However, the theoretically sufficient conditions on the sparsity of the signal for $l^0$ or $l^1$ minimization problems and algorithms are too strict. In some applications, there are signals with structures, i.e., the nonzero entries have some certain distribution. In this paper, we consider the uniqueness and feasible conditions for piecewise sparse recovery. Piecewise sparsity means that the sparse signal $\mathbf{x}$ is a union of several sparse sub-signals $\mathbf{x}_i\ (i=1,2,\ldots,N)$, i.e., $\mathbf{x}=(\mathbf{x}^{\rm T}_1,\mathbf{x}^{\rm T}_2,\ldots,\mathbf{x}_N^{\rm T})^{\rm T}$, corresponding to the measurement matrix $A$ which is composed of union of bases $A=[A_1,A_2,\ldots,A_N]$. We introduce the mutual coherence for the sub-matrices $A_i\ (i=1,2,\ldots,N)$ by considering the block structure of $A$ corresponding to piecewise sparse signal $\mathbf{x}$, to study the new upper bounds of $\|\mathbf{x}\|_0$ (number of nonzero entries of signal) recovered by both $l^0$ and $l^1$ optimizations. The structured information of measurement matrix $A$ is exploited to improve the sufficient conditions for successfully piecewise sparse recovery and also improve the reliability of $l_0$ and $l_1$ optimization models on recovering global sparse vectors.