基于差值映射的压缩感知MUSIC算法

吕志丰 雷 宏



基于差值映射的压缩感知MUSIC算法

吕志丰*①②雷 宏①

①(中国科学院电子学研究所 北京 100190)②(中国科学院大学 北京 100049)

多快拍(MMV)问题旨在恢复具有相同稀疏结构的多列信号。在传统阵列信号处理中MMV问题的求解通常采用多重信号分类(MUSIC)等确定性方法实现，但当快拍数不足或存在相干源时该类方法失效；而在压缩感知(CS)的概率求解模型下，即使信源相干也能得到恢复结果，但现有算法普遍性能不足。近期Kim等人的研究表明，将CS与MUSIC相结合可得到比二者更加优秀的性能和更为宽泛的使用条件，该方法被称作压缩感知 MUSIC或CS-MUSIC算法。作为一种投影型非凸优化算法，差值映射(DM)最早用于解决X射线晶体学中的相位恢复问题，并逐渐在其他非凸及压缩感知问题的求解中展示出优良性能。该文提出一种基于差值映射的CS-MUSIC算法，仿真结果表明该算法在MMV问题求解中十分有效，相比经典CS-MUSIC具有更高的恢复成功率。

压缩感知；多快拍问题；联合稀疏；多重信号分类；差值映射

1 引言

压缩感知(Compressed Sensing, CS)[1,2]主要研究在严重欠采样的情况下如何精确恢复具有稀疏结构的信号。其求解理论基于概率模型，通常借助一系列的优化算法来实现信号恢复。近年来CS已成为信号处理领域的研究热点之一，并且在不同应用方向取得了成功。在CS理论中，多快拍问题(Multiple Measurement Vector, MMV)旨在辨识具有相同稀疏支集的多列未知信号，基于CS的求解算法在快拍数不足和信源相干时仍可得到MMV问题的解，但目前算法在性能上普遍受稀疏度影响严重。

在传统阵列信号处理中，MMV问题等价于波达方向(Direction-Of-Arrival, DOA)估计问题[9]。这类问题的求解往往基于信号和噪声子空间的确定性模型，通过空间谱扫描得到最终结果，其中以多重信号分类(MUSIC)算法[10]最具代表性。该类方法理论性能良好，但在快拍数不足或信源相干时将失效。

结合CS在使用条件上的宽泛性和MUSIC类算法在性能上的优良性，Kim等人在文献[11]中创新性地提出了CS-MUSIC算法用于MMV问题的求解。该文献从理论上给出了CS-MUSIC算法的性能分析，并详细阐述了CS和MUSIC类算法之间的内在联系。同期文献[12]也给出了相似的独立结果，并将其方法称为子空间增强型多重分类(Subspace- Augmented MUSIC, SA-MUSIC)。

作为一种非凸优化算法，差值映射[13,14](Difference Map, DM)最早用于解决X射线晶体学中的相位恢复问题[15,16]，并逐渐在其他非凸及压缩感知问题的求解中展示出优良性能[14,17,18]。文献[18]将DM算法引入到CS单快拍(Single Measurement Vector, SMV)问题的求解和稀疏字典编码中，结论表明其性能要远远优于现有的大多CS算法。

本文将差值映射引入到MMV问题的求解中，并提出了一种基于差值映射的CS-MUSIC算法。仿真结果表明本文所述方法在MMV问题的求解中十分有效，且使得经典CS-MUSIC的恢复性能得到了显著提高。

本文组织结构如下：在第2节中分别介绍MMV问题、CS-MUSIC算法以及差值映射算法；在第3节中给出DM算法在MMV问题和CS-MUSIC中的具体求解过程；第4节通过数值仿真验证本文所提算法的有效性和性能优势。

2 多快拍问题及差值映射算法

2.1压缩感知和多快拍问题

