适定、超定和欠定方程及压缩传感技术不定方程http://wenku.baidu.com/view/67aa0b6f25c52cc58bd6bedb.htmlhttp://wenku.baidu.com/view/e9dfd0d328ea81c758f57864.htmlCS (Compressive sensing, 压缩传感)

72 阅读 0 评论 48 点赞

我是靠谱客的博主酷酷小懒猪，最近开发中收集的这篇文章主要介绍适定、超定和欠定方程及压缩传感技术不定方程http://wenku.baidu.com/view/67aa0b6f25c52cc58bd6bedb.htmlhttp://wenku.baidu.com/view/e9dfd0d328ea81c758f57864.htmlCS (Compressive sensing, 压缩传感)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

原文“适定、超定和欠定方程”，链接http://blog.sina.com.cn/s/blog_4b700c4c0102e5v3.html.

不定方程

http://wenku.baidu.com/view/67aa0b6f25c52cc58bd6bedb.html

http://wenku.baidu.com/view/e9dfd0d328ea81c758f57864.html

http://wenku.baidu.com/view/5ab3d7c70c22590102029dbd.html

http://wenku.baidu.com/view/e9dfd0d328ea81c758f57864.html

适定、超定和欠定方程的概念

矩阵的每一行代表一个方程，m行代表m个线性联立方程。 n列代表n个变量。如果m是独立方程数，根据m<n、m=n、m>n确定方程是 ‘欠定’、‘适定’ 还是 ‘超定’。

超定方程组：方程个数大于未知量个数的方程组。

对于方程组Ra=y，R为n×m矩阵，如果R列满秩，且n>m

超定方程一般是不存在解的矛盾方程。

例如，如果给定的三点不在一条直线上，我们将无法得到这样一条直线，使得这条直线同时经过给定这三个点。也就是说给定的条件（限制）过于严格，导致解不存在。在实验数据处理和曲线拟合问题中，求解超定方程组非常普遍。比较常用的方法是最小二乘法。形象的说，就是在无法完全满足给定的这些条件的情况下，求一个最接近的解。

曲线拟合的最小二乘法要解决的问题，实际上就是求以上超定方程组的最小二乘解的问题。

欠定方程组: 方程个数小于未知量个数的方程组。

对于方程组Ra=y，R为n×m矩阵，且n<m。则方程组有无穷多组解，此时称方程组为欠定方程组。

内点法和梯度投影法是目前解欠定方程组的常用方法。

trackback: http://hgcwxh.blog.163.com/blog/static/5864251720118185139630/

什么是欠定方程?

所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些（如要求是有理数、整数或正整数等等）的方程或方程组。不定方程也称为丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。参考资料：http://blog.sina.com.cn/s/blog_4b700c4c0100kyz0.html

不(欠)定方程http://blog.sina.com.cn/s/blog_4b700c4c0100kyz0.html

不定方程

所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些限制（如要求是有理数、整数或正整数等等）的方程或方程组。

　　indeterminate equation

　　不定方程是数论的一个分支，它有着悠久的历史与丰富的内容。所谓不定方程是指解的范围为整数、正整数、有理数或代数整数的方程或方程组，其未知数的个数通常多于方程的个数。

　　古希腊数学家丢番图于三世纪初就研究过若干这类方程，所以不定方程又称丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。1969年，莫德尔较系统地总结了这方面的研究成果。

概述

　　不定方程是数论中最古老的分支之一。

　　古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。 Diophantus，古代希腊人，被誉为代数学的鼻祖，流传下来关于他的生平事迹并不多。今天我们称整系数的不定方程为「Diophantus方程」，内容主要是探讨其整数解或有理数解。他有三本著作，其中最有名的是《算术》，当中包含了189个问题及其答案，而许多都是不定方程组 (变量的个数大于方程的个数)或不定方程式 (两个变数以上)。丢番图只考虑正有理数解，而不定方程通常有无穷多解的。

