基于基底合并的分片稀疏恢复

Piecewise Sparse Recovery in Union of Bases

中文关键词:  分片稀疏恢复  基底合并  互相干  贪婪算法  BP算法

英文关键词:piecewise sparse recovery  union of bases  mutual coherence  greedy algorithm  BP method

中文摘要:

      如我们所知,诸如视频和图像等信号可以在某些框架下被表示为稀疏信号,因此稀疏恢复(或稀疏表示)是信号处理、图像处理、计算机视觉、机器学习等领域中被广泛研究的问题之一.通常大多数在稀疏恢复中的有效快速算法都是基于求解$l^0$或者$l^1$优化问题.但是,对于求解$l^0$或者$l^1$优化问题以及相关算法所得到的理论充分性条件对信号的稀疏性要求过严.考虑到在很多实际应用中,信号是具有一定结构的,也即,信号的非零元素具有一定的分布特点.在本文中,我们研究分片稀疏恢复的唯一性条件和可行性条件.分片稀疏性是指一个稀疏信号由多个稀疏的子信号合并所得.相应的采样矩阵是由多个基底合并组成.考虑到采样矩阵的分块结构,我们引入了子矩阵的互相干性,由此可以得到相应$l^0$或者$l^1$优化问题可精确恢复解的稀疏度的新上界.本文结果表明.通过引入采样矩阵的分块结构信息.可以改进分片稀疏恢复的充分性条件.以及相应$l^0$或者$l^1$优化问题整体稀疏解的可靠性条件.

英文摘要:

      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.