目前CS框架下用于求解MMV问题的方法主要有贪婪类算法(如同时正交匹配追踪Simultaneous Orthogonal Matching Pursuit, S-OMP[20,21])、混合范数凸松驰类算法[22,23]、贝叶斯类方法(如多重稀疏贝叶斯学习(Multiple Sparse Bayesian Learning, M-SBL)[24])、随机类算法(如Reduce MMV and Boost, ReMBo[25])以及基于块稀疏模型的算法[26,27]等。但当前多数求解算法在性能上与此理论上限还存在相当差距[11]，随着信号稀疏度的变大，信号恢复效果将逐渐变差。

2.2 CS-MUSIC算法

在阵列信号处理的DOA估计中，传统方法主要有Capon最小方差方法[28]、MUSIC算法[10]、基于旋转不变技术的信号参数估计(Estimation of Signal Parameters via Rotational Invariance Techniques, ESPRIT)[29]等，其中以MUSIC算法的应用最为广泛。在信源不相干的条件下，文献[19]给出了MUSIC算法在MMV问题求解中的性能上限为

这表明在快拍数足够时，MUSIC算法可达到对MMV问题的理想恢复。但在信源相干条件下，即信号矩阵中存在相关行时，MUSIC算法将失效。

结合CS的概率性重建方式和MUSIC算法的确定性重建方式，Kim等人提出了CS-MUSIC算法[11]。该算法的主要思想是将待恢复的个非零行拆分为两部分，首先通过压缩感知算法(如同时正交匹配追踪(S-OMP)、二阈值(2-thresholding)等)求得行支集，再利用已得支集的信息构建新的噪声子空间，通过类似MUSIC算法的空间谱扫描计算得出剩余支集位置。CS-MUSIC在接近1时(即单快拍模式)趋于CS算法；而在接近时趋于传统MUSIC算法[11]。该算法很好地结合了CS和MUSIC的优点，在拓宽使用条件的基础上保持了优良性能。作者在文中同时指出，即使存在相干信源，CS-MUSIC的恢复性能仍可达到MMV问题的理论上限。

2.3差值映射算法

差值映射算法最早由文献[13]在解决X射线晶体学中的相位恢复问题时提出。在DM算法中，某一问题的解被看作两个约束条件集合与的交集，集合,分别描述了该问题解所满足的一类约束条件。空间点向,的投影分别表示为与，定义为相应集合中与距离最短的点，即

通过在两个条件集合间的不断投影，迭代点最终收敛于交集处从而得到问题的解。DM算法的一步迭代定义为

本文将DM算法推广到MMV问题的求解中，并在CS-MUSIC算法中加以应用。仿真结果表明，本文所述基于DM的CS-MUSIC算法性能优秀，相比原始文献[11]中的实验结果在恢复成功率上得到了显著提升。

3 DM算法在MMV问题求解和CS-MUSIC中的具体实现

3.1 DM求解压缩感知MMV问题

3.2 基于DM的CS-MUSIC算法

根据3.1节的分析及文献[11]中对CS-MUSIC算法的描述，本文提出基于DM的CS-MUSIC算法步骤为：

4 仿真实验结果

4.1随机MMV问题求解

图1算法收敛性曲线(SNR=)

图2 相对误差和迭代次数随参数变化曲线(SNR=)

图3算法收敛性曲线(SNR=40 dB)

图4 相对误差和迭代次数随参数变化曲线(SNR=40 dB)

4.2 基于DM的CS-MUSIC算法性能比较

这里对本文第3节所述基于DM的CS-MUSIC算法进行仿真实验，并同文献[9]中基于S-OMP的算法及传统MUSIC算法等进行性能上的对比。取高斯分布的随机信号长度，稀疏度，限制以保证信源相干条件，采样信噪比；针对内不同阵元数分别进行求解，若所得结果与真实信号支集位置相同则定义为求解成功；重复独立随机实验500次，统计各算法所有值对应的成功概率。实验中假设信号稀疏度为已知，DM算法参数,，最大迭代次数限制为500。分别对S-OMP算法、传统MUSIC算法、基于S-OMP的CS-MUSIC算法及本文所述基于DM的CS-MUSIC算法进行上述实验过程，对快拍数及两种情形的统计结果分别如图5、图6所示。

