结构化信号处理理论和方法的研究进展

李廉林　周小阳　崔铁军

①（北京大学信息科学技术学院　北京　100871）

②（东南大学毫米波国家重点实验室　南京　210096）

结构化信号处理理论和方法的研究进展

李廉林*①周小阳②崔铁军②

①（北京大学信息科学技术学院北京100871）

②（东南大学毫米波国家重点实验室南京210096）

结构化信号处理是近年来信息领域发展极为迅猛的一个研究分支，它革新了以Nyquist-Shannon理论为基础的信号处理经典体系的众多结论，开启了面向对象的信息处理的大门，促使挖掘信号的结构性与自适应测量有机结合，推动了信息论、电子学、医疗、应用数学、物理等领域的发展。结构化信号处理研究结构化信号的获取、表征、复原及应用等问题，主要包含4方面内容：（1）研究结构化信号表征与测度的模型和理论；（2）研究结构化信号的复原模型、理论及算法实现；（3）研究信号获取的新体制；（4）研究结构化信号处理的应用。该文以数据和先验两类信息源的融合为主线，讨论了结构化信号处理在信号表征和大尺度信号复原等方面的最新研究结果，并对该领域的发展进行了展望。

结构化信号；稀疏信号处理；奈奎斯特采样定理；任务驱动信号处理

1　引言

结构化（包括稀疏）信号处理是过去10多年间信息领域发展最为迅猛的一个研究分支，它革新了人们对信息领域众多理论方法的认知，极大推动了通信、医疗、电子学、雷达、应用数学、物理等学科的发展。结构化信号处理是“实验-理论-计算-数据挖掘”这种科学发展模式的必然产物，是信息论、数值计算、概率与统计等多学科融合发展的结果（图1）。结构化信号处理研究结构化信号的获取、表征、复原及应用等问题，具体包含4方面的研究内容［1-3］：（1）研究结构化信号表征与测度的模型和理论；（2）研究结构化信号的复原模型、理论及算法实现；（3）研究信号获取的新体制；（4）研究结构化信号处理的应用。

图1　结构化信号处理与信息论等学科之间的关系Fig.1　The relation of structural signal processing to other disciplines

经典信号处理根植于20世纪初由Kotelnikov，Nyquist，Shannon及Whittaker等人建立的连续信号采样理论（Nyquist-Shannon信号采样理论）：为保证信号的无失真处理，信号的采样频率必须不低于该信号最大频率的2倍。从线性代数的角度，经典信号处理体系处理完备或超完备线性方程组y=Ax，其中dim（y）≥dim（x），其核心是测量数据y∈ Y完备地包含了目标信号x∈X的全部信息，两者之间满足一一对应关系，其中X和Y是两个赋范线性空间；利用经典线性代数（或矩阵求逆）方法能够从数据y复原信号x。为论述方便，本文分别称y和x为数据和目标信号。以Nyqusit-Shannon理论为核心的经典信号处理体系为人们打开从模拟（Analogy）时代进入数字（Digital）时代的大门，拓展了模拟信息处理的能力，提供了更有效的信息感知和处理技术。随着数据和信息量的爆炸性发展（摩尔定律，Moore's Law），以经典信号理论为指导的数字时代展现了前所未有的挑战和机遇：海量数据处理。例如，以1米分辨率、900平方公里观测带内的星载合成孔径雷达（SAR）成像为例，数据量将达到几个GB，若要同时获取多极化等多维度信息，产生的数据量至少要增加4～8倍［4］。在这样的时代背景下，结构化（包括稀疏）信号处理应运而生。结构化信号处理以挖掘和利用目标信号或数据的结构为核心，以发展有效的信息获取、重构和解译等方法为宗旨，促进信息及其相关学科的发展。经典信号处理坚信的理念是“Let data say themselves···”。结构化信号处理不仅仅只关心数据，在处理数据的同时挖掘信号本身内在蕴含的信息（先验，prior）。也可以说结构化信号处理处理更广义的数据：狭义数据和先验。与之相比，经典信号处理仅考虑目标信号本身，不考虑信号内在固有的信息（尽管这些信息已被很好认知或将被认知），因此经典信号处理的许多结论过于保守和悲观。例如，Nyquist-Shannon定理本身就过于悲观，它仅利用了信号的带宽信息；Rayleigh分辨率也是一个过于悲观的结论，它也是只利用系统带宽信息的产物。结构化信号处理不仅处理数据，而且挖掘利用目标信号的先验，将目标信号的先验知识有机融入信号的获取和处理中，为发展高性能信息感知奠定了基础。以压缩感知为例，它利用信号的稀疏性或可压缩性，在信号获取的同时进行信号压缩，有效地缓解了数据获取和通信的压力［5-17］。表1比较了经典信号处理和结构化信号处理两种体系的重要差异。

