想象你在整理一份很长很长的问卷调查一千个人填了一千份答案但每个人只回答了其中几个问题。现在你想根据这些零零散散的回答猜出问卷设计者最初想调查的到底是哪些关键议题。这听起来是不是有点像大海捞针这正是压缩感知这个领域几十年来一直在琢磨的问题只不过换了个更专业的说法从带噪声的线性观测中恢复一个稀疏信号的支撑集。麻省理工学院的两位研究者Youssef Chaabouni和David Gamarnik最近发表的一篇论文就是在这个老问题里挖出了一个新的角度,当测量工具本身也变得稀疏、变得抠门起来,我们到底要付出多大代价才能把原来的信号找回来。信号恢复,这件事到底难在哪先说清楚问题本身。假设有一个信号β?*一个长度为p的向量其中只有s个位置的数值不是零剩下的全是零。这s个非零位置构成的集合就叫这个信号的支撑集。你没办法直接看到这个信号你能看到的只是它经过一个随机测量矩阵X处理后再叠加了一层噪声Z的观测结果Y。用公式说就是Y Xβ? Z。你的任务是只凭着X和Y猜出β?原本长什么样或者说猜出它的支撑集在哪里。这就像是隔着一层毛玻璃看一幅画玻璃有点模糊(噪声)而且你看到的不是整幅画是画透过一套特殊镜片(测量矩阵)投射出来的光斑。你要根据光斑的样子反推出画上到底画了什么。过去的研究已经把密集测量矩阵也就是矩阵里几乎所有位置都是非零随机数的情况研究得很透彻了。核心结论是随着需要的观测样本数量n逐渐增大问题会经历三个阶段。样本太少的时候恢复根本不可能这是信息论层面的硬限制再聪明的算法也无能为力。样本数量到了一个中间地带理论上可以用最大似然估计法把信号找出来但这个过程计算量爆炸实际上没法在合理时间内跑出来。只有样本数量再往上冲过第二道门槛才有像LASSO这样的多项式时间算法能又快又准地把信号恢复出来。这三个阶段之间有两个明确的分界线学术上叫作信息论门限和算法门限。这个结构本身已经是压缩感知领域一个很成熟的认知框架了。密集测量矩阵存储和计算成本高一句话解释矩阵里几乎每个格子都是非零数字存起来占地方算起来也慢尤其当信号维度p很大的时候这个负担会指数级地压过来。那既然密集矩阵这么费劲为什么不干脆把测量矩阵也搞得稀疏一点大部分位置直接填零只留少数几个非零位置这个想法听起来很自然稀疏矩阵存储方便,矩阵和向量相乘的计算也快还能利用问题本身的结构性质设计更高效的恢复算法。但这里有个陷阱测量矩阵一旦变得稀疏需要的样本数量往往会跟着涨上去。天下没有免费的午餐你在存储和计算上省下来的可能要在数据采集数量上还回去。这就是这篇论文真正要回答的第一个核心问题测量的稀疏程度和所需样本数量之间到底是怎样一个具体的换算关系换句话说,稀疏这件事的价格到底是多少稀疏测量矩阵的样本门限价格公式长什么样论文里先给测量矩阵设定了一个具体的随机模型。矩阵X的每一个位置先按概率d/p决定它是不是零d是每一行期望的非零个数p是信号总维度如果不是零就再从标准正态分布里抽一个具体数值填进去。d越小矩阵越稀疏。信噪比SNR一句话解释衡量信号强度相对于噪声强度的比值这里具体等于ds除以p再除以噪声方差直观理解就是每一行测量里能碰到信号非零位置的概率乘以信号强度除以噪声的干扰程度。论文关注的是高信噪比场景也就是ds/p趋于无穷大的情况。作者证明了一个关键结论只要样本数量n超过一个具体的门限值最大似然估计就能在概率意义上把信号支撑集恢复出来误差控制在任意小的比例之内。这个门限值在信号是次线性稀疏s远小于p的情形下写成n大约等于 2s·log(p/s) 除以 log(ds/p)。这个公式乍看有点抽象但拆开看其实很直白。分子2s·log(p/s)恰好就是密集矩阵情形下所需的样本数量门限这是压缩感知领域早就确立的经典结果。分母log(ds/p)则完全是稀疏测量带来的新东西矩阵越稀疏d越小这个分母越小整个门限值就越大意味着需要更多的样本才能补偿测量稀疏带来的信息损失。这就好比你要在一个陌生城市找一家店如果你手里有一份详细地图密集测量走一趟就能定位但如果你只有几个路人零零散散提供的模糊指路信息稀疏测量你就得多问几个人、多走几趟才能拼凑出同样准确的位置。多问几个人就是多用几个样本而稀疏程度越高意味着每个路人给你的信息越少你就得问更多人才能凑够同样的信息量。如果不多问你大概率会走错路,这就是信息论下限告诉我们的样本不够恢复根本不可能不是算法不够聪明是信息量本身就不够。把这个门限和此前Wang、Wainwright、Ramchandran三人在2010年发表的必要条件结果放在一起看,论文得出了一个更完整的图景稀疏测量下的信号恢复问题同样存在一个清晰的信息论相变点。低于这个门限恢复在信息论意义上是不可能的高于这个门限哪?始终高出一点点最大似然估计就能可靠地找回信号。这个相变点正是文章标题里说的稀疏的价格的精确度量。作者定义了一个比值Γ等于稀疏情形所需样本数除以密集情形所需样本数具体写成log(s)除以log(ds/p)。这个比值恒大于1而且它的大小完全取决于d和s相对于p的增长速度。举个论文里的例子如果s等于p的α次方d等于p的β次方α加β大于1那么Γ等于α除以(αβ-1)。当β趋近于1测量几乎不稀疏时Γ趋近于1代价几乎消失当β趋近于1-α测量变得极度稀疏时Γ趋向无穷大代价变得极其昂贵。有意思的是论文还专门算了一笔性价比账。假设信号维度p固定稀疏测量矩阵每行只保留大约d个非零元素d的取值可以慢到近乎p的任意小的幂次。这时候样本数量的代价只是对数级别的增长但矩阵向量相乘的计算成本却能降到几乎线性。也就是说你多花一点点样本对数量级换来的是计算效率近乎线性的巨大提升。这笔交易怎么算都不亏。对比之前另一篇工作Omidiran和Wainwright在2008年的研究,他们证明了LASSO算法在稀疏测量下也能表现良好但前提是测量矩阵的稀疏度不能太极端具体要求d/p要以s的负三分之一次方的速度衰减。这篇论文的信息论结果覆盖了一个远比这更宽松的稀疏区间,只要d随着p缓慢增长哪怕增长得非常缓慢即可保证信息论意义上的恢复可能性只不过这时候最大似然估计的计算复杂度是指数级的还没有对应的高效算法。这也留下了一个悬而未决的问题在这个更宽松的稀疏区间里是否存在多项式时间的算法从密集数据到稀疏数据主动截肢还能救回信号吗聊完了第一个问题论文转向了一个更贴近实际应用场景的第二个问题。前面讨论的稀疏测量矩阵是研究者主动设计出来的这在信号压缩、图像采集这类场景里很常见你可以自己决定用什么样的矩阵去采样。但现实中还有大量场景测量矩阵是被动观测得到的比如做回归分析、信号去噪、纠错编码这些场景里的数据往往天生就是密集的你没办法事后重新设计一套稀疏的采集方案。那问题来了如果拿到的是一份已经密密麻麻的数据能不能事后把它稀疏化也就是随手抹掉大部分数据只留一小部分然后依然指望从这一小部分里恢复出原本的信号这个思路听起来有点冒险有点像神经网络压缩领域里的模型剪枝一句话解释把训练好的神经网络里大量接近于零或者不重要的权重直接置零从而在几乎不损失性能的前提下大幅压缩模型体积这个思路最早可以追溯到1989年LeCun等人提出的Optimal Brain Damage方法。这里的剪枝对象不一样神经网络剪枝剪的是模型参数这里剪的是测量矩阵但那种能不能大胆砍掉一大块东西还不伤筋动骨的问题精神是相通的。论文里具体的操作是这样的先用一个完全密集的高斯矩阵X生成真实的观测数据YXβ?Z。然后独立地对X做一次稀疏化处理,每个位置按概率1-d/p被置零剩下的原样保留得到一个新的稀疏矩阵X。同时把原始观测Y按比例d/p做一次缩放得到Y。最后试图用X, Y这对稀疏化后的数据去恢复原始的β?。这里有一个关键的细微差别值得停下来想一想观测数据Y是从密集矩阵X生成的但恢复过程用的是稀疏化之后的X加上一个粗暴缩放过的Y。这个Y并不是用稀疏矩阵重新做了一次真实测量它只是把原来密集测量的结果按比例缩小了一下。这就好比你本来有一份完整的会议记录现在把记录撕掉大半但发言总时长却按撕掉的比例往下打了折,这份被撕过的记录里其实混进了一些根本没被撕掉的部分本不该背负的信息扭曲。这个操作听起来简单粗暴,论文也确实证明这种简单粗暴的处理方式引入了一种系统性偏差这个偏差直接决定了后面要付出的代价有多大。在信号维度和信号稀疏度都按比例增长sαpα固定、稀疏化率也按比例设定dψpψ固定且足够小的情形下论文证明了对任意固定的目标误差水平δ和任意的松弛量ε只要样本数量n超过一个具体门限就能保证恢复出的支撑集误差控制在δ以内。这个门限的完整表达式稍微复杂但在ψ趋近于0的强稀疏化区间里可以简化写成n大约是p除以ψ的平方也就是Θ(p/ψ?)。这个平方关系值得多说两句。如果你把稀疏化率ψ砍掉一半需要的样本数量不是翻倍而是要涨到四倍。这个代价增长得比稀疏测量那边对数量级要猛烈得多。论文把这个额外代价称为稀疏化的价格并且特别强调了它和前面测量稀疏的价格性质完全不同。前者是因为测量矩阵本身信息密度低带来的必然损耗而后者纯粹是因为简单粗暴的缩放操作引入的观测偏差,是一种可以被更精细的处理方式所避免的人为损耗。换句话说稀疏化的价格不是稀疏本身欠下的债而是处理方式不够讲究欠下的债。反过来推算一下这个公式还能得到一个挺实用的结论如果你已经有n个观测样本那么大致上可以把数据稀疏化到只保留大约根号(p/n)这个比例的信息量依然能指望恢复出原始信号。而且样本数量翻一倍能承受的稀疏化程度只能提升根号2倍,想要稀疏化程度提升得更猛样本数量得跟着以平方的速度往上涨。这个证明过程比第一部分要曲折得多论文里专门用了一整节来讲清楚背后的技术障碍。核心困难在于稀疏化之后的观测Y并不是信号通过稀疏矩阵的一次干净投影它携带着从原始密集矩阵那里遗留下来的痕迹。这导致用来做大偏差估计的钦诺夫界一句话解释一种通过指数变换和优化技巧给随机变量落入极端区间的概率提供一个可计算上界的经典数学工具压缩感知和统计学里的很多恢复概率下界证明都靠它撑着。的计算里关键的矩生成函数会依赖于随机稀疏化掩码的具体实现而不是一个干净的确定性表达式。作者发现如果直接选用理论上最自然的钦诺夫参数会在指数小概率的一小撮坏掩码上出现退化直接处理这撮坏情况需要一个没法验证的一致可积性假设这在数学上是站不住脚的。论文最终想出的解决办法是引入一个收缩版的钦诺夫参数,把本来的最优参数乘上一个小于1的系数λ。这个收缩操作牺牲了一点点理论上的紧致性但换来的好处是它能让那个决定积分是否收敛的判别式在所有可能的掩码实现上都保持严格正数彻底避开了退化的陷阱。作者在论文里坦诚地提到这个收缩钦诺夫参数的想法是他们和大语言模型讨论技术细节时碰撞出来的最终的数学证明当然还是由作者自己完成并核验的。这就像是走钢丝的时候本来想找一条最短最直的路径过去但发现路径正中间偶尔会踩到几个看不见的坑,虽然踩中的概率极小极小但一旦踩中就直接摔下去理论上不允许这种小概率的灾难存在。于是干脆稍微绕一点弯路牺牲一点点效率但换来的是全程平稳任何一步都不会踩坑。这一点点绕路的代价就体现在最后公式里那个从1变成2λ-λ?的系数上好在只要λ足够接近1这个代价可以压缩到微乎其微。信息论门限和算法门限两条线各自在说什么论文里还专门整理了一张对照表把稀疏测量场景下已知的四类结果放在一起看信息论意义下的必要条件、信息论意义下的充分条件也就是这篇论文的贡献、算法意义下的必要条件目前还是未知以及算法意义下的充分条件。密集情形下这四条线全都已经被前人研究清楚了。稀疏、高信噪比情形下必要条件是Wang等人给出的2s·log(p/s)除以log(ds/p)充分条件正是这篇论文证明的同一个表达式,两者形式上完全吻合说明这个门限是紧的不存在进一步收窄的空间。但算法层面目前只知道在测量不太稀疏的假设下LASSO能达到和密集情形一样的门限至于更稀疏的区间里到底存不存在多项式时间算法论文明确标注为未知留给了后续研究去填。这里有个值得琢磨的地方。论文的作者也很诚实地指出他们证明的充分条件和Wang等人证明的必要条件严格说起来度量的不是完全同一件事。必要条件否定的是精确恢复支撑集充分条件保证的则是支撑集的错误比例趋于零这是一个概率意义上更弱的陈述。两者逻辑上是兼容的但要凑成像密集情形下Reeves、Xu、Zadik三人证明的那种全有或全无现象也就是恢复要么完全成功要么完全失败中间没有过渡态还差一口气作者把这个留作了未来的研究方向。这种诚实标注我们还没证到多强的态度其实是学术论文里很珍贵的品质。很多时候一个漂亮的公式背后藏着几个没敢细说的模糊地带能不能把这些模糊地带主动摊开来说恰恰是判断一篇论文严谨程度的标尺之一。写在后面读这篇论文的过程中最让我意外的一个点是稀疏化那部分里价格来源的区分。很多人包括我自己一开始的直觉都会觉得稀疏测量矩阵和稀疏化一个密集矩阵付出的代价应该是同一种性质的东西,毕竟都是数据变少了。但论文清楚地把两者的代价来源拆开了一个是信息密度天然不足带来的对数级代价一个是处理方式不精细导致的观测偏差带来的平方级代价。这两种代价的数学形式差了整整一个量级背后的原因却完全不是稀疏程度不同这么简单而是有没有引入额外的系统性偏差。这提醒我一件事谈论稀疏的时候光说数据少了多少是不够的还要问数据是怎么变少的。同样是砍掉90%的信息砍法不同代价可能天差地别。这个区分不只是压缩感知领域的事任何做数据压缩、模型剪枝、采样降维的场景可能都值得先问一句我这刀砍下去砍出来的是纯粹的信息损失还是又顺带引入了一层没人注意到的偏差论文结尾提出的猜想也挺有意思作者猜测如果稀疏化率d相对于p是次线性增长的也就是比例趋于零的稀疏化那么无论用多少样本恢复都会变得信息论意义上不可能。这个猜想目前还没有被证明如果成立意味着稀疏化这件事存在一个绝对的天花板,不是代价大不大的问题而是能不能做的问题。这条线到底在哪里会是个值得追下去的问题。QAQ1稀疏测量矩阵和普通密集矩阵相比信号恢复到底需要多付出多少样本A在高信噪比、信号次线性稀疏的情形下稀疏测量所需样本数是密集情形的log(s)/log(ds/p)倍这个比值恒大于1具体大小取决于测量矩阵的稀疏程度d和信号维度p、稀疏度s的相对增长速度测量越稀疏代价越大。Q2把一份原本密集的数据事后稀疏化还能恢复出原始信号吗A可以论文证明在信号和稀疏化率都按比例增长且稀疏化率足够小的前提下只要样本数量达到大约p除以稀疏化率的平方这个量级就能把恢复误差控制在目标范围内但这个代价比单纯的测量稀疏要昂贵得多。Q3稀疏测量的代价和数据稀疏化的代价是同一种东西吗A不是。测量稀疏的代价来自信息密度本身不足是对数级的数据稀疏化的代价来自缩放观测值时引入的系统性偏差是平方级的两者数学形式和产生原因完全不同。