图5 恢复成功率随阵元数变化关系(n=128, r=15)

图6 恢复成功率随阵元数变化关系(n=128, r=256)

5 结束语

本文将差值映射算法引入到多快拍问题的求解中，并将其应用于CS-MUSIC算法。数值实验表明DM算法对MMV问题的求解十分有效，且基于DM的CS-MUSIC算法在性能上具有明显优势，可在保持求解精度的条件下有效缩减阵元数量，从而节省阵列信号处理的系统成本。本文算法在求解结果上表现优异，如何从理论上优化参数选择、加快算法收敛速度，以及分析和提升算法的噪声鲁棒性则是下一步研究的重点。

参考文献

[1] Donoho D. Compressed sensing[J]., 2006, 52(4): 1289-1306.

[2] Cades E, Romberg J, and Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]., 2006, 52(2): 489-509.

[3] Fang L Y, Li S T, Ryan P,.. Fast acquisition and reconstruction of optical coherence tomography images via sparse representation[J]., 2013, 32(11): 2034-2049.

[4] Yang J, Thompson J, Huang X T,.. Segmented reconstruction for compressed sensing SAR imaging[J]., 2013, 51(7): 4214-4225.

[5] Friedland, S, Li Q, and Schonfeld D. Compressive sensing of sparse tensors[J]., 2014, 23(10): 4438-4447.

[6] Hawes M B and Liu W. Robust sparse antenna array design via compressive sensing[C]. IEEE International Conference on Digital Signal Processing, Nice, France, 2013: 1-5.

[7] Northardt E T, Bilik I, and Abramovich Y I. Spatial compressive sensing for direction-of-arrival estimation with bias mitigation via expected likelihood[J]., 2013, 61(5): 1183-1195.

[8] Nagahara M, Quevedo D E, and Ostergaard J. Sparse packetized predictive control for networked control over erasure channels[J]., 2014, 59(7): 1899-1905.

[9] Krim H and Viberg M. Two decades of array signal processing research: the parametric approach[J]., 1996, 13(4): 67-94.

[10] Schmidt R. Multiple emitter location and signal parameter estimation[J]., 1986, 34(3): 276-280.

[11] Kim J M, Lee O K, and Ye J C. Compressive MUSIC: revisiting the link between compressive sensing and array signal processing[J]., 2012, 58(1): 278-301.

[12] Lee K and Bresler Y. Subspace-augmented MUSIC for joint sparse recovery with any rank[C]. Proceedings of the IEEE Sensor Array and Multichannel Signal Processing Workshop, Jerusalem, Israel, 2010: 205-208.

[13] Elser V. Phase retrieval by iterated projections[J]., 2003, 20(1): 40-55.

[14] Elser V, Rankenburg I, and Thibault P. Searching with iterated maps[J]., 2007, 104(2): 418-423.

[15] Eldar Y C, Sidorenko P, Mixon D G,.. Sparse phase retrieval from short-time Fourier measurements[J]., 2015, 22(5): 638-642.

[16] Shechtman Y, Beck A, and Eldar Y C. GESPAR: efficient phase retrieval of sparse signals[J]., 2014, 62(4): 928-938.

[17] Qiu K and Dogandzic A. Nonnegative signal reconstruction from compressive samples via a difference map ECME algorithm[C]. Proceedings of the IEEE Statistical Signal Processing Workshop, Nice, France, 2011: 561-564.

[18] Landecker W, Chartrand R, and DeDeo S. Robust compressed sensing and sparse coding with the difference map[C]. IEEE European Conference on Computer Vision, Zurich, Switzerland, 2014:315-329.

[19] Feng P. Universal minimum-rate sampling and spectrum-blind reconstruction for multiband signals[D]. [Ph.D. dissertation], University of Illinois, Urbana-Champaign, 1997.

[20] Chen J and Huo X. Theoretical results on sparse representations of multiple measurement vectors[J]., 2006, 54(12): 4634-4643.