信号结构性的一个代表性例子就是信号的稀疏性（Sparsity）。例如，如果图像的像素之间具有相关性，那么该图像在离散余弦或某种小波变换域是稀疏的。目前流行的各种图像或视频压缩技术正是利用了这种结构性。对信息领域的多数科研工作者而言，稀疏这个术语并不陌生，这里对稀疏信号的发展历史作个回顾。1795年，Prony提出了噪声干扰情况下从稀疏复指数函数的线性组合中估计复指数参数的方法（Prony方法）［18］。1809年，Laplace提出Laplace分布以及l1测度的概念，Gauss对该工作评价是“Laplace made use of another principle for the solution of linear equations，the number of which is greater than the number of unknown quantities，···”［19，20］。1907年，Caratheodory理论证明：对于k个正弦波线性组合的信号，如果已知它在t=0处及其它任意2k个位置处的测量值，该信号就可以唯一确定［21，22］；显然Caratheodory方法所需的测量数据数2k+1远小于Nyquist-Shannon理论所需的采样点数。1938年，Beuring研究了基于l1范数最小化方法的时域稀疏信号（Spike信号）的完整频域谱复原问题［23］，其方法与目前压缩感知领域的信号复原方法非常相似。1973年，Clearbout和Muir针对地震波反卷积问题提出了数据拟合误差的l1范数最小化问题，并提出与之对应的线性规划算法［24］。1979年，Taylor等人进一步研究了数据拟合误差的l1范数最小化的l1范数正则化问题［25］。1986年，Stantosa和Symes提出了数据拟合误差最小l2范数最小化的l1范数正则化问题，并从理论上揭示了稀疏性与l1范数正则化之间的关系［26，27］。1986年，Coifman和Wickerhauser等人提出了稀疏分解的概念，几乎与此同时，Mallat和Zhang在小波分析的基础上也提出了信号在超完备字典上分解的思想。斯坦福大学的Tibshirani等人［28］和Chen等人［29］分别从机器学习和信号处理的角度几乎同一时间（尽管论文发表日期分别是1996年和1998年，有趣的是两组作者的办公室在斯坦福大学同一院系的同一个走廊）提出了l1范数正则化的稀疏线性模型。尽管稀疏信号处理方法得到了长足发展，人们也清晰地意识到在一些情况下利用目标信号的稀疏性可以有效地正则化病态问题，克服经典信号处理方法遇到的种种制约；但是这些方法是启发式的，缺乏理论支撑。其中一个亟需解决的根本性问题是：在什么条件下目标信号的稀疏性能保证病态问题的精确、稳定求解。直至2004年至2009年，Candes，Tao，Romberg和Donoho等人提出了压缩感知理论［5-17］，该理论首次回答了精确稳定求解线性病态问题所需要的目标信号稀疏性和问题病态性（测量数据）之间需要满足的关系（例如，Candes-Romberg-Tao定理［16］），它明确了观测数据和目标信号先验（稀疏性或可压缩性）有机融合对精确稳定重构目标信号的作用。从这个角度而言，目前在电磁（包括雷达）成像等众多应用所谓的“压缩感知成像方法”只是稀疏驱动成像，并不是真正意义上的压缩感知成像。自从压缩感知提出以来，以挖掘利用目标信号结构性为核心的信息感知和处理方法得到了前所未有的发展，并推动了信号获取体制的改革。以压缩感知理论为代表的结构化信号感知方法革命性地发展了以Nyquist-Shannon理论、经典线性代数及Gaussian假设检验等为基石的经典信号处理体系，开启了面向对象的信号处理的大门，促使将挖掘利用信号结构化特性与智能测量有机结合，积极地推动了信息论、电子、医疗、应用数学、物理等学科的发展［30-39］。

表1　经典信号处理和结构化信号处理两种体系的差异Tab. 1 Comparisons between classical signal processing and structural signal processing

结构化信号处理的研究在国外迅速开展的同时，国内在该领域的研究也开始起步。2007年，中国科学院电子学研究电磁场理论与应用研究室的李芳课题组在国内率先开展了稀疏信号处理方面的研究，向寅的博士论文首次将稀疏信号处理引入聚束合成孔径雷达成像领域，将稀疏信号处理引入电磁逆散射问题，发展了若干分辨率增强的新型电磁逆散射算法［40］。张文吉的博士论文将稀疏信号处理引入穿墙雷达成像，研究了稀疏信号处理在降低穿墙雷达数据量和提高成像质量方面的作用［41］。刘艳丽的博士论文将稀疏成像引入电离层层析成像，降低了电离层层析成像的病态性，提高了成像效果［42］。2009年，由中科院电子所牵头的稀疏微波成像项目列入了我国973计划资助［4］，随后国家自然科学基金委也陆续资助了其它多项关于稀疏信号处理研究的重大和重点项目。在这些项目资助下，中科院电子所、中科院数学与系统应用研究所、西安电子科技大学、北京理工大学、北京航空航天大学、西安交通大学、国防科技大学、清华大学等单位在结构化信号处理领域（主要是应用领域）开展了广泛的研究，例如，西安电子科技大学保铮课题组在稀疏雷达（ISAR，InSAR）成像方面的研究［43，44］、西安电子科技大学石光明课题组在图像处理方面的研究［45］、西安交通大学徐宗本课题组在稀疏信号复原算法方面的研究［46］、国防科技大学金添课题组在稀疏穿墙雷达成像应用方面的研究［47］等等，使我国在稀疏信号处理领域的研究得到了长足发展。我国在稀疏信号处理领域发表论文数方面超欧美国家的论文数（是美国的2倍，德国的8倍左右），但从具有原创性和高影响力的论文方面来看，我国在结构化信号处理方面的研究还具有较大差距（见图2）。

目前虽然稀疏信号处理理论和方法都获得了长足发展，但是人们对信号结构性的挖掘和利用仍不够充分，尚在起步阶段，亟待建立更有效的信号结构性模型和测度，建立以此为基础的有效信号获取及高效复原算法体系，以及推动这些研究成果在相关应用领域的发展。

图2　自2000年以来WEB-OF-SCIENCE统计的美国、中国及德国等的关于稀疏信号处理的论文发表（第1行）和论文引用（第2行）情况Fig. 2　The Web-of-Science statistical results on published paper （the first row）and citation （the second row）of structural signal processing since 2000 for USA （first column），China （second column），and Germany （third column）

2　结构化信号感知问题的数学描述

其中表示数据获取噪声和模型误差等因素。利用Bayes公式得x的后验概率为：

其中为目标信号x的似然估计（Maximum Likelihood），它解释了数据y对x估计的贡献；Pr（x）表示x的先验信息，它解释了目标信号x的先验对参数估计的作用。尽管式（2）清楚地诠释了观测数据（data）和目标信号先验（prior）对重建x的作用，但在它提出后的100多年里先验项Pr（x）的作用并没有被充分挖掘利用，它仅用来抑制噪声和防止数据过拟合，或简单地约束估计参数的有效范围。直到最近随着结构化信号处理和深度学习研究的兴起，先验Pr（x）对观测体制和数据参数估计精度的作用才得到足够重视。目前已发展了一些信号结构性Pr（x）的描述方法，大致包括4类。

（1）独立同分布的稀疏模型