　　研究不定方程要解决三个问题：①判断何时有解。②有解时决定解的个数。③求出所有的解。中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志中国对不定方程理论有了系统研究。秦九韶的大衍求一术将不定方程与同余理论联系起来。百鸡问题说：“鸡翁一，直钱五，鸡母一，直钱三，鸡雏三，直钱一。百钱买百鸡，问鸡翁、母、雏各几何？”。设x，y，z分别表鸡翁、母、雏的个数，则此问题即为不定方程组的非负整数解x，y，z，这是一个三元不定方程组问题。

问题的常见类型

　　（1）求不定方程的解；

　　（2）判定不定方程是否有解；

　　（3）判定不定方程的解的个数（有限个还是无限个）。

一次不定方程

　　二元一次不定方程的一般形式为ax+by=c。其中 a，b，c 是整数，ab ≠ 0。此方程有整数解的充分必要条件是a、b的最大公约数整除c。若a、b互质，即它们的最大公约数为1，(x0，y0)是所给方程的一个解，则此方程的解可表为{(x=x0-bt，y=y0+at）|t为任意整数}。

　　S（≥2）元一次不定方程的一般形式为a1x1+a2x2+…+asxs=n0a1，…，as，n为整数，且a1…as≠0。此方程有整数解的充分必要条件是a1，…，as的最大公约数整除n。

　　埃拉托塞尼筛法产生的素数普遍公式是一次不定方程　公元前300年，古希腊数学家欧几里得就发现了数论的本质是素数，他自己证明了有无穷多个素数，公元前250年古希腊数学家埃拉托塞尼发明了一种筛法：

　　（一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。后来人们

　　（二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<d≤√N”。（《基础数论》13页，U杜德利著，上海科技出版社）。.

　　（三）再将（二）的内容等价转换：“若自然数N不能被不大于(根号)√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。

　　（四）上面这句话的汉字可以等价转换成为用英文字母表达的公式：

　　N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(1) 　　

　　其中 p1，p2，.....，pk表示顺序素数2，3，5，,,,,。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标] ，则N是一个素数。

　　（五）可以把（1）等价转换成为用同余式组表示：

　　N≡a1(modp1)， N≡a2(modp2)，.....，N≡ak(modpk)。 (2)

　　例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于7的平方49，所以29是一个素数。

　　以后平方用“*”表示，即：㎡=m*。