[21] Tropp J A, Gilbert A C, and Strauss M J. Algorithms for simultaneous sparse approximation, Part I: Greedy pursuit[J]., 2006, 86(3): 572-588.

[22] Malioutov D, Cetin M, and Willsky A S. A sparse signal reconstruction perspective for source localization with sensor arrays[J]., 2005, 53(8): 3010-3022.

[23] Tropp J A. Algorithms for simultaneous sparse approximation. Part II: Convex relaxation[J]., 2006, 86(3): 589-602.

[24] Wipf D P. Bayesian methods for finding sparse representations[D]. [Ph.D. dissertation], University of California, San Diego, 2006.

[25] Mishali M and Eldar Y C. Reduce and boost: recovering arbitrary sets of jointly sparse vectors[J]., 2008, 56(10): 4692-4702.

[26] Eldar Y C, Kuppinger P, and Bolcskei H. Compressed sensing of block-sparse signals: uncertainty relations and efficient recovery[J]., 2010, 58(6): 3042-3054.

[27] Baraniuk R G, Cevher V, Duarte M F,.. Model-based compressive sensing[J]., 2010, 56(4): 1982-2001.

[28] Capon J. High-resolution frequency-wavenumber spectrum analysis[J]., 1969, 57(8): 1408-1418.

[29] Roy R and Kailath T. ESPRIT-estimation of signal parameters via rotational invariance techniques[J]., 1989, 37(7): 984-995.

[30] Fienup J R. Phase retrieval algorithms: a comparison[J]., 1982, 21(15): 2758-2769.

[31] Bauschke H and Borwein J. On projection algorithms for solving convex feasibility problems[J]., 1996, 38(3): 367-426.

[32] Adiga A and Seelamantula C S. An alternating Lp-L2 projections algorithm (ALPA) for speech modeling using sparsity constraints[C]. IEEE International Conference on Digital Signal Processing, Hong Kong, China, 2014: 291-296.

[33] Yan W, Wang Q, and Shen Y. Shrinkage-based alternating projection algorithm for efficient measurement matrix construction in compressive sensing[J]., 2014, 63(5): 1073-1084.

[34] Hesse R, Luke D R, and Neumann P. Alternating projections and Douglas-Rachford for sparse affine feasibility[J]., 2014, 62(18): 4868-4881.

Compressive Sensing MUSIC Algorithm Based on Difference Map

Lü Zhi-feng①②Lei Hong①­­­­­

①(,,100190,)②(,100049,)

The Multiple Measurement Vectors (MMV) problem addresses the recovery of unknown input vectors which share the same sparse support. The Compressed Sensing (CS) has the capability of estimating the sparse support even in coherent cases, where the traditional array processing approaches like MUltiple SIgnal Classification (MUSIC) often fail. However, CS guarantees the accurate recovery in a probabilistic manner, and often shows inferior performance in cases where the traditional ways succeed. Recently, a novel compressive MUSIC (or CS-MUSIC) algorithm is proposed by Kim., in which both the advantages of CS and traditional MUSIC-like methods are combined together. As an iterative projecting algorithm, Difference Map (DM) is first used to solve the phase retrieval problem in crystallography. Recent results show that it has excellent performance in solving a wide variety of non-convex problems like compressed sensing. In this paper, a DM-based CS-MUSIC algorithm is proposed. Experiments show that the proposed algorithm is very effective in MMV problem solving and the success rate of CS-MUSIC is dramatically improved.

Compressed Sensing (CS); Multiple Measurement Vectors (MMV) problem; Joint sparsity; MUltiple SIgnal Classification (MUSIC); Difference Map(DM)

TN911.72

A

1009-5896(2015)08-1874-05

10.11999/JEIT141542

吕志丰 snowby2010@gmail.com

2014-12-04收到，2015-03-13改回，2015-06-09网络优先出版

吕志丰： 男，1987年生，博士生，研究方向为压缩感知、阵列信号处理.

雷 宏： 男，1963年生，研究员，博士生导师，研究方向为电磁场与微波技术、天线理论与工程、信号处理理论与技术.