这类模型的发展历史最为久远、研究最为深刻、内容最为丰富。从范数测度的角度来讲，-logPr（x）通常取为lp（0≤p≤1）范数或非负函数φ（xi）=|xi|p［48-57］。如果目标信号x本身不是稀疏的，那么可以考虑该信号在某种变换域（例如小波变换、人工训练字典域［58］等）下是稀疏的。针对lp（0≤p≤1）范数诱导的稀疏性，目前发展了成熟的算法解决该类结构化信号的复原［48-57］，例如MP/ OMP/CoSaMP等贪婪算法、LASSO算法、基追踪算法、迭代加权算法等。从统计角度来讲，P（xi）不仅可以为Cauchy分布、Gaussian-Bernoulli分布、Laplace分布、加权Laplace分布、t-student等良好定义的概率分布；也可以是混合高斯分布（其中N（xi|0，s）表示零均值、s方差的高斯分布，r（s）表示某种预先定义的概率分布）、或由受限玻尔兹曼机（Restricted Boltzmann Machine，RBM）学习的分布P（xi）= Pr（xi|h）（其中h表示｛0，1｝N二进制隐藏向量）等。

（2）非交叠稀疏组

尽管上面的独立同分布的稀疏性及lp（0≤p≤1）范数等稀疏测度能很好地描述信号的结构性，并且在众多应用领域得到了广泛的应用，但是大多数实际问题中信号具有除了信号元素稀疏性之外更丰富的结构，这种结构性信息的利用将有助于提升信号获取和处理的性能。例如，很多微波遥感图像具有分区连续特性（Region-based smooth或Block-based smooth）；大多数雷达监测信号具有准周期特性，其时频谱具有良好的聚类现象；小波系数的树状结构等。针对此类结构性信号的研究也相对成熟，目前已发展了系统的理论、算法和应用体系，例如，基于模式的压缩感知理论（Model-CS理论）［59］，基于l1/lp（0≤p≤∞）混合范数的稀疏分组测度［60-72］，基于非局部梯度的Non-local TV信号模型和信号复原算法［73］，Group-LASSO算法和Group稀疏Bayesian信号复原算法［60-72］。

（3）相互交叠稀疏组

上述信号结构化模型属于浅层结构，它仅考虑了统计独立稀疏组的简单特性，没有考虑稀疏分组之间的依赖关系（如图3-图5从不同角度演示了不同的信号结构性）。考虑不同组之间的相关性属于深度学习的内容，目前发展了一些简单的方法，相关研究属于起步阶段。2009年Jacob等人［64］和2012年Obozinski和Bach等人［74］提出了含隐藏变量的互相

图3　范数诱导的稀疏表征方法的3维示意图。||x1，2||2+|x3|球表示无交叠的混合范数，第2排的3个图表示有交叠的混合范数球Fig. 3　Illustration of norm-inducing sparse measures in threedimensional case

图4　信号的多层结构性描述。第1行表示向量是稀疏的，第2行用黑色方框标出了该向量是具有分组稀疏性，第3行用红色方框进一步表示该向量具有“天蓝色-浅蓝色-深红色”特定模式的深层结构性Fig. 4　Hierarchal structural illustration. The first row corresponds to the i.i.d. sparse vector，and the second row for grouped sparse vector in red rectangle，and the third line for group mode with some certain structure

图5　结构化信号复原算法的研究体系，它主要包括针对具体应用建立合适的优化目标函数模型，充分利用数据和先验两种信息源。根据实际应用对精度和效率的需求，调整价格函数的数学形态（包括可分解性、光滑性、凸性等）等4个方面Fig. 5　The basic requirements on the efficient reconstruction algorithm of very-large-scale structural signals

交叠组的稀疏测度：

并且发展了有效的结构化信号重建理论和onepass算法；随后，2015年Shervashidze和Bach提出采用多任务学习（Multi-task learning）方法估计）的方法。除了采用范数或与其关联的概率分布作为信号结构性的测度外，也有其它描述方法。2012年Peleg等人采用限制玻尔兹曼学习机（Restricted Boltzmann Machine）描述具有一般信号的结构性［75］，Dremeau等人利用统计物理的平均场理论和变分Bayesian方法提出了一种更有效的结构化信号重建方法［76］等。

（4）基于机器学习的信号结构建模

值得说明的是上述前3类信号结构性测度需已知信号的结构性模型，例如，信号的稀疏变换域，或者稀疏组的结构（Probabilistic or deterministic graphic model），因此如何构造信号的结构性模型成为一个公开的挑战性研究课题。目前常用的策略包括3类：（1）使用多个经典的变换域构造超完备字典，（2）基于大量样本采用确定性或者统计性训练的方法构造元素独立［58，59］或具有结构［65，77，78］的超完备字典，（3）将区域分割或者聚类等方法引入算法复原过程，该方法无需训练样本，在信号重构过程中自适应引入信号结构型的度量。

除了上述4类模型外，我们要强调的是在许多实际应用中还有一类重要的问题需引起研究者的关注。在这类问题中目标信号本身不具备结构性，但它在某种非线性变换的情况下却具有良好的结构性。例如，森林的微波遥感图像类似于零均值的随机数，它本身没有结构性，但是通过方差或者其它度量变换下图像会变成典型的分段连续，呈现良好的结构性［1］。相信这类问题将会引起结构化信号领域的研究者的高度关注。

下面重点介绍式（2）的最大后验估计或者是模式分析：

式（4a）的等价表述方式为：

其中γ为正则化参数（用最优化或统计分析的语言）。如果Pr（x）取元素独立同分布的Laplace分布，那么此时优化问题式（4）变为大家熟知的l1范数正则化的稀疏优化问题。针对该问题，压缩感知理论上明确指出了先验和数据两重信息的融合对测量体制的影响，并给出了信号稀疏度（先验）、观测数据、以及测量方式之间的定量关系，这就是著名的约束等容（Restricted Isometric Property，RIP）定理（Candes-Romberg-Tao定理［16］）。下面给出作者2010年提出的广义RIP定义［79，80］：

