-
摘要: 在系统生物学、信号处理等研究领域，许多问题都可以转化为块稀疏信号重构问题.一般而言，求解欠定系统线性方程的最稀疏解是一个NP困难问题.Block-StOMP算法是一种可以从压缩测量中重构块稀疏信号的贪婪算法，该算法不仅有满意的实际表现，而且还有理论保证.本文提出了Block-StOMP的一种改进算法，即mBlock-StOMP算法.该算法利用真发现率（True discovery rate）的估计值，对算法每阶段的支撑集进行精简，从而可以降低假报警率（False alarm rate），提高重构效率.进一步，本文给出了mBlock-StOMP算法的理论分析.对比Block-StOMP算法，仿真结果显示，在不明显增加计算量的情况下，mBlock-StOMP算法的重构精度优于Block-StOMP算法.Abstract: Many problems arisen in research fields like systems biology and signal processing can be formulated as problems of block sparse signal recovery. Generally, it is known that to pursue the sparsest solution of an underdetermined system of linear equations is non-deterministic polynomial (NP)-hard. To solve block sparse recovery problems, the algorithm of block stagewise orthogonal matching pursuit (Block-StOMP) has been proposed to recover block sparse signals from compressed measurements, which is a greedy algorithm with satisfactory practical performance and some particularly interesting theoretical properties. In this paper, we propose an improved version of Block-StOMP, termed mBlock-StOMP. Specifically, mBlock-StOMP uses the estimated TDR (true discovery rate) to prune support sets of each stage in order to decrease FAR (false alarm rate) and pursue high recovery accuracy. Moreover, rigorous theoretical analysis for mBlock-StOMP is given in this paper. Compared with Block-StOMP, simulation results demonstrate that mBlock-StOMP outperforms Block-StOMP in terms of reconstruction accuracy without increasing computational burden significantly.
-
Key words:
- Block sparse /
- compressed sensing /
- phase diagram /
- underdetermined system
-
Fig. 1 Progression of the mBlock-StOMP algorithm. Panels (a), (e), and (i) (the 1st column): Successive block matched filtering outputs. Panels (b), (f) and (j) (the 2nd column): Successive hard thresholding results. Panels (c), (g), and (k) (the 3rd column): Successive pruned support sets. Panels (d), (h), and (l) (the 4th column): Successive approximate solutions.
Fig. 2 Phase diagrams and predicted phase transition curves. (a) Block-StOMP. (b) mBlock-StOMP.
Fig. 3 Frequency of successful reconstruction as a function of block sparsity. (a) CFAR thresholding, $\eta=0$ , $S=10$ . (b) CFAR thresholding, $\eta=5 \times 10^{-6}$ , $S=10$ . (c) CFDR thresholding, $\eta=1 \times 10^{-1}$ , $q=0.2$ . (d) CFDR thresholding, $\eta=2 \times 10^{-5}$ , $q=0.1$ .
Fig. 4 Number of iterations as a function of block sparsity. (a) CFAR thresholding, $\eta=0$ , $S=10$ . (b) CFAR thresholding, $\eta=5 \times 10^{-6}$ , $S=10$ . (c) CFDR thresholding, $\eta=1 \times 10^{-1}$ , $q=0.2$ . (d) CFDR thresholding, $\eta=2 \times 10^{-5}$ , $q=0.1$ .
Fig. 5 Running time as a function of block sparsity. (a) CFAR thresholding, $\eta=0$ , $S=10$ . (b) CFAR thresholding, $\eta=5 \times 10^{-6}$ , $S=10$ . (c) CFDR thresholding, $\eta=1 \times 10^{-1}$ , $q=0.2$ . (d) CFDR thresholding, $\eta=2 \times 10^{-5}$ , $q=0.1$ .
Table Ⅰ Block-StOMP Algorithm
Input: measurement matrix ${\it\Phi}$ , measurement vector $\pmb{y}$ according
to $\pmb{y}={\it\Phi}\pmb{x}$ , and block-sparsity level $k$ ;
Output: the estimate of $\pmb{x}$Procedure:
The following steps will be performed repeatedly if the conditions ${s < S}$ and ${\left\|\pmb{r}_s\right\|_2>{\varepsilon}}$ and ${J_s} \ne {\varnothing}$ are all satisfied, until the stopping criterion becomes true.
Step 1: Matched Filtering.
$\pmb{c}_s{\left(j\right)}={\left\| \frac{{{\it\Phi}^{T}}\left[j\right]\pmb{r}_{s-1}} {\sigma_{s-1}}\right\|}_2^2, j=1, 2, \ldots, M$ .
Step 2: Hard Thresholding.
$\begin{array}{l} J_s^\prime = \left\{ {j:{\pmb{c}_s}\left( j \right) > {t_s}} \right\};\\ {J_s} = \left\{ {j;1 + \left[ {J_s^\prime \left( i \right) - 1} \right]d \le j \le J_s^\prime \left( i \right)d,i = 1,2, \ldots \left| {J_s^\prime } \right|} \right\}. \end{array}$
Step 3: Support Set Update. ${I_s=I_{s-1}\cup{J_s}}$ .
Step 4: Projection and Pursuit.
${\left({\pmb{x}_s}\right)_{I_s}={\left( {{\it\Phi}_{I_s}^{{T}}}{\it\Phi}_{I_s}\right)}^{-1} {{{\it\Phi}_{I_s}^{{T}}}\pmb{y}}}$ .
Step 5: Residual Update. ${\pmb{r}_s}= \pmb{y} -{\it \Phi} {\pmb{x}_s}$ .
下载: 导出CSV
Table Ⅱ mBlock-StOMP Algorithm
Input: measurement matrix ${\it\Phi}$ , measurement vector ${y}$ according
to ${\pmb{y}={\it\Phi}\pmb{x}}$ , and block-sparsity level $k$ .
Output: the estimate of the block-sparse signal ${\pmb{x}}$ .Procedure:
The following procedure will be performed repeatedly if the conditions ${s < S}$ and ${\left\|\pmb{r}_s \right\|>{\varepsilon}}$ and ${J_s} \ne {\varnothing}$ are all satisfied, otherwise it stops.
Step 1: Matched Filtering.
$\pmb{c}_s{\left(j\right)}={\left\|\frac{{{\it\Phi}^{{T}}} \left[j\right]\pmb{r}_{s-1}} {\sigma_{s-1}^{(1)}}\right\|}_2^2, j = $ $1, 2, \ldots, M$ ;
Step 2: Hard Thresholding.
$\tilde{J}_{s}^{\prime}=\left\{j:{{\pmb{c}_s{\left(j\right)}}>{t_s}}\right\}$ , where
$\tilde{J}_{s}=\left\{i:{1+\left[\tilde{J}_{s}^{\prime}{\left(j\right)}-1\right]d}\leq{i} \leq{\tilde{J}_{s}^{\prime}{\left(i\right)}d}, j=1, 2, \ldots, \left|\tilde{J}_{s}^{\prime}\right|\right\}$
Step 3: Estimate True Discovery Rate $\hat{\beta}_s$ .
To calculate $\hat{\beta}_s$ , we assume that matched filter coefficients chosen in Step 2 follow Gaussian distribution with nonzero mean:
$ \left\langle \pmb\phi_j, \pmb{r}_{s-1} \right\rangle \sim N\left(\mu_{s-1}, {\sigma_{s-1}^{(2)}}^2\right)$
The estimates of $\mu_{s-1}, \sigma_{s-1}^{(2)}$ can be obtained through maximum likelihood method. Thus, $\hat{\beta}_s$ can be calculated as follows:
$\hat{\beta}_s={\rm Prob}\left\{ \chi_{d, \sum\limits_{i=1}^d {\left( \frac{\mu_{s-1}}{\sigma_{s-1}^{(2)}} \right)^2}}^2 > t_s \cdot \frac{{\sigma_{s-1}^{(1)}}^2}{{\sigma_{s-1}^{(2)}}^2} \right\}$
and we take the cardinality of $\tilde{J}'_s$ as the estimate of $k_s$ , denoted as $\hat{k}_s$ .
Step 4: Pruning $\tilde{J}_{s}$ .
First, update set according to $\tilde{I}_s =I_{s-1} \cup \tilde{J}_{s}$ , and then use Least- squares, ${\left({\pmb{x}_s}\right)_{\tilde{I}_s}={\left({{\it\Phi}_{\tilde{I}_s}^{{T}}}{\it\Phi}_{\tilde{I}_s}\right)}^{-1} {{{\it\Phi}_{\tilde{I}_s}^{{T}}}\pmb{y}}};$ based on the above solution, we can get $(\pmb{x}_s)_{\tilde{J}_{s}}$ and $(\pmb{x}'_s)_{\tilde{J}'_{s}}$ , corresponding to $\tilde{J}_{s}$ , which can be written as $(\pmb{x}'_s)_{\tilde{J}'_{s}}=\left( (\pmb{x}'_s)_{\tilde{J}'_{s}}[1], \ldots, (\pmb{x}'_s)_{\tilde{J}'_{s}}[\hat{k}_s]\right)$
where $(\pmb{x}'_s)_{\tilde{J}'_{s}}[j] =\sum_{i=(j-1)d+1}^{jd}({(\pmb{x}_s)_{\tilde{J}_{s}}(i)})^2, j=1, $ $2, \ldots, $ $\hat{k}_s$ .
Then, sort the elements of $(\pmb{x}'_s)_{\tilde{J}'_{s}}$ in descending order based on their amplitudes, and we take the first $\hat{k}_s \times\hat{\beta}_s$ indices as the components of $J'_s$ , and
$J_s=$ $\left\{i:{1+\left[J'_s{\left(j\right)}-1\right]d}\leq{i} \leq{J'_s{\left(i\right)}d}, j=1, 2, \ldots, |J'_s|\right\}$ .
Step 5: Support Set Update. ${I_s=I_{s-1}\cup{J_s}}$ .
Step 6: Projection and Pursuit.
${\left({\pmb{x}_s}\right)_{I_s}={\left({{\it\Phi}_{I_s}^{{T}}}{\it\Phi}_{I_s}\right)}^{-1}{{{\it\Phi}_{I_s}^{{T}}}\pmb{y}}}$ .
Step 7: Residual Update. ${\pmb{r}_s=\pmb{y}-{\it\Phi}\pmb{x}_s}$ .
下载: 导出CSV
-
[1] D. L. Donoho, Y. Tsaig, I. Drori, and J. L. Starck, "Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, "IEEE Trans. Inf. Theory, vol. 58, no. 2, pp. 1094-1120, Feb. 2012. http://dl.acm.org/citation.cfm?id=2332326 [2] J. Xiong and T. Zhou, "Gene regulatory network inference from multifactorial perturbation data using both regression and correlation analyses, "PLoS One, vol. 7, no. 9, Article ID e43819, Sep. 2012. http://europepmc.org/articles/PMC3448649 [3] T. Zhou and Y. L. Wang, "Causal relationship inference for a large-scale cellular network, "Bioinformatics, vol. 26, no. 16, pp. 2020-2028, Aug. 2010. https://academic.oup.com/bioinformatics/article/26/16/2020/216870/Causal-relationship-inference-for-a-large-scale [4] Y. L. Wang and T. Zhou, "A relative variation-based method to unraveling gene regulatory networks, "PLoS One, vol. 7, no. 2, Article ID e31194, Feb. 2012. http://europepmc.org/abstract/med/22363578 [5] W. H. Zhang, B. X. Huang, and T. Zhou, "An improvement on StOMP for sparse solution of linear underdetermined problems, "in Proc. the 32nd Chinese Control Conf. , Xi'an, China, 2013, 1951-1956. http://ieeexplore.ieee.org/document/6639746/ [6] B. M. Sanandaji, T. L. Vincent, and M. B. Wakin, " Exact topology identification of large-scale interconnected dynamical systems from compressive observations, "in Proc. the 2011 American Control Conf. , 2011, pp. 649-656. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5990982 [7] D. L. Donoho, "For most large underdetermined systems of linear equations the minimal-norm solution is also the sparsest solution, "Commun. Pure Appl. Math. , vol. 59, no. 6, pp. 797-829, Mar. 2006. https://www.researchgate.net/publication/284048721_For_Most_Large_Underdetermined_Systems_of_Linear_Equations_the_Minimal_L1-norm_Solution_is_also_the_Sparsest_Solution [8] M. A. Davenport and M. B. Wakin, "Analysis of orthogonal matching pursuit using the restricted isometry property, "IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4395-4401, Sep. 2010. http://ieeexplore.ieee.org/document/5550495 [9] S. S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by basis pursuit, "SIAM J. Sci. Comput. , vol. 20, no. 1, pp. 33-61, Aug. 1998. http://dl.acm.org/citation.cfm?id=305222&dl= [10] S. G. Mallat and Z. F. Zhang, "Matching pursuits with time-frequency dictionaries, "IEEE Trans. Signal Processing, vol. 41, no. 12, pp. 3397-3415, Dec. 1993. http://dl.acm.org/citation.cfm?id=2203996 [11] J. A. Tropp and A. C. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit, "IEEE Trans. Inf. Theory, vol. 53, no. 12, pp. 4655-4666, Dec. 2007. http://ieeexplore.ieee.org/document/4385788/ [12] Y. C. Eldar, P. Kuppinger, and H. Bolcskei, "Block-sparse signals: Uncertainty relations and efficient recovery, "IEEE Trans. Signal Processing, vol. 58, no. 6, pp. 3042-3054, Jun. 2010. http://dl.acm.org/citation.cfm?id=1820926.1820937 [13] R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, "Model-based compressive sensing, "IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 1982-2001, Apr. 2010. http://dl.acm.org/citation.cfm?id=1821075 [14] L. Yu, H. Sun, J. P. Barbot, and G. Zheng, "Bayesian compressive sensing for cluster structured sparse signals, "Signal Processing, vol. 92, no. 1, pp. 259-269, Jan. 2012. http://www.sciencedirect.com/science/article/pii/S0165168411002490 [15] M. Stojnic, F. Parvaresh, and B. Hassibi, "On the reconstruction of block-sparse signals with an optimal number of measurements, "IEEE Trans. Signal Processing, vol. 57, no. 8, pp. 3075-3085, Apr. 2009. http://dl.acm.org/citation.cfm?id=1653443 [16] B. X. Huang and T. Zhou, "Recovery of block sparse signals by a block version of StOMP, "Signal Processing, vol. 106, pp. 231-244, Jan. 2015. http://www.sciencedirect.com/science/article/pii/S0165168414003570 [17] J. Wang, S. Kwon and B. Shim, "Generalized orthogonal matching pursuit, "IEEE Trans. Signal Processing, vol. 60, no. 12, pp. 6202-6216, Dec. 2012. http://ieeexplore.ieee.org/document/6302206/ [18] W. H. Zhang, T. Zhou, and B. X. Huang, "Outlier deletion based improvement on the StOMP algorithm for sparse solution of large-scale underdetermined problems, "Sci. China Inf. Sci. , vol. 57, no. 9, pp. 1-14, Sep. 2014. http://kns.cnki.net/KCMS/detail/detail.aspx?filename=jfxg201409020&dbname=CJFD&dbcode=CJFQ -
图(5) / 表(2)
计量
- 文章访问数: 1449
- HTML全文浏览量: 127
- PDF下载量: 623
- 被引次数: 0