　　由于（2）的模p1，p2，....，pk 两两互素，根据孙子定理(中国剩余定理）知，（2）在p1p2.....pk范围内有唯一解。

　　例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。

　　k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。

　　k=3时,

　　---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|

　　---------------------|---------|----------|--------|---------|

　　n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----|

　　n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|

　　------------------------------------------------------------

　　求得了（7，7*）区间的全部素数。仿此下去可以求得任意大的数以内的全部素数。

多元一次不定方程

　　关于整数多元一次不定方程，可以有矩阵解法、程序设计等相关方法辅助求解。

二次不定方程

　　二元二次不定方程本质上可以归结为求二次曲线（即圆锥曲线）的有理点或整点问题。

　　一类特殊的二次不定方程是x^2+y^2=z^2，其正整数解称商高数或勾股数或毕达哥拉斯数，中国《周髀算经》中有“勾广三，股修四，经隅五”之说，已经知道（3，4，5）是一个解。刘徽在注《九章算术》中又给出了（5，12，13），（8，15，17），（ 7，24，25），（20，21，29）几组勾股数。它的全部正整数解已在16世纪前得到。这类方程本质上就是求椭圆上的有理点。

　　另一类特殊的二次不定方程是所谓佩尔方程x2－Dy2=1，D是非平方的正整数。利用连分数理论知此方程永远有解。这类方程就是求双曲线上的有理点。

　　最后一类就是平方剩余问题，即求x^2-py=q的整数解，用高斯的同余理论来描述，就是求x^2≡q(mod p) 的剩余类解。高斯发现的著名二次互反律给出了次方程是否有解的判定方法。这类方程就相当于求抛物线上的整点。

　　圆锥曲线对应的不定方程求解可以看做椭圆曲线算术性质的一种特例。

高次不定方程

　　对高于二次的不定方程，相当复杂。当n>2时，x^n+y^n=z^n没有非平凡的整数解，即著名的费马大定理，历经3个世纪，已由英国数学家安德鲁 ·维尔斯证明完全可以成立。

　　有一些高次方程同样无解。

多元高次不定方程

　　多元高次不定方程没有一般的解法，任何一种解法都只能解决一些特殊的不定方程，如利用二次域来讨论一些特殊的不定方程的整数解．

解不定方程问题常用的解法

　　（1）代数恒等变形：如因式分解、配方、换元等；

　　（2）不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解；

　　（3）同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解；

　　（4）构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解；

　　（5）无穷递推法。

一些特殊方程的求解方法

　　（一）二元一次不定方程（组）

　　定义1. 形如 ax + by = c ( a，b，c∈Z，a，b不同时为零)的方程称为二元一次不定方程。

　　定理1. 方程 ax + by = c 有解的充要是 ( a,b ) | c；

　　定理2. 若( a,b ) = 1，且 x_0，y_0为 ax + by = c 的一个解，

　　定理3. n元一次不定方程 a_1x_1 + a_2x_2 +…+ a_nx_n = c，( a_1，a_2，…a_n，c∈N )有解的充要条件是：( a_1，a_2，…a_n ) | c.

　　方法与技巧：

　　1．解二元一次不定方程通常先判定方程有无解。若有解，可先求 ax + by = c 一个特解，从而写出通解。当不定方程系数不大时，有时可以通过观察法求得其解，即引入变量，逐渐减小系数，直到容易得其特解为止；

　　2．解n元一次不定方程 a_1x_1 + a_2x_2 +…+ a_nx_n = c 时，可先顺次求出 ( a_1，a_2 ) = d_2，( d_2，a_3 ) = d_3，…，( d_(n-1)，a_n ) = d_n. 若c不能被 d_n 整除，则方程无解；若c可以被 d_n 整除，则方程有解，

　　求出最后一个方程的一切解，然后把 t_(n-1) 的每一个值代入倒数第二个方程，求出它的一切解，这样下去即可得方程的一切解。

　　3．m个n元一次不定方程组成的方程组，其中 m < n，可以消去 m-1 个未知数，从而消去了 m-1 个不定方程，将方程组转化为一个 n-m+1 元的一次不定方程。

　　（二）高次不定方程（组）及其解法

　　1．因式分解法：对方程的一边进行因式分解，另一边作质因式分解，然后对比两边，转而求解若干个方程组；

　　2．同余法：如果不定方程 F( x_1，x_2，…，x_n ) = 0 有整数解，则对于任意 m∈N，其整数解 ( x_1，x_2，…，x_n ) 满足 F( x_1，x_2，…，x_n ) ≡ 0 ( modm )，利用这一条件，同余可以作为探究不定方程整数解的一块试金石；

　　3．不等式估计法：利用不等式工具确定不定方程中某些字母的范围，再分别求解；

　　4．无限递降法：若关于正整数n的命题 P(n) 对某些正整数成立，设 n_0 是使 P(n) 成立的最小正整数，可以推出：存在正整数n，使得 n_1 < n_0 成立，适合证明不定方程无正整数解。

　　方法与技巧：

　　1．因式分解法是不定方程中最基本的方法，其理论基础是整数的唯一分解定理，分解法作为解题的一种手段，没有因定的程序可循，应具体的例子中才能有深刻地体会；

　　2．同余法主要用于证明方程无解或导出有解的必要条件，为进一步求解或求证作准备。同余的关键是选择适当的模，它需要经过多次尝试；

　　3．不等式估计法主要针对方程有整数解，则必然有实数解，当方程的实数解为一个有界集，则着眼于一个有限范围内的整数解至多有有限个，逐一检验，求出全部解；若方程的实数解是无界的，则着眼于整数，利用整数的各种性质产生适用的不等式；

　　4．无限递降法论证的核心是设法构造出方程的新解，使得它比已选择的解“严格地小”，由此产生矛盾。

　　（三）特殊的不定方程

　　1．利用分解法求不定方程 ax + by = cxy ( abc≠0 )整数解的基本思路：

　　将 ax + by = cxy 转化为 (x - a)(cy -b) = ab 后，若 ab 可分解为 ab = a_1b_1 = a_2b_2 =…= a_ib_i∈Z。

　　再取舍得其整数解；

　　2．定义2：形如的 x^2 + y^2 = z^2 的方程叫做勾股数方程，这里x，y，z为正整数。

　　对于方程 x^2 + y^2 = z^2 ，如果 (x，y) = d，则 d^2|z^2，从而只需讨论 (x，y) = 1 的情形，此时易知x，y，z两两互素，这种两两互素的正整数组叫方程的本原解。

　　定理3.勾股数方程满足条件 2|y 的一切解可表示为：

　　其中 a > b > 0，(a，b) = 1，且a，b为一奇一偶。

　　其中 a > b > 0 是互质的奇偶性不同的一对正整数，d是一个整数。

　　勾股数不定方程的整数解的问题主要依据定理来解决。

　　3．定义3.方程 x^2 - dy^2 = ±1，±4 ( x，y∈Z，正整数d不是平方数) 是 x^2 - dy^2 = c 的一种特殊情况，称为沛尔(Pell)方程。

　　这种二元二次方程比较复杂，它们本质上归结为双曲线方程 x^2 - dy^2 = c 的研究，其中c，d都是整数，d > 0 且非平方数，而 c ≠ 0。它主要用于证明问题有无数多个整数解。对于具体的d可用尝试法求出一组成正整数解。如果上述pell方程有正整数解(x，y)，则称使 x + yd^0.5 的最小的正整数解为它的最小解。

　　定理4.Pell方程 x^2 - dy^2 = 1 ( x，y∈Z，正整数d不是平方数)必有正整数解，且若设它的最小解为(x_1，y_1)。

　　定理5.Pell方程 x^2 - dy^2 = -1 ( x，y∈Z，正整数d不是平方数)要么无正整数解，要么有无穷多组正整数解，且在后一种情况下，设它的最小解为(x_1，y_1)。

　　定理6. （费尔马（Fermat）大定理）方程 x^n + y^n = z^n (n≥3且为整数)无正整数解。

　　费尔马（Fermat）大定理的证明一直以来是数学界的难题，但是在1994年6月，美国普林斯顿大学的数学教授A.Wiles完全解决了这一难题。至此，这一困扰了人们四百多年的数学难题终于露出了庐山真面目，脱去了其神秘面纱。

简单例题

　　例1 求11x+15y=7的整数解．

　　解法1 将方程变形得

　　因为x是整数，所以7-15y应是11的倍数．由观察得x0=2，y0=-1是这个方程的一组整数解，所以方程的解为

　　解法2 先考察11x+15y=1，通过观察易得

　　11×(-4)+15×(3)=1，

　　所以

　　11×(-4×7)+15×(3×7)=7，

　　可取x0=-28，y0=21．从而

　　可见，二元一次不定方程在无约束条件的情况下，通常有无数组整数解，由于求出的特解不同，同一个不定方程的解的形式可以不同，但它们所包含的全部解是一样的．将解中的参数t做适当代换，就可化为同一形式．

　　例2 求方程6x+22y=90的非负整数解．

　　解因为(6，22)=2，所以方程两边同除以2得

　　3x+11y=45． ①

　　由观察知，x1=4，y1=-1是方程

　　3x+11y=1 ②

　　的一组整数解，从而方程①的一组整数解为

　　由定理，可得方程①的一切整数解为

　　因为要求的是原方程的非负整数解，所以必有

　　由于t是整数，由③，④得15≤t≤16，所以只有t=15，t=16两种可能．

　　当t=15时，x=15，y=0；当t=16时，x=4，y=3．所以原方程的非负整数解是

　　例3 求方程7x+19y=213的所有正整数解．

　　分析这个方程的系数较大，用观察法去求其特殊解比较困难，碰到这种情况我们可用逐步缩小系数的方法使系数变小，最后再用观察法求得其解．

　　解用方程

　　7x+19y=213 ①

　　的最小系数7除方程①的各项，并移项得

　　因为x，y是整数，故3-5y/7=u也是整数，于是5y+7u=3．T儆*5除此式的两边得

　　2u+5v=3． ④

　　由观察知u=-1，v=1是方程④的一组解．将u=-1，v=1代入③得y=2．y=2代入②得x=25．于是方程①有一组解x0=25，y0=2，所以它的一切解为

　　由于要求方程的正整数解，所以

　　解不等式，得t只能取0，1．因此得原方程的正整数解为

　　当方程的系数较大时，我们还可以用辗转相除法求其特解，其解法结合例题说明．

　　例4 求方程37x+107y=25的整数解．

　　解 107=2×37+33，

　　37=1×33+4，

　　33=8×4+1．

　　为用37和107表示1，我们把上述辗转相除过程回代，得

　　1=33-8×4=37-4-8×4=37-9×4

　　=37-9×(37-33)=9×33-8×37

　　=9×(107-2×37)8×37=9×107-26×37

　　=37×(-26)+107×9．

　　由此可知x1=-26，y1=9是方程37x+107y=1的一组整数解．于是

　　x0=25×(-26)=-650，y0=25×9=225

　　是方程37x+107y=25的一组整数解．

　　所以原方程的一切整数解为

　　例5 某国硬币有5分和7分两种，问用这两种硬币支付142分货款，有多少种不同的方法？

　　解设需x枚7分，y枚5分恰好支付142分，于是

　　7x+5y=142. ①

　　所以

　　由于7x≤142，所以x≤20，并且由上式知5|2(x-1)．因为(5，2)=1，所以5|x-1，从而x=1，6，11，16，①的非负整数解为

　　所以，共有4种不同的支付方式．

　　说明当方程的系数较小时，而且是求非负整数解或者是实际问题时，这时候的解的组数往往较少，可以用整除的性质加上枚举，也能较容易地解出方程．

　　多元一次不定方程可以化为二元一次不定方程．

　　例6 求方程9x+24y-5z=1000的整数解．

　　解设9x+24y=3t，即3x+8y=t，于是3t-5z=1000．于是原方程可化为

　　用前面的方法可以求得①的解为

　　②的解为

　　消去t，得

　　大约1500年以前，我国古代数学家张丘建在他编写的《张丘建算经》里，曾经提出并解决了“百钱买百鸡”这个有名的数学问题，通俗地讲就是下例．

　　例7 今有公鸡每只五个钱，母鸡每只三个钱，小鸡每个钱三只．用100个钱买100只鸡，问公鸡、母鸡、小鸡各买了多少只？

　　解设公鸡、母鸡、小鸡各买x，y，z只，由题意列方程组

　　①化简得 15x+9y+z=300． ③

　　③-②得 14x+8y=200，

　　即 7x+4y=100．

　　解7x+4y=1得

　　于是7x+4y=100的一个特解为

　　由定理知7x+4y=100的所有整数解为

　　由题意知，0<x，y，z<100，所以

　　由于t是整数，故t只能取26，27，28，而且x，y，z还应满足

　　x+y+z=100．

　　t x y z

　　26 4 18 78

　　27 8 11 81

　　28 12 4 84

　　即可能有三种情况：4只公鸡，18只母鸡，78只小鸡；或8只公鸡，11只母鸡，81只小鸡；或12只公鸡，4只母鸡，84只小鸡．

多项式不定方程与代数几何

　　对于多项式不定方程，我们相当于求解某个代数簇上的有理点或整点等等。这样，一个数论问题就转化为某种几何问题。这种观点将数论与代数几何联系起来，是一种重要的数学思想。对于代数曲线来说，相应的不定方程是否有解的以及是否有无限个解，都与曲线的亏格密切相关。这就是著名的莫代尔猜想（由法尔廷斯证明）所包含的内容。

　　亏格零的曲线就是直线和二次曲线，他们就对应了上述的一次和二次不定方程。亏格1的是椭圆曲线，它的算术性质和代数几何性质极为丰富。它将数论、复分析、代数几何、表示论等等都联系起来，是当代数学最重要的研究对象之一。与此相关的是千禧年七大数学难题之一的BSD猜想。

　　著名的费马大定理的证明也与此相关。

进展与学科联系

　　近年来，这个领域更有重要进展。但从整体上来说，对于高于二次的多元不定方程，人们知道得不多。另一方面，不定方程与数学的其他分支如代数数论、代数几何、组合数学等有着紧密的联系，在有限群论和最优设计中也常常提出不定方程的问题，这就使得不定方程这一古老的分支继续吸引着许多数学家的注意，成为数论中重要的研究课题之一。

CS (Compressive sensing, 压缩传感)

由来

　　采样定理（又称取样定理、抽样定理）是采样带限信号过程所遵循的规律，1928年由美国电信工程师H.奈奎斯特首先提出来的，因此称为奈奎斯特采样定理。1948年信息论的创始人C.E.香农对这一定理加以明确说明并正式作为定理引用，因此在许多文献中又称为香农采样定理。该理论支配着几乎所有的信号/图像等的获取、处理、存储、传输等，即：采样率不小于最高频率的两倍(该采样率称作Nyquist采样率)。该理论指导下的信息获取、存储、融合、处理及传输等成为目前信息领域进一步发展的主要瓶颈之一，主要表现在两个方面：

　　(1)数据获取和处理方面。对于单个(幅)信号/图像，在许多实际应用中(例如，超宽带通信，超宽带信号处理，THz成像，核磁共振，空间探测，等等）， Nyquist采样硬件成本昂贵、获取效率低下，在某些情况甚至无法实现。为突破Nyquist采样定理的限制，已发展了一些理论，其中典型的例子为Landau理论， Papoulis等的非均匀采样理论，M. Vetterli等的 finite rate of innovation信号采样理论，等。对于多道(或多模式)数据(例如，传感器网络，波束合成，无线通信，空间探测，等)，硬件成本昂贵、信息冗余及有效信息提取的效率低下，等等。

　　(2)数据存储和传输方面。通常的做法是先按照Nyquist方式获取数据，然后将获得的数据进行压缩，最后将压缩后的数据进行存储或传输，显然，这样的方式造成很大程度的资源浪费。另外，为保证信息的安全传输，通常的加密技术是用某种方式对信号进行编码，这给信息的安全传输和接受带来一定程度的麻烦。

　　综上所述：Nyquist-Shannon理论并不是唯一、最优的采样理论，研究如何突破以Nyquist-Shannon采样理论为支撑的信息获取、处理、融合、存储及传输等的方式是推动信息领域进一步往前发展的关键。众所周知：(1)Nyquist采样率是信号精确复原的充分条件，但绝不是必要条件。(2)除带宽可作为先验信息外，实际应用中的大多数信号/图像中拥有大量的structure。由贝叶斯理论可知：利用该structure信息可大大降低数据采集量。(3) Johnson-Lindenstrauss理论表明：以overwhelming性概率，K+1次测量足以精确复原N维空间的K-稀疏信号。

　　近年来，由D. Donoho(美国科学院院士)、E. Candes(Ridgelet, Curvelet创始人)及华裔科学家T. Tao(2006年菲尔兹奖获得者，2008年被评为世界上最聪明的科学家)等人提出了一种新的信息获取指导理论，即，压缩感知或压缩传感（Compressive Sensing(CS) or Compressed Sensing、Compressed Sampling）。该理论指出：对可压缩的信号可通过远低于Nyquist标准的方式进行采样数据，仍能够精确地恢复出原始信号。该理论一经提出，就在信息论、信号/图像处理、医疗成像、模式识别、地质勘探、光学/雷达成像、无线通信等领域受到高度关注，并被美国科技评论评为2007年度十大科技进展。目前CS理论的研究尚属于起步阶段，但已表现出了强大的生命力，并已发展了分布CS理论(Baron等提出)，1-BIT CS理论(Baraniuk等提出)，Bayesian CS理论(Carin等提出)，无限维CS理论(Elad等提出)，变形CS理论(Meyer等提出)，等等，已成为数学领域和工程应用领域的一大研究热点。

基本知识

　　核心思想是将压缩与采样合并进行，首先采集信号的非自适应线性投影 (测量值)，然后根据相应重构算法由测量值重构原始信号。压缩传感的优点在于信号的投影测量数据量远远小于传统采样方法所获的数据量，突破了香农采样定理的瓶颈，使得高分辨率信号的采集成为可能。

　　压缩传感理论主要包括信号的稀疏表示、编码测量和重构算法等三个方面。信号的稀疏表示就是将信号投影到正交变换基时，绝大部分变换系数的绝对值很小，所得到的变换向量是稀疏或者近似稀疏的，以将其看作原始信号的一种简洁表达，这是压缩传感的先验条件，即信号必须在某种变换下可以稀疏表示。通常变换基可以根据信号本身的特点灵活选取，常用的有离散余弦变换基、快速傅里叶变换基、离散小波变换基、Curvelet基、Gabor 基以及冗余字典等。在编码测量中，首先选择稳定的投影矩阵，为了确保信号的线性投影能够保持信号的原始结构，投影矩阵必须满足约束等距性 (Restricted isometry property, RIP)条件，然后通过原始信号与测量矩阵的乘积获得原始信号的线性投影测量。最后，运用重构算法由测量值及投影矩阵重构原始信号。信号重构过程一般转换为一个最小L0范数的优化问题，求解方法主要有最小L1 范数法、匹配追踪系列算法、最小全变分方法、迭代阈值算法等。

应用领域

　　压缩传感技术是一种抽象的数学概念，而不是具体的操作方案，它可以应用到成像以外的许多领域。以下只是其中几个例子：

　　磁共振成像(MRI)：在医学上，磁共振的工作原理是做许多次（但次数仍是有限的）测量（基本上就是对人体图像进行离散拉东变换（也叫X光变换）），再对数据进行加工来生成图像（在这里就是人体内水的密度分布图像）。由于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数，加快成像（甚至有可能做到实时成像，也就是核磁共振的视频而非静态图像）。此外我们还可以以测量次数换图像质量，用与原来一样的测量次数可以得到好得多的图像分辨率。

　　天文学：许多天文现象（如脉冲星）具有多种频率震荡特性，使其在频域上是高度稀疏也就是可压缩的。压缩传感技术将使我们能够在时域内测量这些现象（即记录望远镜数据）并能够精确重建原始信号，即使原始数据不完整或者干扰严重（原因可能是天气不佳，上机时间不够，或者就是因为地球自传使我们得不到全时序的数据）。

　　线性编码：压缩传感技术提供了一个简单的方法，让多个传送者可以将其信号带纠错地合并传送，这样即使输出信号的一大部分丢失或毁坏，仍然可以恢复出原始信号。例如，可以用任意一种线性编码把1000比特信息编码进一个3000比特的流；那么，即使其中300位被（恶意）毁坏，原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号（只集中在3000比特中的300位）。

需要解决的问题

　　尽管压缩传感已经在很多领域表现出了超然的优势，但作为一种新兴的理论，CS还有很多有待完善的地方。

　　比如测量矩阵的设计，怎样设计测量矩阵使得更符合原始信号的结构特点，并能以最大概率精确重构原始信号，而并非一定要满足RIP，即要找出充要条件；

　　比如如何让实现动态测量，尤其是在硬件实现上；

　　还有算法的优化，如何减少计算量，提高重建速度等等。

trackback: http://baike.baidu.com/view/2761805.html?fromTaglist

Link

Massimo Fornasier and Holger Rauhut, Compressive Sensing. (Chapter in Part 2 of the "Handbook of Mathematical Methods in Imaging" (O. Scherzer Ed.), Springer, 2011 (http://www.ricam.oeaw.ac.at/people/page/fornasier/CSFornasierRauhut.pdf)
Compressed Sensing: A Tutorial (PPT), http://people.ee.duke.edu/~willett/SSP//Tutorials/ssp07-cs-tutorial.pdf
Candes, E., & Wakin, M. (2008). An Introduction To Compressive Sampling IEEE Signal Processing Magazine, 25 (2), 21-30 DOI:10.1109/MSP.2007.914731 (中文翻译：http://www.cvchina.info/2011/05/07/ej-candes-translation/)
Shihao Ji, Y. Xue, and L. Carin, "Bayesian compressive sensing," IEEE Trans. Signal Processing, vol. 56, no. 6, pp. 2346-2356, June 2008. [pdf file | code]
Introduction to Restricted Isometry Property (RIP), http://cnx.org/content/m15149/latest/
R. Baraniuk , M. Davenport , R. DeVore and M. Wakin "A simple proof of the restricted isometry property for random matrices", Constr. Approx., , 2008. (http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/JL_RIP.pdf)