上述定理是Candes-Romberg-Tao定理的推广，它适应于任意稀疏字典和测量矩阵。在这里我们要强调的是，尽管RIP在压缩感知和其它结构化信号感知中扮演着重要的角色，但判定某种测量方式是否满足RIP或其它类似特性却是一个公开的难题。除特殊情况外（例如，过于保守的相关性分析Coherence-based analysis［1，2］，高斯随机矩阵等特殊的测量方法等），目前可行的方式是采用蒙特卡洛方法计算Donoho-Tanner相转换曲线 （Phase-transition method［13，81］）。压缩感知理论自诞生以来，经过多年的发展其内涵和外延均得到了极大的发展。例如，2006年Raraniuk等人提出了基于模式的压缩感知方法yi=gi（＜ai，x＞）（i=1，2，…，M）的结构化信号感知问（Model-based CS）［59］，2010年Candes等人提出了低秩矩阵填充（Low-rank matrix completion）理论及算法［82］，2011年Duarte和Elad提出了结构化压缩感知理论和方法［3］等。近年来结构化信号的非线性感知成为信号处理领域的一个重要研究分支，例如，压缩相位复原（Compressive Phase Retrieval）问题［83，84］、1-bit压缩感知（one-bit compressive sensing，也称指数测量（Single-index measurement）［85，86］）问题［85-90］等。尤其是对压缩相位复原问题的研究较为深入，建立了与经典压缩感知理论相对应的系统理论和算法体系。2015年Thrampoulidis等人对非线性稀疏感知问题作了一个突破性的工作，理论上证明了非线性测量）（i=1，2，M）的结构化信号感知问题与某个线性测量（其中μ和σ是与非线性函数gi有关的已知参数）的鲁棒性广义LASSO问题minx］的解在统计平均意义上是等价的，该工作为研究结构化信号的非线性感知开辟了一条新思路［83］。最近，Brunton，Proctor以及Kutz等人采用通过结构化信号处理复原数据的非线性物理方程［91］。

3　大尺度结构化信号感知问题的信号复原 算法

信号复原算法是稀疏信号处理体系的核心组成部分，它是直接影响稀疏信号处理体系能否实用的关键。稀疏信号复原算法的设计主要从以下4个方面入手考虑［92-96］：（1）针对具体应用建立合适的优化目标函数模型，充分利用数据和先验两种信息源；（2）根据实际应用对精度和效率的需求，调整价格函数的数学形态（包括可分解性、光滑性、凸性等）；（3）结合价格函数具体的数学形态设计迭代策略，建立实现超线性收敛速度的算法；（4）针对具体应用实现算法的并行化。对应这4个组成部分，信号复原算法的评价体系包含4个方面：即目标函数模型是否充分挖掘了数据和先验两种信息源、目标函数的数学形态是否具有低复杂性、优化迭代策略是否超收敛以及算法是否可以并行化处理。

下面介绍两种信号复原的算法模型：最大后验估计（Maximum A Posteriori）和最大均值对数后验估计（Maximum Mean log Posteriori），它们的定义分别如下：

将式（10）代入式（8）和式（9）得到：

其中Lt（yt，x）=（yt-At（x））2/2，M是观测数据的总个数。

式（11）和式（12）的区别是前者不需要数据y的概率模型，而后者需要已知数据的概率模型，称之为统计优化问题（Stochastic Optimization）。特别地，如果数据y是统计均匀分布，那么式（11）和式（12）是等价的；从这个角度，式（11）是式（12）的一种特例。除非特殊情况（例如，A（x）=Ax且先验P（x）是高斯分布），式（11）和式（12）没有解析解，需采用迭代算法求解。如上所述，目前发展了大量信号复原算法求解问题式（11），例如匹配追踪算法、概率匹配追踪算法、压缩采样匹配追踪算法（CoSaMP）、迭代硬门限算法、迭代软门限算法、迭代加权算法、梯度投影算法、基追踪算法、Nesterov算法（或NESTA算法）、Split-Bregman迭代算法、亚梯度迭代算法方法等。这些方法均具有坚实优化理论作基础（例如，算法的收敛性、计算复杂性、精度等），但这些优化算法的每一步迭代需要遍历所有观测数据，同时又需要处理信号的所有维度，这导致了处理海量数据大尺度优化问题的主要技术瓶颈。由于被观测对象的结构性和观测数据的海量性和冗余性，大多数海量数据大尺度稀疏优化问题的数据在统计上是独立同分布的，海量数据存在严重的冗余，少部分数据甚至极少部分数据就足以反映数据集的统计规律。利用这个特性，在线学习的优化方法成为处理海量数据大尺度优化问题的一个重要工具，它的迭代策略是［97，98］：

其中μt表示更新步长，）分别表示Lt（yt，x）和logP（x）对x的梯度。针对问题式（11），迭代格式式（13）可用序列式或随机方式选取观测数据；针对问题式（12），数据yt需利用P（y）的统计模型生成。由式（13）可知，在线学习优化方法的核心思想是每步迭代处理一个或少数几个数据点，与批处理的优化算法相比大大缩减了内存开销；但也正是每次仅仅优化单个数据点造成的损失，收敛速度不可避免地会受到影响。然而如前所述，大尺度电磁成像（例如，多维度微波遥感）观测数据统计上独立同分布，并且这些海量数据呈现高度的冗余性，少部分数据甚至极少部分数据就足以反映整个数据集的统计规律。因此只要针对部分样本点运行随机优化步骤后，优化问题解的精度就呈现出稳定的趋势，这就是在线学习优化方法特别适合求解大尺度结构化信号感知问题的主要原因。与在线学习方法相对偶，有效求解大尺度优化问题的另一类随机优化方法是坐标下降（Randomized Coordinate Descent，简称RCD（在不同的文献中对其称呼不同，例如，信号处理领域称之为SPSA优化方法，医疗成像领域称之为Order-Set优化方法等；另外，该方法与变分Bayesian和Approximate Message Passing等方法有很大相似性，与交替迭代方法具有相同的思想））。RCD优化方法的迭代步骤就是固定其他维坐标，一次仅对选中的1维坐标或少数几个坐标进行优化求解。RCD优化方法具有重要的理论基础，它更新一次的计算复杂度仅为O（M），具有低的计算复杂性。RCD优化方法以简洁的操作流程和快速的实际收敛效果，成为处理海量数据大尺度稀疏优化问题的重要方法之一［99-100］。

