首页 >> 数学 >> 计算机科学 >> 文章

不确定性原理系列全篇

到二十世纪末,人们对「信号」这个词的理解已经发生了微妙的变化。如果在二十世纪上半叶的时候提到一个信号,人们还倾向于将它理解为一个连续的函数。而到下半叶,信号已经越来越多地对应于一个离散的数组。毫无疑问,这是电子计算机革命的后果。

在这样的情形下,「不确定性原理」也有了新的形式。在连续情形下,我们可以讨论一个信号是否集中在某个区域内。而在离散情形下,重要的问题变成了信号是否集中在某些离散的位置上,而在其余位置上是零。数学家给出了这样有趣的定理:


一个长度为 N 的离散信号中有 a 个非零数值,而它的傅立叶变换中有 b 个非零数值,那么 a+b ≥ 2√N。

也就是说一个信号和它的傅立叶变换中的非零元素不能都太少。毫无疑问,这也是某种新形式的「不确定性原理」。

在上面的定理中,如果已知 N 是素数,那么我们甚至还有强得多的结论(它是 N. Chebotarev 在 1926 年证明的一个定理的自然推论):


一个长度为素数 N 的离散信号中有 a 个非零数值,而它的傅立叶变换中有 b 个非零数值,那么 a+b > N。

不幸的是这里「素数」的条件是必须的。对于非素数来说,第二条命题很容易找到反例,这时第一条命题已经是能够达到的最好结果了。

这些定理有什么用呢?如果它仅仅是能用来说明某些事情做不到,就像它字面意思所反映出的那样,那它的用处当然相对有限。可是——这无疑是辩证法的一个好例证——这样一系列宣称「不确定」的定理,事实上是能够用来推出某些「确定」的事实的。

设想这样一种情况:假定我们知道一个信号总长度为 N,已知其中有很大一部分值是零,但是不知道是哪一部分(这是很常见的情形,大多数信号都是如此),于此同时,我们测量出了这个信号在频域空间中的 K 个频率值,但是 K<N (也就是我们的测量由于某些原因并不完整,漏掉了一部分频域信息)。有没有可能把这个信号还原出来呢?

按照传统的信号处理理论,这是不可能的,因为正如前面所说的那样,频域空间和原本的时空域相比,信息量是一样多的,所以要还原出全部信号,必须知道全部的频域信息,就象是要解出多少个未知数就需要多少个方程一样。如果只知道一部分频域信息,就像是只知道 K 个方程,却要解出 N 个未知数来,任何一个学过初等代数的人都知道,既然 K<N,解一定是不唯一的。

但是借助不确定性原理,却正可以做到这一点!原因是我们关于原信号有一个「很多位置是零」的假设。那么,假如有两个不同的信号碰巧具有相同的 K 个频率值,那么这两个信号的差的傅立叶变换在这 K 个频率位置上就是零。另一方面,因为两个不同的信号在原本的时空域都有很多值是零,它们的差必然在时空域也包含很多零。不确定性原理(一个函数不能在频域和时空域都包含很多零)告诉我们,这是不可能的。于是,原信号事实上是唯一确定的!

这当然是一个非常违反直觉的结论。它说明在特定的情况下,我们可以用较少的方程解出较多的未知数来。这件事情在应用上极为重要。一个简单的例子是医学核磁共振技术(很多家里有重病患者的朋友应该都听说过这种技术)。核磁共振成像本质上就是采集身体图像的频域信息来还原空间信息。由于采集成本很高,所以核磁共振成像很昂贵,也很消耗资源。但是上述推理说明,事实上核磁共振可以只采集一少部分频域信息(这样成本更低速度也更快),就能完好还原出全部身体图像来,这在医学上的价值是不可估量的。

在今天,类似的思想已经被应用到极多不同领域,从医学上的核磁共振和 X 光断层扫描到石油勘测和卫星遥感。简而言之:不确定性可以让测量的成本更低效果更好,虽然这听起来很自相矛盾。

糟糕的是,本篇开头所描述的那个不确定性定理还不够强,所能带来的对频域测量的节省程度还不够大。但是数学上它又是不可改进的。这一僵局在本世纪初被打破了。E. Candès 和陶哲轩等人证明了一系列新的不确定性原理,大大提高了不等式的强度,付出的代价是……随机性。他们的定理可以粗略叙述为:


一个长度为 N 的离散信号中有 a 个非零数值,而它的傅立叶变换中有 b 个非零数值,那么 a+b 以极大概率不小于 N/√(log N) 乘以一个常数。

这里的「极大概率」并不是一个生活用语,而是一个关于具体概率的精确的数学描述。换言之,虽然在最倒霉的情况下不确定性可以比较小,但是这种情况很罕见。一般来说,不确定性总是很大。于是可以带来的测量上的节约也很大。

这当然也是一种「不确定性原理」,而且因为引入了随机性,所以在某种意义上来说比原先的定理更「不确定」。在他们的工作的基础上,一种被称为「压缩感知」的技术在最近的五六年内如火如荼地发展起来,已经成为涵盖信号处理、信息提取、医学成像等等多个工程领域的最重要的新兴工程技术之一。

