《应用数学和信号处理相遇_陈刚》由会员分享，可在线阅读，更多相关《应用数学和信号处理相遇_陈刚（16页珍藏版）》请在金锄头文库上搜索。
1、* 这是经 St phane Mallat同意的其在 1998年国际数学家大会上的专题报告的中译稿 .译文 1999 年 2 月 25 日收到 . 1 浙江大学高等数学研究所 . 2 复旦大学中法应用数学中心 . 3 香港理工大学电子与资讯工程学系. 高校应用数学学报 第 14卷 A辑第 3 期 Appl. Math. JCU Vol. 14 Ser. A No. 3 应用数学和信号处理相遇* St phane Mallat著 陈 刚 1 张 2 池哲儒3 译 1 超越 Fourier变换 Fourier变换方法曾长时间地统治了信号处理的领域 ,留给新的、有挑战性的数学工具 的只是不大的一点空
2、间.七十年代以前 ,所考虑的大多数信号都是语音信号或其它声音信 号 ,它们往往被认为是一个高斯过程 .相应地 ,在几乎所有的过程中线性算法都被认为是最 优的.因为是基于平稳性的假设 ,所以信号处理方法被严格地限制在一类卷积运算 Fourier变换中. 八十年代以来 ,随着图像处理研究的发展这种情况发生了彻底的改变.一般情况下 ,图 像信号很难用高斯过程来进行刻划.并且图像中的一些突变结构例如边缘信息远比图像的 平稳性重要.于是忽然间不可避免地涌现出了各种各样的非线性算法 ,从而也打开了信号处 理通往现代数学的大门 .除了传统的应用如信号传输、编码和信号恢复之外 ,信号处理也进 入了信息分析的领
3、域 ,语音理解和计算机视觉是其中的两大主要分支.信号处理和应用数学 这种带有火花的相互碰撞也产生了许多新的数学问题. 对于信号处理和信息处理来说 ,为信号 (函数 )、处理方法 (过程 )和各种运算 (算子 )构造 相应的稀疏表示式 ( sparse representations)是一个首要问题.一个稀疏表示式可以用特征化 的较少的几个参数近似地表示信号 ,这些参数是从一组扩张的基或者一本冗长的“字典”中 获得的.在稀疏表示的基础上 , (关于信号处理的 )复杂的非线性算法常常可以被简化和加 速.稀疏表示同时也是处理很多数学问题的一个强有力的工具 .在 1990 年的国际数学家大会 上 ,
4、Coifman和 Meyer从调和分析的观点对此进行了分析;随后 ,在 1994 年的国际数学家大 会上 , Daubechies和 Donoho又从数值分析和统计应用中紧支小波基的角度对稀疏表示式 进行了解释.在共同研究数据表示技术的过程中 ,信号处理成为一种促进数学和工程界的重 新交流与结合的推动力量.信号压缩、噪声滤波和随机模拟的各种应用导致我们从新的角度 去研究逼近论、调和分析、算子理论、概率论和统计等数学分支并获得新的成果. 2 稀疏表示式 稀疏表示式已经能够直接应用于数据压缩 .但对于处理海量的数据信号而言 ,我们还需 要降低分类和识别的复杂性 .本节的叙述从逼近论开始 ,然后逐步
5、把讨论的内容转移到信号 压缩方面. 2. 1 图像模型 Beyes认为 ,一个信号 f (x )可以被看作是某个过程 F( x )的一个样本函数 (原文为 real- ization) ,其误差的度量期望值与 F的概率分布有关 .事实上自然界的图像并不是一个高斯 过程.至今还没有一个统计模型可以完全包容兼有边缘和各种纹理信息的复杂场景 ,图 1( a) 就是一个很典型的例子.这促使我们选择一个简单而实用的决定性模型: 把一个信号看作 L 2 0, 1 d 中某个子集 S中的一个函数 f (x ) ,但是我们没有任何关于这个子集 S的概率分 布的先验知识.接下来 ,对一个具体的过程 ,我们会试图
6、极小化 S中的信号对此具体过程的 误差 ,这个方法称为 minimax(极小极大 )框架 .在这样的模型中用 N 个采样点去离散一个 信号 f (x )并不困难 ,因为在本质上就是将这个信号投影到一个 N 维的子空间上去 . 很 大一类图像 ,包括图 1( a) ,都具有有界的全变差. f ( x )在 0, 1的全变差被定义为 f (x )的变化率的振幅之和 f TV=| f (x )| dx t. 如果 H 1( K t)是其边界 Kt的一维 Hausdorff测度 ,那么 f TV= + - H1( Kt)dt.( 1) 我们把有界变差与有界振幅合起来得到一个图像模型: SBV=f: f
7、 TV= | f (x )| dx C, f =sup x0, 12| f (x )| C . ( 2) 这些图像具有典型的水平集和有限长度的“轮廓”.这个模型虽然简单 ,但已经足够用来体现 信号表示的核心思想以及说明其困难所在.更特别的一类图像 ,比如具有同类纹理的图像 , 可能用稀疏表示下的 Markov 随机域来表示更合适一些 .有关的内容在本文的第四节中介 绍. 2. 2 稀疏表示式和逼近论 设 f L 2 0, 1d在某个正交基B = g mm N下的展开式为 f = + m= 0f ,g mgm, 通过截断上述表达式可以获得 f 的一个稀疏表示式 .注意到研究某个函数在一组基下的稀
8、 351 第 3期St phane Mallat: 应用数学和信号处理相遇 疏表示也是逼近论中的一个中心课题 .在此我们仅简单介绍采用非线性逼近的动机 ,更完整 的叙述可以参见文献 13. 设 VM是B中 M个向量 g1, g2, ,gM张成的子空间 ,则对 f 用 M个内积f ,gm的线 性逼近就是 f 在空间 VM上的正交投影: fM= PVMf = M- 1 m= 0f ,g mgm. 这样 ,在某个信号集合 S上的极大逼近误差就是 X l( S, M) =sup f S f - f M 2 =sup f S + m= M| f ,g m| 2. 如果随着 M的增加 1X l( S, M
9、)衰减得非常快或者说随着 m 的增加| f ,gm| 衰减得很快的 话 ,那么上式的逼近是十分有效的 ,而这依赖于当 S确定以后对 B 的选择 .例如 ,一致正则 函数就可以被 L 2 0, 1中对应于 Fourier基 e i2 mx m Z的 M个低频向量很好地逼近.如果 S 被包含在周期为 1 的函数组成的 Sobolev空间 W s 0, 1中的一个球中 ,那么根据其 Fourier 系数在高频的衰减速度可以推出 Xl( S, M)= O( M - 2s) (参见 13) .有界变差函数可能会不 连续 ,所以用 Fourier基逼近的效果可能会不好.利用 Kolmogorov引入的 M
10、- Width的概 念 ,可以证明对于有界变差函数组成的一个球 SBV,在一组基B下最快的误差衰减速度是 Xl( SBV, M) M - 1 (参见 13). 1此处原文为减少 ( decrease),疑为作者笔误.译者注 . 为了改进以上的逼近效果 ,可以建立一个更为自适应的表示: 把 f 投影到 M个基向量 上 ,而这个 M个基向量是依据 f 来选择的 fM= m IMf ,g mgm.( 3) 因为 f - fM 2= m IM | f ,g m| 2,所以可以选择 M个向量使得系数| f , gm| 具有最大 振幅来得到最优逼近.逼近的结果依赖于 2M个参数: 其中的 M 个是 IM中
11、的向量 ,而另外 M个是内积 f , gmm IM.我们把这 M个内积按递减排序 (即当 k 1 时 ,| ck | | c k+ 1| )并记 为 ck= f ,gmk.这时非线性逼近的误差是: f - fM 2 = + k= M- 1| c k| 2 , XM( S, M) = sup f S f - f M 2. 误差值与| ck| 的衰减速度有关.对于上述的基B,我们定义一个半径为 C的 wI P 球 Swlp= f: | ck|= | f ,gmk| Ck- 1/p.( 4) 我 们很容易验证: 存在某个 p 0使得 S Swlp成立的充要条件是 X n( S, M ) = O( M
12、 1- 2 p ).对于非线性逼近来说 ,主要的困难是寻找最小的 p和相应的基B满足 S Swlp. 这样得到的一组基被称为 S的一个最优非线性逼近基.无条件基就是最优基的一个例子. Banach子空间 B L 2 0, 1d中的一组正交基B被称为无条件基 ,如果存在正常数 A, 对于任意的符号序列 sm - 1, 1和 f B,有 + m= 0s mf ,gmgm B A + m= 0f ,g mgm B. 352 高 校 应 用 数 学 学 报第 14 卷 A辑 注意到 f B 2l )级分辨率下 ,小波 jj ,n正交于所有的 q次多项式.可以 通过伸缩和平移“母小波”j来生成支集在 (
13、 0, 1)上的小波族 jj, n jj, n(t) =2 jj( 2jt - n) . 并且可以通过某些方法 ,使边界小波 2的支集落入 0, 1. 2靠边界的小波被称为边界小波 (Boundary wavelets) ,译者注. 一个函数 (信号 ) f 用 M层小波 (M= 2 J 2 j )和尺度函数去线性逼近的过程是保留所有 2 j 0,对所有支集包含在 a,b中的非边界小波 jj,n,都有 | f ,jj,n| A2 - (T + 1/2) j . 在 Lipschitz系数 T 较大的区域 ,当分辨率 2 j 增加时| f ,jj, n| 衰减得非常快;当 0 T 0,极大逼近误
14、差并没有随着 M的增加而趋向于 0. 非线性的逼近比线性逼近更为有效是因为它保留了奇异点附近的小波系数 ,并且 ( 1)式 354 高 校 应 用 数 学 学 报第 14 卷 A辑 说明“图像边缘”的长度是有限的 .更精确地说 ,可以证明 SBV被包含在一个 wI 1球中 ,并且逼 近误差 Xn ( S BV, M) = O( M- 1) .对图像而言 ,小波自适应网格逼近比均匀逼近的效果好出许 多 ,没有其它一种正交基的逼近阶可以超过正交小波基. 2. 4 信号压缩 在有带宽限制的信道 (例如 Internet)中对海量数据的信号进行经济地存储和快速的传 输是信号压缩的主要应用领域.提高编码
15、 (压缩 )效率 ,也就是用尽可能少的位 ( bit)数表示 一个信号需要给出信号的稀疏表示式 .为了满足在语音和图像压缩中的需要 ,信号处理领域 的工程师们没有等数学中非线性逼近理论的成熟就开始了小波基的应用. 1986 年有了第一 个小波图像编码器 34 ,那时在数学领域中对于小波正交基的研究还没有真正开始.所谓的 快速正交小波变换实质上采用的是一个被称为“滤波器组” ( Filter Bank)的算法 .这个算法 最 初被用在复路信号 (利用一个信道传输多路信号 )的处理上 7.文献 33首次将 Filter Bank的理论引入到信号处理中 ,但在后来的文献 19中才真正将正交小波基与之
16、相联系. 虽然数学家们姗姗来迟 ,但在分析图象编码器的工作机理方面确实需要最新的逼近论成果 , 这样一来也为该领域的潜在发展开辟了众多新的方向. S中的信号在 N 级分辨率上被离散和逼近 ,则意味着该离散信号属于一个 N 维空间. 信号 f 在正交基B = g m0 m /2f ,g mgm. 355 第 3期St phane Mallat: 应用数学和信号处理相遇 因为当| x| p,其量化失真为 d ( S, R ) = O( R 1- 2/q ). 奇妙的是 ,当采用的是使 S的非线性逼近最优的基B时 , d( S, R)的衰减率也同时达到 最快 ,因为此时选择的是满足 S Swlp的最小的指数 p.特别是 ,对于有界变差图像来说 ,小 波基是最优的并且极小指数为