为进一步提高算法性能，使其有效处理海量数据的大尺度稀疏优化问题，目前已经发展了一些非常有用的辅助技术。针对l1范数正则化的稀疏优化问题，可以采用价格函数的1阶泰勒级数展开结合软门限方法进行解析求解［50，93-95，98-106］，或采用Split技术结合软门限方法处理（例，交替迭代乘子法，ADMM［107］）。改善优化价格函数的强凸性也可有效加快算法的收敛速度，例如，增强拉格朗尔方法（Augmented Lagrangian Method），Bregman距离辅助方法。为增强价格函数的强凸性，在凸优化框架下考虑式（11）和式（12）：

其中ψ是连续光滑的强凸函数。从优化算法角度，信号复原算法的性能对迭代步长的选择特别敏感，主要表现在两个方面：（1）引入一些常规性的迭代步长选择机制，使算法具有超线性的收敛速度［1］。常用的方法是线性搜索，但是对于一些复杂的应用问题，线性搜索缺乏步长解析解，需依赖耗时的计算，需发展一些加速技术［50，93-95，98-106］；（2）Nesterov等加速技术能使目标函数在迭代初期急剧下降，但在迭代后期会进入震荡或缓慢下降阶段，为解决这个问题需采用一些warm restart技术［107，108］。结构化信号优化问题经常是非凸的，为了解决非凸性优化问题，Hazan等人提出了准凸性概念和局部Lipschitz，并在此基础上提出了归一化统计梯度方法，有效解决了非凸优化的伪解问题［103］。

在线学习优化和随机坐标优化这两种方法在求解高维大样本问题时简单、高效，各有特点和优势。在线学习优化方法主要利用大规模数据独立同分布的统计规律；而坐标优化主要利用目标信号结构化的特性，有复杂性较低的计算目标函数及其梯度的技巧。在线优化和坐标优化方法充分地利用了大尺度优化问题自身的特点，很好地满足了大尺度结构化信号感知问题的实际需求。

［1］李廉林，李芳. 稀疏信号处理讲义［M］. 北京大学内部讲义，2015.

Li Lian-lin and Li Fang. Lecture on Sparse Signal Processing （Preprint）［M］. Peking University，2015.

［2］Elad M. Sparse and redundant representation modeling-what next？［J］. IEEE Signal Processing Letters，2012，19（12）: 922-928.

［3］Duarte M F and Eldar Y C. Structured compressed sensing: from theory to applications［J］. IEEE Transactions on Signal Processing，2011，59（9）: 4053-4085.

［4］吴一戎. 稀疏微波成像理论、体制和方法研究，国家973项目申请书（项目首席科学家: 吴一戎，中国科学院电子学研究所），2010.

Wu Yi-rong. Sparse microwave imaging: theories，methods，and systems，The proposal submitted to the National Basic Research Program of China，Leading Scientist: Wu Yirong，Institute of Electronics，Chinese Academy of Sciences，2010.

［5］Candes E J and Tao T. Near-optimal signal recovery from random projections: universal encoding strategies？［J］. IEEE Transactions on Information Theory，2006，52（12）: 5406-5425.

［6］Donoho D L. Neighborly polytopes and sparse solutions of underdetermined linear equations［J］. Preprint，2005.

［7］Donoho D L. Compressed sensing［J］. IEEE Transactions on Information Theory，2006，52（4）: 1289-1306.

［8］Donoho D L. For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution［J］. Communications on Pure and Applied Mathematics，2006，59（7）: 797-829.

［9］Donoho D L and Elad M. Optimally sparse representation in general （nonorthogonal）dictionaries via l1minimization［J］. Proceedings of the National Academy of Sciences，2003，100（5）: 2197-2202.

［10］Donoho D L and Elad M. On the stability of the basis pursuit in the presence of noise［J］. Signal Processing，2006，86（3）: 511-532.

［11］Donoho D L，Elad M，and Temlyakov V N. Stable recovery of sparse overcomplete respresentations in the presence of noise［J］. IEEE Transactions on Information Theory，2006，52（1）: 6-18.

［12］Donoho D L and Jared T. Sparse nonnegative solution of underdetermined linear equations by linear programming［J］. Proceedings of the National Academy of Sciences，2005，102（27）: 9446-9451.

［13］Donoho D L and Tanner J. Precise undersampling theorems［J］. Proceedings of the IEEE，2010，98（6）: 913-924.

［14］Donoho D L and Tsaig Y. Fast solution of l1-norm minimization problems when the solution may be sparse［J］. IEEE Transactions on Information Theory，2008，54（11）: 4789-4812.

［15］Candes E J，Romberg J，and Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information［J］. IEEE Transactions on Information Theory，2006，52（2）: 489-509.

［16］Candès E J，Romberg J K，and Tao T. Stable signal recovery from incomplete and inaccurate measurements［J］. Communications on Pure and Applied Mathematics，2006，59（8）: 1207-1223.

［17］Candès E J and Tao T. Decoding by linear programming［J］. IEEE Transactions on Information Theory，2005，51（12）: 4203-4215.

［18］Prony R. Essai experimental et analytique sur les lois de la Dilatabilit_e des uideselastiques et sur celles de la Force expansive de la vapeur de l'eau et de la vapeur de l'alkool，a dierentes temperatures. J. de l' Ecole Polytechnique，Floreal et Prairial III，1795，1（2）: 24-76.

［19］Tarantola A. Inverse Problem Theory and Method for Model Parameter Estimation［M］. SIAM Press.

［20］Jaynes E. Probability Theory: The Logic of Science［M］. Cambridge University Press，2003.

［21］Carathéodory C. Über den Variabilitätsbereich der Koeffizienten von Potenzreihen，die gegebene Werte nicht annehmen［J］. Mathematische Annalen，1907，64（1）: 95-115.

［22］Carathéodory C. Über den variabilitätsbereich der fourier'schen konstanten von positiven harmonischen funktionen［J］. Rendiconti Del Circolo Matematico Di Palermo，1911，32（1）: 193-217.

［23］Beurling A. Sur les integrales de Fourier absolument convergentes et leur application a une transformation fonctionelle［C］. In Proc. Scandinavian Math. Congress，Helsinki，Finland，1938.

［24］Claerbout J F and Muir F. Robust modeling of erratic data［J］. Geophysics，1973，38（5）: 826-844.

