Piecewise Sparse Recovery in Union of Bases
Received:September 05, 2022  Revised:January 08, 2023
Key Words: piecewise sparse recovery   union of bases   mutual coherence   greedy algorithm   BP method
Fund Project:Supported by the National Natural Science Foundation of China (Grant Nos.11871137; 11572081) and the Fundamental Research Funds for the Central Universities of China (Grant No.QYWKC2018007).
 Author Name Affiliation Chongjun LI School of Mathematical Sciences, Dalian University of Technology, Liaoning 116024, P. R. China Yijun ZHONG School of Mathematical Sciences, Dalian University of Technology, Liaoning 116024, P. R. China
Hits: 54
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.