2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Efficient Recovery of Block Sparse Signals by an Improved Algorithm of Block-StOMP

Huang Boxue Zhou Tong

黄博学, 周彤. 利用Block-StOMP的一种改进算法高效重构块稀疏信号. 自动化学报, 2017, 43(9): 1607-1618. doi: 10.16383/j.aas.2017.e150116
引用本文: 黄博学, 周彤. 利用Block-StOMP的一种改进算法高效重构块稀疏信号. 自动化学报, 2017, 43(9): 1607-1618. doi: 10.16383/j.aas.2017.e150116
Huang Boxue, Zhou Tong. Efficient Recovery of Block Sparse Signals by an Improved Algorithm of Block-StOMP. ACTA AUTOMATICA SINICA, 2017, 43(9): 1607-1618. doi: 10.16383/j.aas.2017.e150116
Citation: Huang Boxue, Zhou Tong. Efficient Recovery of Block Sparse Signals by an Improved Algorithm of Block-StOMP. ACTA AUTOMATICA SINICA, 2017, 43(9): 1607-1618. doi: 10.16383/j.aas.2017.e150116

利用Block-StOMP的一种改进算法高效重构块稀疏信号

doi: 10.16383/j.aas.2017.e150116
基金项目: 

the Specialized Research Fund for the Doctoral Program of Higher Education, China 20110002110045

the National Natural Science Foundation of China 60721003

the National Basic Research Program of China (973 Program) 2012CB316504

the National Natural Science Foundation of China 61174122

the National Natural Science Foundation of China 61021063

the National Basic Research Program of China (973 Program) 2009CB320602

the National Natural Science Foundation of China 60625305

Efficient Recovery of Block Sparse Signals by an Improved Algorithm of Block-StOMP

Funds: 

the Specialized Research Fund for the Doctoral Program of Higher Education, China 20110002110045

the National Natural Science Foundation of China 60721003

the National Basic Research Program of China (973 Program) 2012CB316504

the National Natural Science Foundation of China 61174122

the National Natural Science Foundation of China 61021063

the National Basic Research Program of China (973 Program) 2009CB320602

the National Natural Science Foundation of China 60625305

More Information
    Author Bio:

    Tong Zhou is a Professor of control theory and control engineering, Tsinghua University. He received the B.S. and M.S. degrees from the University of Electronic Science and Technology of China, Chengdu, China, in 1984 and 1989, respectively, another M.S. degree from Kanazawa University, Ishikawa Prefecture, Japan, in 1991, and the Ph.D. degree from Osaka University, Osaka, Japan, in 1994. His current research interests include robust control, system identification, signal processing and their applications to real-world problems in molecular cell biology, spatio-temporal systems. Dr. Zhou was a recipient of the First-Class Natural Science Prize in 2003 from the Ministry of Education, China, and a recipient of the National Outstanding Youth Foundation of China Award in 2006. He has served as an Associate Editor of both the IEEE Transactions on Automatic Control and Automatica. E-mail: tzhou@mail.tsinghua.edu.cn

    Corresponding author: Boxue Huang is a Senior Engineer of Institute of Electronics, Chinese Academy of Sciences. He received the bachelor degree from Huazhong University of Science and Technology in 2009 and the Ph.D. degree from Tsinghua University in 2016. His research interests include system identification, signal processing and systems biology. Corresponding author of this paper. E-mail: bxhuang@mail.ie.ac.cn
  • 摘要: 在系统生物学、信号处理等研究领域,许多问题都可以转化为块稀疏信号重构问题.一般而言,求解欠定系统线性方程的最稀疏解是一个NP困难问题.Block-StOMP算法是一种可以从压缩测量中重构块稀疏信号的贪婪算法,该算法不仅有满意的实际表现,而且还有理论保证.本文提出了Block-StOMP的一种改进算法,即mBlock-StOMP算法.该算法利用真发现率(True discovery rate)的估计值,对算法每阶段的支撑集进行精简,从而可以降低假报警率(False alarm rate),提高重构效率.进一步,本文给出了mBlock-StOMP算法的理论分析.对比Block-StOMP算法,仿真结果显示,在不明显增加计算量的情况下,mBlock-StOMP算法的重构精度优于Block-StOMP算法.
    Recommended by Associate Editor Xuegong Zhang
  • 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)
计量
  • 文章访问数:  1394
  • HTML全文浏览量:  123
  • PDF下载量:  615
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-07-23
  • 录用日期:  2016-06-12
  • 刊出日期:  2017-09-20

目录

    /

    返回文章
    返回