［25］Taylor H，Banks S，and McCoy J. Deconvolution with the l1norm［J］. Geophysics，1979，44（1）: 39-52.

［26］Santosa F and Symes W W. Linear inversion of band-limited reflection seismograms［J］. SIAM Journal on Scientific and Statistical Computing，1986，7（4）: 1307-1330.

［27］Santosa F and Symes W. Inversion of impedance profile from band-limited data［C］. International Geoscience and Remote Sensing Symposium，1983.

［28］Tibshirani R. Regression shrinkage and selection via the Lasso［J］. Journal of the Royal Statistical Society, Series B，1996，58（1）: 267-288.

［29］Chen S，Donoho D，and Saunders M. Atomic decomposition by basis pursuit［J］. SIAM Journal on Scientific Computing，1998，20（1）: 33-61.

［30］Samadi S，Cetin M，and Masnadi-Shirazi M. Sparse representation-based synthetic aperture radar imaging［J］. IET Radar，Sonar & Navigation，2011，5（2）: 182-193.

［31］Soldovieri F，Solimene R，and Ahmad F. Sparse tomographic inverse scattering approach for through-thewall radar imaging［J］. IEEE Transactions on Instrumentation & Measurement，2012，61（12）: 3340-3350.

［32］Oliveri G，Rocca P，and Massa A. A bayesian-compressivesampling-based inversion for imaging sparse scatterers［J］. IEEE Transactions on Geoscience & Remote Sensing，2011，49（10）: 3993-4006.

［33］Desmal A and Bagci H. Shrinkage-thresholding enhanced Born iterative method for solving 2D inverse electromagnetic scattering problem［J］. IEEE Transactions on Antennas & Propagation，2014，62（7）: 3878-3884.

［34］Solimene R，Ahmad F，and Soldovieri F. A novel CSTSVD strategy to perform data reduction in linear inverse scattering problems［J］. IEEE Geoscience & Remote Sensing Letters，2012，9（5）: 881-885.

［35］Winters D W，Van Veen B D，and Hagness S C. A sparsity regularization approach to the electromagnetic inverse scattering problem.［J］. IEEE Transactions on Antennas & Propagation，2010，58（1）: 145-154.

［36］Huang Q，Qu L，Wu B，et al.. UWB through-wall imaging based on compressive sensing［J］. IEEE Transactions on Geoscience & Remote Sensing，2010，48（3）: 1408-1415.

［37］Yoon Y S and Amin M G. Through-the-wall radar imaging using compressive sensing along temporal frequency domain［C］. 2010 IEEE International Conference on Acoustics，Speech，and Signal Processing，2010: 2806-2809.

［38］Leigsnering M，Ahmad F，Amin M G，et al.. Compressive sensing based specular multipath exploitation for throughthe-wall radar imaging［C］. 2013 IEEE International Conference on Acoustics，Speech and Signal Processing（ICASSP），2013: 6004-6008.

［39］Zhu X X and Bamler R. Super resolving SAR tomography for multidimensional imaging of urban areas: compressive sensing-based TomoSAR inversion［J］. IEEE Signal Processing Magazine，2014，31（4）: 51-58.

［40］向寅. 压缩采样、稀疏约束成像及等效辐射源无相位逆散射［D］. ［博士论文］，中国科学院研究生院，2010.

Xiang Yin. Study of compressed sampling，sparse imaging its applications in phaseless inverse scattering［D］. ［Ph.D. dissertation］，University of Chinese Academy of Sciences，2010.

［41］张文吉. 电磁逆散射成像方法及压缩感知理论在成像中的应用［D］. ［博士论文］，中国科学院研究生院，2009.

Wenji Zhang，Study of fast methods of electromagnetic inverse scattering and compressive electromagnetic imaging［D］. ［Ph.D. dissertation］，University of Chinese Academy of Sciences，2009.

［42］刘艳丽. 基于抛物线方程的电波传播问题及电离层成像研究［D］. ［博士论文］，中国科学院研究生院，2009.

Yanli Liu，Study of parabolic equations based radio wave propagation and its applications in ionosphere tomography［D］. ［Ph.D. dissertation］，University of Chinese Academy of Sciences，2009.

［43］Xu G，Xing M D，Xia X G，et al.. Sparse regularization of interferometric phase and amplitude for InSAR image formation based on bayesian representation［J］. IEEE Transactions on Geoscience & Remote Sensing，2015，53（4）: 2123-2136.

［44］Zhang L，Qiao Z J，Xing M，et al.. High-resolution ISAR imaging with sparse stepped-frequency waveforms［J］. IEEE Transactions on Geoscience & Remote Sensing，2011，49（11）: 4630-4651.

［45］石光明，刘丹华，高大化，等. 压缩感知理论及其研究进展［J］.电子学报，2009，37（5）: 1070-1078.

Guangming Shi，Danhua Liu，Dahua Gao，et al.. Theory of compressive sensing and its recent progress，Recent progress on theory and compressive sensing［J］. Chinese Journal of Electronics，2009，37（5）: 1070-1078.

［46］Xu Z，Chang X，Xu F，et al.. L1/2regularization: a thresholding representation theory and a fast solver［J］. IEEE Transactions on Neural Networks & Learning Systems，2012，23（7）: 1013-1027.

［47］黄晓涛，杨俊刚，金添. 压缩感知雷达成像［M］. 北京: 科学出版社，2014.

Huang Xiao-tao，Yang Jun-gang，and Jin Tian. Compressed Radar Imaging［M］. Beijing: Science Press，2014.

［48］Mallat S and Zhang Z. Matching pursuit in a timefrequency dictionary［J］. IEEE Transactions on Signal Processing, 1993，41（12）: 3397-3415.

［49］Needell D and Tropp J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples［J］. Applied & Computational Harmonic Analysis，2008，26（12）: 93-100.

［50］Nesterov Y. Introductory Lectures on Convex Optimization: A Basic Course［M］. Kluwer Academic Publishers，2004.

［51］Wainwright M J. Structured regularizers for highdimensional problems: statistical and computational issues［J］. Social Science Electronic Publishing，2014，1（1）: 233-253.

［52］Donoho D and Tsaig Y. Fast solution of l1 norm minimization problems when thesolution may be sparse［J］.IEEE Transactions on Information Theory，2008，54（11）: 4789-4812.