不过,这些后续的发展估计是远远超出海森堡的本意了。

(完)

0
为您推荐

41 Responses to “不确定性原理的前世今生 · 数学篇(完)”

  1. 猛犸说道:

    抢个沙发先!

    这个系列真赞!

  2. laoma说道:

    我原来以为CT要解很多方程呢

  3. diesirae说道:

    K<N也能解出方程来这个太nb了……

  4. 大兔子说道:

    很好的文章。不过K<N解信号的问题还没有听明白:假定频谱上除K之外,N-K个信号中有极少的非零值,如此的少以至于这些多出的非零值并没有破坏“信号大多数为零”这一结论,那么多出的非零值如何被枪毙掉呢,他们携带的信息会不重要吗

    • 木遥说道:

      这问题我也没看明白不好意思……

    • fkkf说道:

      我的理解是这里求到的信号只是极大概率接近原信号。毕竟这里是以极少的信息还原信号,要想没有误差的精确解,还是需要N个信号才行。

      • 大兔子说道:

        有道理,这里面应该是有对信号的预先判断,如“大多数都是零”之类。而这种信号缺失应该也是常态,我们拍照片也是这样吧,除非镜头和底片非常大,不然频谱肯定覆盖不全的。

  5. Hal说道:

    Compressed Sensing
    压缩感知...还是忠于英文吧

  6. rustic说道:

    呃……文科生表示(三)和(四)看不懂了,掩面而过

  7. woniu说道:

    这样的文章真的很好,希望以后都一些。

  8. zmn0079说道:

    越来越看不懂了
    文科生压力很大……

  9. Achilles Wong说道:

    离散傅立叶变化,z变换 在数字电路中用得比较多

  10. 稀饭火锅说道:

    可以这样去理解,假定有一个长度为N的时域信号y,其傅里叶变换为Y,显然从信息量的完备性来讲,Y的采样值也应该是N才能恢复y,但如果y的许多分量都是0(稀疏性约束),则有可能用K<N个的频域采样值去恢复y。
    对此可以有一个粗略的说明,存在一个长度为N的时域信号y0(y!=y0),其傅里叶变换为Y0,Y和Y0在所采样的K个采样点上的值有可能是一样的。换句话讲,利用K<N个频域采样值去重构原始信号所得到的解是不唯一的。不难看出,如果K的数值越小,就越不唯一,随着K的值的增长,重构的解逐渐趋近于唯一,充分条件是K=N,问题是K=N是否是一个必要条件?
    E. Candès 和陶哲轩的工作实际上是告诉我们答案是否定的,K可以小于N,并且他们给出了一个精确的关于K的取值,这个值和原始信号长度和稀疏度(非零点的个数)有关。这意味着,获知K个数据就可以重构N维信号,信号被压缩了,而且在理论上是无损的压缩!当然天下没有免费的午餐,这样的压缩所付出的代价是什么呢?首先这种重构是在极大概率意义下实现的,稳定性有所丧失;其次,重构算法的复杂度增加。
    最后给出一个粗略的证明,因为Y与Y0在K个采样点上有相同的数值,则Y-Y0在频域上都是0,由不确定性原理可知,y-y0在时域上必然有大量的非零值,这意味着y!=y0,则y是唯一的。

    • ligand说道:

      谢谢。你的补充解释,我貌似看懂了。还是挺通俗科普的

    • sleeeper说道:

      你结尾的证明证错了。。
      “y-y0在时域上必然有大量的非零值,这意味着y!=y0”
      y和y0不相同,那岂不是和假设一致了?我们要证的是y=y0,即频域上K个点确定,则时域信号唯一。

      证明方法文中提到,但表述得不太清楚:“另一方面,因为两个不同的信号在原本的时空域都有很多值是零,它们的差必然在时空域也包含很多零。”
      为什么y0在时域也有很多值是零?
      事实上,y0在时域也有很多值是零是我们要设定一个约束条件。在压缩感知的信号重建中,也必须设立这样一个关键条件——重建的信号是最稀疏的解(0范数或1范数最小化)。也就是我们找不到另一个同样稀疏或更稀疏的信号,它在频域有与原信号相同的K个值。去掉稀疏的限制,则不成立。

  11. Sheldon说道:

    没有公式,有点儿晕了

  12. xoox说道:

    要是我认为构造两个长度都为N的信号,其中只有一个点不一样,而采样的K个值并没有覆盖这个点,那怎么能保证解是唯一的呢?

  13. 稀饭火锅说道:

    所以只能保证使以极大概率的唯一重构

  14. 1号楼说道:

    那段因为零值不能太多,所以信号被唯一确定没太看懂。。能再解释一下么

  15. 玉成说道:

    和图像压缩算法看来有点关系

  16. HH说道:

    如果只知道一部分频域信息,就像是只知道 K 个方程,却要解出 N 个未知数来,任何一个学过初等代数的人都知道,既然 K<N,解一定是不唯一的。

    这个是错误的,比如x^2+y^2=0,可以解出唯一解。

    • 老草说道:

      “这个是错误的,比如x^2+y^2=0,可以解出唯一解。”实数域上的唯一解,复数域上无穷多解

  17. 王茜莹说道:

    可以这样去理解,假定有一个长度为N的时域信号y,其傅里叶变换为Y,显然从信息量的完备性来讲,Y的采样值也应该是N才能恢复y,但如果y的许多分量都是0(稀疏性约束),则有可能用K<N个的频域采样值去恢复y。
    对此可以有一个粗略的说明,存在一个长度为N的时域信号y0(y!=y0),其傅里叶变换为Y0,Y和Y0在所采样的K个采样点上的值有可能是一样的。换句话讲,利用K<N个频域采样值去重构原始信号所得到的解是不唯一的。不难看出,如果K的数值越小,就越不唯一,随着K的值的增长,重构的解逐渐趋近于唯一,充分条件是K=N,问题是K=N是否是一个必要条件?
    E. Candès 和陶哲轩的工作实际上是告诉我们答案是否定的,K可以小于N,并且他们给出了一个精确的关于K的取值,这个值和原始信号长度和稀疏度(非零点的个数)有关。这意味着,获知K个数据就可以重构N维信号,信号被压缩了,而且在理论上是无损的压缩!当然天下没有免费的午餐,这样的压缩所付出的代价是什么呢?首先这种重构是在极大概率意义下实现的,稳定性有所丧失;其次,重构算法的复杂度增加。
    最后给出一个粗略的证明,因为Y与Y0在K个采样点上有相同的数值,则Y-Y0在频域上都是0,由不确定性原理可知,y-y0在时域上必然有大量的非零值,这意味着y!=y0,则y是唯一的。

  18. yexiaoya说道:

    在信号处理里面,更多的相关的是 那奎斯特采样定理,或者上采样方法。当然也存在频谱混叠的分析。但一般不会延伸到 不确定性 这么远。

  19. 白毛驴说道:

    不确定是太绝对了,相对而言还是确定的,
    这就是绝对相对论的有界有边,只是体内点的位置有很多个。

  20. shirleybae说道:

    文章中说“一个长度为 N 的离散信号中有 a 个非零数值,而它的傅立叶变换中有 b 个非零数值,那么 a+b ≥ 2√N。”
    这句话不是很理解,这里的傅里叶变换指的是离散傅里叶变换还是傅里叶变换?如果是傅里叶变换,那该离散信号的傅里叶变换肯定是连续的,又怎么会在变换后得到b个非零数值?如果是离散傅里叶变换,那么如果a很小,且这a个非零数值之间的距离很大,那对这种信号进行离散傅里叶变换b是不是也很小?又怎么会得到a+b大于N的结论呢?
    是不是说采样率与稀疏度也有关系呢?时域采样率越低信号稀疏度越小?离散傅里叶变换不了解。。。得回去查资料了。。希望有人帮我解答这个疑问呀

  21. XQX说道:

    ”假如有两个不同的信号碰巧具有相同的 K 个频率值,那么这两个信号的差的傅立叶变换在这 K 个频率位置上就是零“?两个信号虽然频率不同,但幅度可以不同吗?频率域的值不是幅度值吗?

  22. 杜阿凡说道:

    基本上就是信号与系统+随机信号原理+大学物理电磁场部分的浅显版本了,比老师讲的有趣多了,但总觉得深度有所不够。

  23. ZKL说道:

    原信号压缩处理是线性代数概念,引入了随机概念不能说成“更不准”,而是懂行的人士找出信号信息本身具有随机性一面,仅是过去没被发现而巳。比如传统的DOE正交试验数据必须用方差分析,后北大以张里千(非参数统计专家)为首学者发现,完全试验才适用方差分析,部分正交试验属非参数统计范畴。(也类似线性代数未知数多于方程组。)所以中国特色正交最优化法,用极差、趋势图和多轮正交试验逼出最优参数组合,跳过了方差分析。
    陶神童交叉学科的洞察力,来自其数学基础“宽”,专长水平“深”。

  24. sysy说道:

    写的很好!不错哦!

  25. 王康宁说道:

    这个系列好,对于数学学习很有用。

  26. 张大柱说道:

    K<N的情形在反演理论中经常遇到,不过都是做了各种前提假设,最后得到的一般称为最优解。

  27. unice说道:

    核磁共振成像不是利用不确定性原理吧。MRI之所以可以采集部分频域信息,是因为MRI的频域是共轭对称的,所以不需要采用全部的频域信息

  28. Lily说道:

    非常喜欢这个系列,醍醐灌顶了

  29. fenghaolw说道:

    从不确定性原理解释Compressed Sensing还是第一次看到,大赞。

    说起来这几年Compressed sensing这个大坑已经被大家一拥而上填得差不多了啊,不过除了MRI和单像素相机好像也没看到什么靠谱的应用。

  30. 徐希望说道:

    很好的文章,我就是喜欢这样的文章

Leave a Reply