［53］Chen S S，Donoho D L，and Saunders M A. Atomic decomposition by basis pursuit［J］. SIAM Review，2001，43（1）: 129-159.

［54］Koh K，Kim S J，and Boyd S. An interior-point method for large-scale l1-regularized logistic regression［J］. Journal of Machine Learning Research，2007，8（3）: 1519-1555.

［55］Shevade S K and Keerthi S S. A simple and efficient algorithm for gene selection using sparse logistic regression［J］. Bioinformatics，2003，19（17）: 2246-2253.

［56］Hui Z and Trevor H. Regularization and variable selection via the elastic net［J］. Journal of the Royal Statistical Society，2005，67（2）: 301-320.

［57］Candès E J，Wakin M B，and Boyd S P. Enhancing sparsity by reweighted l1minimization［J］. Journal of Fourier Analysis & Applications，2008，14: 877-905.

［58］Tosic I and Froccard P. Dictionary learning［J］. IEEE Signal Processing Magazine，2011: 27-38.

［59］Aharon M，Elad M，and Bruckstein A. K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation［J］. IEEE Transactions on Signal Processing，2006，54（11）: 4311-4322.

［60］Van den Berg E，Schmidt M，Friedlander M P，et al.. Group sparsity via linear-time projections［R］. Technical Report，University of British Columbia，2008，Technical Report Number TR-2008，2008.

［61］Friedman J，Hastie T，and Tibshirani R. A note on the group lasso and a sparse group lasso［J］. Preprint arXiv:1001:0736v1，2010.

［62］Huang J and Zhang T. The benefit of group sparsity［J］. Annals of Statistics，2009，38（4）: 1978-2004.

［63］Huang J，Zhang T，and Metaxas D. Learning with structured sparsity［J］. Journal of Machine Learning Research，2011，12（7）: 3371-3412.

［64］Jacob L and Obozinski G. Group lasso with overlaps and graph lasso［C］. Proceedings of the 26th International Conference on Machine Learning，2009.

［65］Jenatton R，Audibert J Y，and Bach F. Structured variable selection with sparsity-inducing norms［J］. Journal of Machine Learning Research，2011，12（10）: 2777-2824.

［66］Baraniuk R G，Cevher V，Duarte M F，et al.. Model-based compressive sensing［J］. IEEE Transactions on Information Theory，2010，56（4）: 1982-2001.

［67］He L and Carin L. Exploiting structure in wavelet-based bayesian compressive sensing［J］. IEEE Transactions on Signal Processing，2009，57（9）: 3488-3497.

［68］He L，Chen H，and Carin L. Tree-structured compressive sensing with variational bayesian analysis［J］. IEEE Signal Processing Letters，2010，17（3）: 233-236.

［69］Eldar Y C，Kuppinger P，and Bölcskei H. Block-sparse signals: uncertainty relations and efficient recovery［J］. IEEE Transactions on Signal Processing，2010，58（6）: 3042-3054.

［70］Yuan M and Lin Y. Model selection and estimation in regression with grouped variables［J］. Journal of the Royal Statistical Society，2006，68（1）: 49-67.

［71］Robert T，Michael S，Saharon R，et al.. Sparsity and smoothness via the fused lasso［J］. Journal of the Royal Statistical Society，2005，67（1）: 91-108.

［72］Amit Y，Fink M，Srebro N，et al.. Uncovering shared structures in multiclass classification［C］. Twenty-fourth International Conference on Machine Learning，2007: 17-24.

［73］Gilboa G and Osher S. Nonlocal operators with applications to image processing［J］. SIAM Journal on Multiscale Modeling & Simulation，2008，7（3）: 1005-1028.

［74］Bach F and Obozinski G. Structured sparsity through convex optimization［J］. Statistical Science，2011，27（4）: 450-468.

［75］Peleg T，Eldar Y C，and Elad M. Exploiting statistical dependencies in sparse representations for signal recovery［J］. IEEE Transactions on Signal Processing，2012，60（5）: 2286-2303.

［76］Dremeau A，Herzet C，and Daudet L. Boltzmann machine and mean-field approximation for structured sparse decompositions［J］. IEEE Transactions on Signal Processing，2012，60（7）: 3425-3438.

［77］Marlin B M and Murphy K P. Sparse Gaussian graphical models with unknown block structure［C］. ICML'09 Proceedings of the 26th International Conference on Machine Learning，2009: 705-712.

［78］Marlin B M，Schmidt M，and Murphy K P. Group sparse priors for covariance estimation［C］. Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence，2012: 383-392.

［79］Li L. Note on RIP-based co-sparse analysis［OL］. http://arxiv.org/abs/1202.2037.

［80］Pournaghi R and Wu X. Coded acquisition of high frame rate video［J］. IEEE Transactions on Image Processing，2013，23（12）: 5670-5682.

［81］Donoho D and Tanner J. Observed universality of phase transitions in high-dimensional geometry，with implications for modern data analysis and signal processing［J］. Philosophical Transactions A：Mathematical, Physical and Engineering Sciences，2009，367（1906）: 4273-4293.

［82］Candès E J and Recht B. Exact matrix completion via convex optimization［J］. Foundations of Computational Mathematics，2008，9（6）: 717-772.

［83］Thrampoulidis C，Abbasi E，and Hassibi B. The LASSO with non-linear measurements is equivalent to one with linear measurements［OL］. http://arxiv.org/abs/1506.02181.

［84］Candes E J and Plan Y. Matrix completion with noise［J］. Proceedings of the IEEE，2009，98（6）: 925-936.

［85］Hardle W，Hall P，and Ichimura H. Optimal smoothing in single-index models［J］. The Annals of Statistics，1993，21（1）: 157-178.

［86］Hristache M and Spokoiny V. Direct estimation of theindex coefficient in a single-index model［J］. The Annals of Statistics，2001，29（3）: 595-623.

［87］Gopi S，Netrapalli P，Jain P，et al.. One-bit compressed sensing: provable support and vector recovery［C］. In International Conference on Machine Learning，2013.

［88］Jacques L，Laska J，Boufounos P，et al.. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors［J］. arXiv:1104.3160，2011.

［89］Plan Y and Vershynin R. One-bit compressed sensing by linear programming［J］. Communications on Pure & Applied Mathematics，2013，66（8）: 1275-1297.

［90］Plan Y and Vershynin R. Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach［J］. IEEE Transactions on Information Theory，2013，59（1）: 482-494.

［91］Bahmani S and Romberg J. Efficient compressive phase retrieval with constrained sensing vectors. arXiv: 1507. 08254v1，2015.

［92］Cevher V，Becker S，and Schmidt M. Convex optimization for big data: Scalable，randomized，and Parallel algorithms for big data analytics［J］. IEEE Signal Processing Magazine，2014，31（5）: 32-43.

［93］Slavakis K，Giannakis G B，and Mateos G. Modeling and Optimization for Big Data Analytics: （Statistical）learning tools for our era of data deluge［J］. IEEE Signal Processing Magazine，2014，31（5）: 18-31.

［94］Yuan G X，Chang K W，Hsieh C J，et al.. A comparison of optimization methods and software for large-scale L1-regularized linear classification［J］. Journal of Machine Learning Research，2010，11（2）: 3183-3234.

［95］Fercoq O，Qu Z，Richtarik P，et al.. Fast distributed coordinate descent for non-strongly convex losses［OL］. http://arxiv.org/abs/1405.5300.

［96］Bertsekas D P and Tsitsiklis J N. Parallel and Distributed Computation: Numerical Methods［M］. Prentice Hall，1989.

［97］Nemirovski A，Juditsky A，Lan G，et al.. Robust stochastic approximation approach to stochastic programming［J］. SIAM Journal on Optimization，2009，19（4）: 1574-1609.

［98］Kushner H and Yin G. Stochastic Approximation Algorithms and Applications［M］. New York: Springer，1997.

［99］Nesterov Y. Efficiency of coordinate descent methods on huge-scale optimization problems［J］. SIAM Journal on Optimization, 2012，22（2）: 341-362.

［100］Richtárik P and Taká M. Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function［J］. Mathematical Programming，2014，144（1）: 1-38.

［101］Nesterov Y. Gradient methods for minimizing composite objective function［OL］. http://eonpapers.repec.org/paper/ corlouvco/2007076.htm.

［102］Fercoq O and Richtarik P. Accelerated，parallel and proximal coordinate descent［OL］. http://arXiv:1312.5799.

［103］Hazan E，Levy K，and Shalev-Shwartz S. Beyond convexity: stochastic quasi convex optimization［OL］. http://arxiv.org/abs/1507.02030.

［104］Qu Z，Richtarik P，and Zhang T. Randomized dual coordinate ascent with arbitrary sampling［OL］. http://arxiv.org/abs/1411.5873.

［105］Hardt M，Recht B，and Singer Y. Train faster，generalize better: stability of stochastic gradient descent［OL］. http://arxiv.org/abs/1509.01240.

［106］Johnson R and Zhang T. Accelerating stochastic gradient descent using predictive variance reduction［C］. Advances in Neural Information Processing Systems，2013，26: 315-323.

［107］Boyd S，Parikh N，Chu E，et al.. Distributed optimization and statistical learning via the alternating direction method of multipliers［J］. Foundations and Trends in Machine Learning，2011，3（1）: 1-122.

［108］Su W，Boyd S，and Candes E J. A differential equation for modeling nesterov's accelerated gradient method: theory and insights［OL］. http://arxiv.org/abs/1503.01243.

李廉林（1980-），男，山西平遥人，2006年获得中科院电子所博士学位，现任北京大学信息科学技术学院特聘研究员，博士生导师，研究方向为超分辨电磁成像、电磁大数据处理以及超宽带雷达系统。E-mail: lianlin.li@pku.edu.cn

周小阳（1979-），男，博士，东南大学毫米波国家重点实验室副教授，研究方向为计算电磁学高频近似方法与雷达信号处理。

E-mail: xyzhou@seu.edu.cn

崔铁军（1965-），男，东南大学毫米波国家重点实验室教授、博士生导师，目前主要研究方向为计算电磁学及其快速算法、新型人工电磁材料的理论、实验及应用研究、目标特性与目标识别、大型军用目标的精确电磁仿真等。

E-mail: tjcui@seu.edu.cn

Perspectives on Theories and Methods of Structural Signal Processing

Li Lian-lin①Zhou Xiao-yang②Cui Tie-jun②

①（School of Electronics Engineering and Computer Science，Peking University，Beijng 100871，China）
②（State Key Laboratory of Millimeter Waves，Southeast University，Nanjing 210096，China）

Over the past decade structural signal processing is an emerging field，which gained researchers' intensive attentions in various areas including the applied mathematics，physics，information theory，signal processing，and so on. The structural signal processing is a paradigm of making the revolutionary refresh on theories and methods in the nutshell of traditional signal processing based on the well-known Nyquist-Shannon theory，which will render us a new perspective on the adaptive data acquisition in the task-driven manner. Basically，the structural signal processing includes four research contents （MAMA）: （a）Measures for the structural signal，（b）Algorithms for reconstructing the structural signal at the low-complexity computational cost，（c）Methods for smart data acquisition at the low hardware cost and system complexity，and （d）Applications of structural signal processing in applied fields. This paper reviews on the recent progress on the theory and algorithms for structural signal processing，which will provides hopefully useful guide for readers of interest.

Structural signal processing； Sparse signal processing； Task-driven signal processing； Nyquist-Shannon theory

The National Natural Science Foundation of China （61471006）

TN911.7

A

2095-283X（2015）-05-0491-12 DOI：10.12000/JR15111

李廉林，周小阳，崔铁军. 结构化信号处理理论和方法的研究进展［J］. 雷达学报，2015，4（5）: 491-502.

10.12000/JR15111.

Reference format：Li Lian-lin，Zhou Xiao-yang，and Cui Tie-jun. Perspectives on theories and methods of structural signal processing［J］. Journal of Radars，2015，4（5）: 491-502. DOI: 10.12000/JR15111.

2015-10-08；改回日期：2015-11-08

李廉林lianlin.li@pku.edu.cn

国家自然科学基金（61471006）