用于压缩感知的非欠定估算

摘要

信号矢量的非零元素，其可为稀疏信号矢量，其可基于代表欠定观测的集合的观测矢量、运用压缩感知优化和非欠定估算方法例如迭代线性最小均方差(“LMMSE”)估算而确定。压缩感知优化可用于求得所述信号矢量的潜在非零元素的子集，然后LMMSE估算可用于从所述潜在非零元素中找出非零元素。然后可使用标明的所述非零元素来从所述观测矢量中还原出所述信号矢量。此技术可用于从测量中还原压缩数据，例如音频或视频数据的稀疏频率空间表示。此技术也可用于在过载通信网络中的基站处识别出相对少数的活动设备。

权利要求

1.一种方法，包括：

处理器接收观测矢量，所述观测矢量包括对信号的观测集；

基于所述观测矢量和观测矩阵，所述处理器运用压缩感知优化生成信号矢量估算；

依据稀疏化范数，所述处理器确定所述信号矢量估算中特征元素的指数集，其中所述特征元素的个数至多为所述观测矢量中元素的个数；以及基于所述观测矩阵、所述观测矢量和所述信号矢量估算中特征元素的所述指数集，所述处理器通过执行非欠定估算方法，生成信号矢量的非零元素的指数集。

2.根据权利要求1所述的方法，其中所述信号对所述信号矢量进行编码，并且所述观测矢量中元素的个数少于所述信号矢量中元素的总数。

3.根据权利要求1所述的方法，其中所述观测矢量中元素的个数大于所述信号矢量的非零元素的个数。

4.根据权利要求3所述的方法，其中所述特征元素的个数大于所述信号矢量的非零元素的个数。

5.根据权利要求1所述的方法，其中所述特征元素的个数小于所述观测矢量的元素的个数。

6.根据权利要求1所述的方法，其中所述观测矩阵描述所述观测矢量与所述信号矢量之间的关系。

7.根据权利要求1所述的方法，其中所述非欠定估算方法是迭代线性最小均方差LMMSE估算法，其中所述处理器在所述LMMSE估算法的每次迭代中都基于所述观测矢量和迭代指数集生成信号矢量估算子集，并依据所述稀疏化范数，确定所述信号矢量估算子集中特征元素的迭代指数子集，其中在每次迭代中，所述迭代指数子集的大小都比所述迭代指数集小一个预定的步长，其中在第一迭代中，所述迭代指数集是所述信号矢量估算的特征元素的指数集，并且其中在每次逐次迭代中，所述迭代指数集都是其上一次迭代的迭代指数子集。

8.根据权利要求7所述的方法，其中所述信号矢量的非零元素是所述LMMSE估算法最后一次迭代之后的所述信号矢量估算子集的元素。

9.根据权利要求8所述的方法，还包括：

基于所述LMMSE估算法最后一次迭代之后的所述信号矢量的非零元素的指数集和所述信号矢量估算子集的元素，还原所述信号矢量；以及输出所述信号矢量。

10.根据权利要求1所述的方法，还包括：

输出所述信号矢量的非零元素的指数集。

11.根据权利要求8所述的方法，其中在所述LMMSE估算法的每次迭代中，所述信号矢量估算子集确定于：其中，

其中，是所述迭代指数集， 是对应于迭代指数集 的所述信号矢量估算子集，y是所述观测矢量， 是矢量子集 的协方差矩阵， 是对应于迭代指数集 的观测子矩阵，是观测子矩阵 的共轭转置，并且Cz是噪音矢量z的协方差矩阵。

12.根据权利要求1所述的方法，其中所述稀疏化范数是l1范数。

13.根据权利要求1所述的方法，其中所述压缩感知优化法优化最小绝对收缩与选择算子Lasso。

14.根据权利要求13所述的方法，其中所述压缩感知优化法是所述Lasso的坐标下降优化。

15.根据权利要求1所述的方法，其中所述处理器包括数字信号处理器。

16.根据权利要求1所述的方法，其中所述观测矢量对所述信号矢量的压缩形式进行编码，并且其中所述观测矩阵定义压缩模式。

17.根据权利要求16所述的方法，其中所述观测矢量对图片、视频或音频数据在表示域中的压缩表示进行编码，并且所述信号矢量对所述图片、所述视频或所述音频数据在所述表示域中的未压缩表示进行编码。

18.根据权利要求17所述的方法，其中所述表示域是频域或小波域。

19.根据权利要求1所述的方法，其中所述观测矢量对接收自第一组多个传输中设备的调制符号的观测进行编码，其中所述观测矩阵对多个符号调制签名进行编码，并且其中所述信号矢量在包含第二组多个非传输中设备的较多的多个设备中标识所述传输中设备。

20.根据权利要求1所述的方法，其中所述估算法执行至满足停止条件。

21.根据权利要求20所述的方法，其中当确定所述信号矢量的非零元素的指数集时，满足所述停止条件。

22.一种包括处理器的装置，所述处理器用于：

接收观测矢量，所述观测矢量包括对信号的观测集；

基于所述观测矢量和观测矩阵，运用压缩感知优化生成信号矢量估算；

依据稀疏化范数，确定所述信号矢量估算中特征元素的指数集，其中所述特征元素的个数至多为所述观测矢量中元素的个数；以及基于所述观测矩阵，所述观测矢量和所述信号矢量估算中特征元素的所述指数集，通过执行非欠定估算方法，生成所述信号矢量的非零元素的指数集。

23.根据权利要求22所述的装置，其中所述信号对所述信号矢量进行编码，并且所述观测矢量中元素的个数少于所述信号矢量中元素的总数。

24.根据权利要求22所述的装置，其中所述观测矢量中元素的个数大于所述信号矢量的非零元素的个数。

25.根据权利要求24所述的装置，其中所述特征元素的个数大于所述信号矢量的非零元素的个数。

26.根据权利要求22所述的装置，其中所述观测矩阵描述所述观测矢量与所述信号矢量之间的关系。

27.根据权利要求22所述的装置，其中所述非欠定估算方法是迭代线性最小均方差LMMSE估算法，其中所述处理器在所述LMMSE估算法的每次迭代中都基于所述观测矢量和迭代指数集生成信号矢量估算子集，并依据所述稀疏化范数，确定所述信号矢量估算子集中特征元素的迭代指数子集，其中在每次迭代中，所述迭代指数子集的大小都比所述迭代指数集小一个预定的步长，其中在第一迭代中，所述迭代指数集是所述信号矢量估算的特征元素的指数集，并且其中在每次逐次迭代中，所述迭代指数集都是其上一次迭代的迭代指数子集。

28.根据权利要求22所述的装置，其中所述装置包含于与多个设备进行无线通信的基站中，所述信号矢量的每个元素对应所述多个设备中的一个不同设备，所述信号矢量的每个非零元素代表所述多个设备中与所述非零元素对应的活动设备所传输的符号，所述观测矢量代表对所述活动设备所传输的所述符号的若干观测，所述观测矩阵定义与所述传输符号关联的调制签名，并且其中所述信号矢量的非零元素的指数集标识所述活动设备。

29.根据权利要求22所述的装置，其中所述特征元素的个数小于所述观测矢量的元素的个数。

30.根据权利要求22所述的装置，其中所述装置是集成电路。

说明书

用于压缩感知的非欠定估算

[0001] 相关申请的交叉引用

[0002] 本申请要求申请日为2015年1月14日、发明名称为“用于压缩感知的非欠定估算”的第14/596,680号美国专利申请的优先权，上述专利申请的全部公开内容通过引用结合至本申请中。

技术领域

[0003] 本公开涉及通讯和信号处理应用中稀疏信号的重构。

背景技术

[0004] 在数字通信和信号处理应用中，使用连续的物理现象或信号，例如电磁波来对数字信息进行编码。要将编码为连续物理信号的数字信号还原，就要以某些采样率对该连续信号进行采样。常规采样方法通常要求采样率至少等于该连续信号中最大频率的两倍，也称奈奎斯特采样率，方能可靠地重构数字信号。然而在很多应用中，处理代价是与采样率相关的，因此希望开发出技术，实现测量采样率的降低。

[0005] 如果已知或预见到数字信号是稀疏的，即指信号中很多系数都等于或几乎等于零，则以亚奈奎斯特采样率从编码后的连续信号中还原出数字信号是有可能的。这种技术就称为压缩感知(compressed sensing)。这里的稀疏性假设作为一个附加约束，以实现本问题的求解。

[0006] 从观测的欠定集合中还原出稀疏信号属于非确定性多项式时间困难(NP-hard)问题，但如果用 范数来作为稀疏化范数，则可化归为凸优化问题。已提出了若干种解决这个优化问题的算法。一些已知算法运用最小二乘法中的最小绝对收缩与选择算子(Lasso)法。两个此种已知算法包括最小角回归(LARS)和坐标下降(CD)。然而，这些算法都存在一定的局限性。第一，它们并不求解原始的压缩感知问题，因为那属于NP-hard问题。第二，由于它们对某些参数敏感，所以经过给定次数的迭代之后，所找到的未必是问题的最优解。此外，已知的迭代压缩感知算法趋向于每次迭代都增加复杂度，也就增加了实现更好地估算数字信号元素的处理代价。

[0007] 因此，依然希望开发改进的技术，使用具有更低的复杂度和处理代价的压缩感知算法来还原出稀疏信号。

发明内容

[0008] 本文所公开的实施例克服或改进了现有方法的缺陷，提供了附加能力或优点，或提供了用于产生理想结果的可选方法。

[0009] 一般的，一种常规压缩感知算法可用于得到信号矢量的潜在非零元素的子集。然后，一种非欠定估算方法例如迭代线性最小均方差优化可用于从所述潜在非零元素中找出非零元素。所述非欠定估算方法的运算强度会低于所述常规压缩感知算法，并也能够更快地求解出所述信号矢量中的非零元素。

[0010] 在一个实施例中可以从包含有观测集合的观测矢量中还原出信号矢量，该信号矢量可为稀疏信号矢量。所述信号可对具有若干非零元素的信号矢量进行编码。所述观测矢量的元素的个数可少于所述信号矢量的元素的总个数。在一个实施例中，所述观测矢量中元素的个数大于所述信号矢量的非零元素的个数。运用压缩感知优化，可基于所述观测矢量和观测矩阵生成信号矢量估算。所述观测矩阵描述所述观测矢量与所述信号矢量之间的关系。依据稀疏化范数，可确定所述信号矢量估算中特征元素的指数集。所述特征元素的个数至多为所述观测矢量中元素的个数，且在一个实施例中大于所述信号矢量中非零元素的个数。在一个实施例中，所述特征元素的个数小于所述观测矢量的元素的个数。基于所述观测矩阵、所述观测矢量和所述信号矢量估算中特征元素的所述指数集，通过执行非欠定估算方法，可生成所述信号矢量的非零元素的指数集，所述方法可以是迭代线性最小均方差优化。

[0011] 以上所提供的概要便于更好地理解下文对实施例的详细描述。这些实施例包含附加特征和优点，并且本领域普通技术人员将会理解的是，以下所述具体实施例可以在不违背所附权利要求中所提出的主题的精神和范围的同时进行修改，或以之为基础进行构建，以执行本文所提出的相同的功能，并提供相同的结果。

附图说明

[0012] 现在将参照附图，以仅为举例的方式，描述本公开的实施例。

[0013] 图1是本文所公开的实施例提供的系统的框图；

[0014] 图2是本文所公开的实施例提供的用于从欠定观测矢量中确定稀疏信号矢量的非零元素的方法流程图；

[0015] 图3是本文所公开的实施例提供的、适于在图2的方法中使用的迭代线性最小均方差优化算法的流程图；

[0016] 图4是本文所公开的实施例提供的、适用于执行图2的方法的过载通信系统的框图；

[0017] 图5是符合本文所公开的实施例的、适用于执行图2的方法的一种基站的框图；并且

[0018] 图6是本文所公开的实施例提供的、显示了示出执行图2所示方法与常规方法在标识活动设备上进行对比的仿真结果的图表。

具体实施方式

[0019] 现在将在其中运用了信号数据的压缩感知的通信和信号处理系统的上下文中描述具体实施例。不过，本领域普通技术人员将会理解的是，可应用本文所提出的原理来让实施例顺应任意对信号或数据进行压缩采样的内容。

[0020] 一般而言，数字信号x可以编码为某种具有连续信号特征的物理现象，且通过求解下列关系式，可以从对该连续信号的观测y中还原出此数字信号x：

[0021] ym×p＝Am×nxn×p                (1)

[0022] 其中，A是一个算子，可称之为“观测矩阵”，它描述了观测y与编码后的数字信号x之间的关系。在非欠定的，或换言之，完全确定或超定的系统中，即m≥n，如果算子A是满秩的，则原则上可以得到x的唯一解。不过在实际中，一般要求运用优化方法来确定所述数字信号x的估计值。

[0023] 具体而言，在观测y中的测量次数m小于数字信号x中的元素个数n时，亦即m＜n时，问题就是欠定的，且原则上不可能得到x的唯一解。不过，如果已知或预见到x是s稀疏的，意指其所包含的非零元素的个数s相对较小，使得s＜＜n，则这个附加约束使得可以实现求解。从观测的欠定集中还原出s-稀疏信号就称为压缩感知(compressed sensing)。虽然观测的次数m小于信号x中元素的个数n，并且有s＜m＜n，但由于稀疏性约束，仍有可能还原出信号x。例如，压缩感知就是一种可用于以低于奈奎斯特比率的采样率从连续信号中还原出数字信号的技术。

[0024] 要解决从线性观测的欠定集y中还原出s稀疏的矢量x的问题，可使用凸优化压缩感知算法。一些此类算法运用最小二乘法中的最小绝对收缩与选择算子(1east absolute shrinkage and selection operator，“Lasso”)法，也称无约束的基追踪去噪问题(unconstrained basis pursuit denoising problem，UBPDN)：

[0025]

[0026] 两种这样的已知算法包括最小角回归(least-angle regression，LARS)和坐标下降(coordinate descent，CD)算法。然而，这些算法都存在一定的局限性，因而依然希望提供改进的技术，使用具有更低的复杂度和处理代价的压缩感知算法来重构出稀疏信号。

[0027] 一种改进的信号还原方法可使用常规的压缩感知算法来生成信号x的估算 并要么基于对信号x中非零元素个数的先验了解，要么基于用于估算此个数的单独方法，可以选出一个有k个潜在非零元素的子集，其中k≤m，其中m是观测的次数。这样，优化问题就不再是欠定的。选出k个潜在非零元素之后，可使用不同于所述压缩感知算法的其他方法来求解这个非欠定优化问题，但现在的选择可以不受欠定系统约束的限制。具体而言，可使用非欠定估算方法，其中所述非欠定估算方法是适用于估算不欠定的方程组的解的任意方法。所述非欠定估算方法的运算强度可以低于压缩感知算法，能够更快地求解出信号x中的非零元素。在一些实施例中，所述非欠定估算方法是迭代线性最小均方差(linear minimum mean-square error，LMMSE)算法，其用于从所述k个潜在非零元素中找出非零元素。在其他实施例中，可使用其他非欠定估算方法，如迫零(Zero Forcing，ZF)法。

[0028] 鉴于以上描述，现在将参照图1描述一种运用压缩感知进行信号还原的系统100，并将参照图2描述一种使用系统100的方法200。

[0029] 如图1所示，系统100包括处理器110，其输入或接收对来自源120的信号x的观测y(步骤210)。处理器110用于执行图2所示方法200，并向接收机130输出或发送指数子集 其中标识了信号x的非零元素(步骤250)，以及也可选地，输出或发送信号估算子集 其中包含信号x的非零元素的估算的子集。

[0030] 处理器110可以在使用环境所要求或适用的设备或装置中实现。例如，处理器110可以包含在计算机中，计算机也可具有易失性存储器、非易失性存储、显示器、用户界面中的一个或多个，以及一个或多个通信接口。源120和接收机130可以分别是该计算机的方面，或可选地，在该计算机的外部。例如，源120可以包括非易失性存储，并且处理器110自该非易失性存储处接收对信号x的观测y进行编码的数据。可选地，源120可包含通信接口，并且处理器110自该通信接口处接收对信号x的观测y进行编码的信号。类似地，接收机可包含非易失性存储或通信接口，并且处理器110将所述指数子集 以及可选地，所述信号估算子集存储在所述非易失性存储中或通过所述通信接口发送。

[0031] 处理器110可以是数字信号处理器或集成电路，且/或可以包含在通用计算机，或可选地，特殊用途设备中或形成其一个方面。例如，在通信应用中，处理器110可以包含在基站、路由器、接入点、交换机、或配置用于通过可包含有线或无线网络的网络与一个或多个设备进行有线或无线通信的集线器中，或形成它们的一个方面。处理器110可以是通用处理器，其配置用于执行存储器中所编制的指令，以执行本文所述方法；或者可选地，处理器110可以是专用电路，其配置用于执行所述方法，并可以是例如专用集成电路。处理器110可包括一个或多个处理器，其配置用于协同执行指令或执行方法，或者可选地配置用于使得每个处理器执行指令的不同部分或方法的方面的不同步骤。对应地，本文所用“处理器”一词可理解为包括一个或多个处理器，可基于有关设计和性能考虑加以选择。

[0032] 处理器110可以输入或接收任意方便的形式或格式的观测y，并可输出或发送指数子集 以及可选地，以任意方便的形式或格式输出或发送信号估算子集 例如，处理器110接收数据包形式的观测y，并/或可输出或发送指数子集 以及可选地，以数据包形式输出或发送信号估算子集

[0033] 现在描述可由处理器110执行的方法200。

[0034] 一般的，观测y与信号x由下式联系：

[0035] y＝Ax+z                 (3)

[0036] 其中，A是观测矩阵，z代表噪音。如果系统是无噪的，或可以假定如此，或者噪音是可忽略的，则噪音z可以略去或设为零。观测y和信号x在理论上可以具有任意维数，从而也决定着观测矩阵A和噪音z的维数，其中所述系统可以是欠定的。为便于阐述，将假定观测y、信号x和噪音z是一维矢量，且观测矩阵A是二维矩阵，不过要理解的是，本文所提出的原理无关维数，同等适用。

[0037] 故在本方法中，信号矢量xn×1是已知为、确定为或估算为s稀疏的——换言之，信号矢量xn×1中相对较少的s＜＜n个元素是非零元素。将矢量xn×1编码而成信号，对其进行m次观测ym×1，并以之作为输入，或将其接收(步骤210)，其中有s＜m＜n，且相互联系如下：

[0038] ym×1＝Am×nxn×1+zm×1            (4)其中，Am×n是观测矩阵，且zm×1代表噪音。

[0039] 使用压缩感知优化算法，可生成信号x的估算 (步骤220)。所述压缩感知算法可以是任意常规的或尚为未知的压缩感知算法。所述压缩感知算法可以是Lasso算法，例如最小角回归算法或坐标下降算法。也可使用其他的压缩感知算法。

[0040] 基于信号估算 生成信号x的k个潜在非零元素的指数集 其中k不大于观测矢量y中观测的个数m，即k≤m。如此有：

[0041]

[0042] 如前所述，信号x具有n个元素。

[0043] k的值——即潜在非零元素的个数——的选择可以基于任意合适的基础，并可等于观测数m，比观测数小1，即m-1，或其他小于m的任意量。具体而言，k可以是基于实验或其他涉及待考察系统的任意基础而确定的设计参数。

[0044] 选定潜在非零元素的个数k之后，依据所用稀疏化范数，生成指数集 来标识信号估算 中k个特征元素(步骤230)，其中有s＜k≤m＜n。因此，如果用 范数，则信号估算 中k个特征元素可以确定为具有最大范数 的k个元素 又例如，如果用 范数作为稀疏化范数，则信号估算 中k个特征元素由子矢量 中具有最大 范数 的元素组成，并有

[0045] 指数集 从而定义了信号估算 的子矢量 其中包含的元素对应着指数集以及类似地，定义了子矩阵 其中包含的列对应着指数集 信号矢量估算 中元素的个数k不大于矩阵 中测量的次数m——换言之，有k≤m——故而优化问题就不再是欠定的，可以由不受欠定系统约束条件限制的方法求解。

[0046] 因此，基于指数集 和观测矢量y，可使用非欠定估算方法来在k个潜在非零元素中找出非零元素。在一些实施例中，所述非欠定估算方法是迭代线性最小均方差(LMMSE)法。也可使用其他非欠定估算方法。例如在其他实施例中，可以使用迫零(ZF)估算法。具体而言，所述估算法生成信号估算 的非零元素的迭代指数子集 以及元素估算 (步骤240)。在一些实施例中，选择k＜m可得到改进的LMMSE算法表现，得到更低的估算错误，即的值更小。

[0047] 现在参照附图3，更详细地描述迭代LMMSE优化算法300。在下文中：

[0048] 是 的子集，其中包含的元素对应指数集

[0049] 是A的子矩阵，其中包含的列对应指数集

[0050] Cx是信号矢量x的协方差矩阵；并且

[0051] Cz是噪音矢量z的协方差矩阵。

[0052] 在迭代LMMSE算法的初始步骤中，设为等于 (步骤310)——亦即 ——并设置迭代步长Δ(步骤320)。

[0053] 迭代步长Δ可按任意合适的基础选择。在一些实施例中，设置为Δ＝1，使得每次迭代仅消除单个潜在非零元素。可选地，Δ＞1。具体而言，迭代步长Δ可以基于任意其他优化方法选择，并可以是依照在研究中的系统，基于实验而确定的设计参数。

[0054] 选定迭代步长Δ之后，算法每次迭代都执行以下步骤。

[0055] 首先，生成单个信号估算子集 (步骤330)，其中， 且LMMSE矩阵W由下式给出：

[0056]其中， 是 的共轭转置。

[0057] 第二，依照稀疏化范数，确定 中q个特征元素(步骤340)，亦即：

[0058] 其中

[0059] 最后，更新指数子集 以标识从而确定 的q个特征元素(步骤350)，亦即[0060] 以上步骤迭代执行，直至 ——亦即，当指数子集 中的元素的个数大于信号x中非零元素个数时执行迭代——或执行迭代直至满足其他任意停止条件(决策步骤360，结束步骤370)。例如，每次迭代都可确定信号估算子集 中不定个数的一个或多个元素，而停止条件则可定义为该不定个数的阈值。可有其他可选方案。

[0061] 在噪音和信号矢量各自的元素内部无关的特例中，W化简为：

[0062]

[0063] 其中，σx与σz分别是x与z的方差，并且其中I是适当大小的单位矩阵。

[0064] 当迭代终止时，指数子集 标识了信号x中的非零元素，且信号估算子集 是信号x的非零元素的估算的子集。可输出或发送指数子集 (步骤250)。可选地，也可输出或发送信号估算子集 附加的或可选地，可还原信号x(步骤260)。例如，可基于 和 还原信号x。可选地，在指数集 中标识了信号x中的非零元素后，可用其他方法来基于观测矢量y和指数集 重构信号x。

[0065] 依照以上方法使用非欠定估算方法可改进压缩感知算法的性能。具体而言，迭代LMMSE迭代所具有的复杂度低于压缩感知迭代，包括在使用坐标下降算法时的情况。例如，LMMSE的每次迭代涉及一次矩阵乘法，而坐标下降的每次迭代涉及n次矩阵乘法，如此，LMMSEE的每次迭代的运算强度都较低。而且，每次LMMSE迭代解得的信号x的非零元素都可比每次压缩感知迭代的更完全，从而可以更低的运算代价实现更快的求解速度。

[0066] 在任意应用中，如果已知或确定x是稀疏的，并且在应用常规压缩感知算法之后，有一定的理由选择若干数量的特征元素，且其数量不少于测量次数，则可应用以上用于从观测矢量y中重构出信号矢量x的系统和方法。所述系统和方法在应用中不局限于任何具体的领域，而是可以用于任何矢量x与矢量y所分别代表的现象的关系满足方程(3)的应用。所述系统和方法可以用于通信或信号处理中的任何领域，包括有线或无线电信、图片、视频或音频处理，包括作为图片、视频或音频压缩和传输方法的一部分。

[0067] 例如，在系统和方法的一个实施例中，观测矢量y可代表通过任意方案A对稀疏数字信号矢量x进行编码而得的连续电磁信号的测量。在另一个实施例中，y可代表符合压缩方案A的压缩数据，其中x是稀疏的未压缩数据。例如，y可代表依照压缩方案A而压缩的某个表示域(可以是例如频域或小波域)内的图片、视频或音频数据的压缩表示，而x则代表在该表示域内未压缩的图片、视频或音频数据。

[0068] 发明人已发现，以上系统和方法也可用于在过载、非协同的通信系统中识别活动设备，具体如下。

[0069] 如图4所示，通信系统400中可包括若干个通信设备410，后者配置用于向基站420传输一个或多个信号。从设备410到基站420的传输可以是非协同的，意指每个设备410都可向基站420进行自主的传输，各设备410之间不做协同。例如，基站420与设备410之间可能不存在控制信道或类似物来进行通信协同。在给定时间，这些设备410中的一个或多个可能是活动设备415，意指在该时间正进行传输，并且余下的设备410可以是非活动设备412，意指在该时间未进行传输。

[0070] 例如，所述通信设备可包括一个或多个数字无线电、蜂窝电话、智能手机、平板电脑、笔记本电脑、智能电器、智能设备或任意其他具有传输能力的设备。基站配置用于接收来自通信设备的传输。例如，基站可包括处理器110和源120，其中所述源120包括基站的通信接口，用于接收来自活动设备415的传输。

[0071] 在这样的系统中，如果设备个数不大于与基站进行通信的可用信道的个数，并且每个设备都被指派到不同的信道，则基站只需观测通过哪个信道有收到信号，即可随时确定哪些设备在活动中(即传输中)。然而，在设备个数大于可用信道个数的情况下，系统就是过载的，基站也就不能按这种方式确定哪些设备在活动中。

[0072] 例如，运用了码分多址接入(CDMA)信道接入方法的通信系统通过依据代码或签名调制各个信号，从而在单个通信信道上实现多个信号的同步或异步并发传输。只要所述签名集是互为正交的，则所有信号在理论上都是可还原的。然而在实际中，互为正交的签名集在给定的条件集中数量是有限的，故而随着这种系统中进行通信的设备数量的增加，为每个新设备指派一个新签名，这就会到达一个点：所述签名集不再是完全互为正交的。这样的系统就称为“过载”。

[0073] 上述类型的过载系统符合下面的模型：

[0074] ym×p＝Am×nxn×p             (8)

[0075] 其中，矢量ym×p代表着依据编码算子Am×n，从n个设备xn×p通过m个信道所接收的p个符号。例如，在CDMA系统中，算子Am×n就代表着可供信号调制所用的n个签名，且m是签名长度。如果为n＞m个设备指派了n＞m个对应签名，而这些签名不能形成互为正交的集合，则系统就是过载的，也无法简单地通过参考信道而确定任意给定时间哪些设备正在进行传输。

[0076] 不过，如果已知或预见到在这些设备中只有相对少数的s个设备在给定时间是活动的(即传输中)，即s＜＜n，则可运用以上用于从m个观测的欠定集y中还原出s稀疏的信号x的方法，来确定该过载系统中有s个活动设备。

[0077] 故而，假定在给定时间，n个设备中有s是活动的，并且为便于阐述，假定每个设备在给定时间传输单个符号。这就是例如同步通信系统中的情况。不过，将要理解的是，本文的原则在传输的符号不止一个时也同样适用。符号可以按照任意想要的方式编码为传输信号，故而符号可以通过正交相移键控(QPSK)调制编码。于是，观测ym×1与传输符号xn×1之间的联系为：

[0078] ymm×1＝Am×nxn×1+zn×1             (9)

[0079] 其中，n是设备的个数，m是签名长度，Am×n是编码算子，且zn×1代表噪音。如果系统是或可以假定是无噪的，或者噪音是可忽略的，则zn×1可以略去或设为零。签名长度小于设备的个数，即m＜n，故系统是过载的。已知或预见到活动设备的个数s很少，即s＜＜n，并小于签名长度，即s＜m。

[0080] 因此，基于以上定义，就使得从测量的欠定集中还原出稀疏信号的系统和方法可同等地应用于确定在给定时间向基站自主传输的s＜＜n个活动设备。于是参照图5，基站500可包括可以是或可以包括处理器110的处理器510、存储器520、无线接口530和回传接口
540。基站500可通过接口连接源120和/或接收机130，或者这些可以作为基站500的方面或组件而包含其中。例如，无线接口530可以是或可以包括源120，并可配置用于接收来自设备
410的传输，并生成观测ym×1，由基站的处理器510接收。接收机130可包括用于在通过处理器
510执行方法200之后接收指数子集 (以及可选地，信号估算子集 )的任意方面或设备。
具体而言，处理器510还可配置用于基于由方法200所生成的指数子集 来从观测ym×1中还原出传输符号xn×1。

[0081] 在本方法的应用中，可将k初始设置为潜在活动设备的个数，且矢量xn×1中特征元素的指数集 可代表潜在活动设备的集合，即对应的传输符号不为零的那些设备。k的值可以基于以上进行设置，并且在本申请中也可以基于系统中n个设备的集合的任意已知系数进行设置，其表明了在给定时间处于活动中的设备个数的上限。应用此方法之后，并且具体地，在LMMSE算法的最后一次迭代之后，指数子集 标识了解码而得的符号 不为零的s个设备，并从而标识了s个活动中的设备。

[0082] 参照图6，其中显示了图表600，示出了所述活动设备标识方法的仿真结果。在仿真中，已知在拥有100个设备的设备池中有4个活动设备，但并不知道是哪几个。此仿真模拟的是4个活动设备传输以长度60的签名进行调制、采用QPSK编码的单个符号。此仿真模拟的是衰落信道，即信道干扰。对应地，参照方程(4)，在模拟中有s＝4，m＝60且n＝100，故而服从条件s＜m＜n。如图6所示，运用并对比了三个不同的优化方法610、620和630。在第一可选方案610中，使用了40次坐标下降Lasso压缩感知优化(“CD”)迭代。在第二可选方案620中，使用了100次CD迭代。在第三可选方案630中，使用了方法200，其中在步骤220使用了40次CD迭代，接着为方法200中所提出的迭代LMMSE，其中可能的活动设备的初始个数设置为k＝16，并且迭代步长设置为Δ＝1，故而得12＝16-4次LLMSE优化迭代。图表600显示了被传输符号的不同信噪比与仿真的检测错误率之间的对比结果，该仿真的检测错误率即为实验中任意检测错误的比率。如图表600中所清楚显示的，代表方法200结果的可选方案630与单用CD的可选方案610、620相比，在所有信噪比之下始终产生较低的检测错误率，即便第二可选方案620中所用的CD迭代次数较大也依然如此。

[0083] 在另一个实施例中，编码有可由处理器执行的指令的非易失性计算机可读介质可以执行如下的方法。在处理器处接收到观测矢量，所述观测矢量包括一个编码有信号矢量的对信号的观测集，所述信号矢量可为稀疏信号矢量。所述信号矢量具有一定个数的非零元素。所述观测矢量的元素的个数少于所述信号矢量的元素的总个数。在一些实施例中，并且在一些实施例中也大于所述信号矢量的非零元素的个数。基于所述观测矢量和观测矩阵，所述处理器运用压缩感知优化生成信号矢量估算，所述观测矩阵描述所述观测矢量与所述信号矢量之间的关系。依据稀疏化范数，所述处理器确定所述信号矢量估算中特征元素的指数集，其中所述特征元素的个数至多等于所述观测矢量中元素的个数，并且在一些实施例中也大于所述信号矢量中非零元素的个数。基于所述观测矩阵、所述观测矢量和所述信号矢量估算中特征元素的所述指数集，所述处理器通过执行非欠定估算方法，例如迭代LMMSE优化算法，生成所述信号矢量的非零元素的指数集。

[0084] 在前文的描述中，为了更好地解释，列出了大量细节，以求提供对实施例的透彻理解。然而，对本领域技术人员而言显而易见的是，这些特定细节并非必需。在其他实例中，公知的电气结构和电路以框图显示，以免妨碍理解。例如，特定细节并未提供，如本文所描述的实施例是否采用软件程序、硬件电路、固件还是它们的组合来实现。

[0085] 本公开的实施例可以表现为存储在有形的机器可读介质中的计算机程序产品(也称为内有计算机可读程序代码的计算机可读介质、处理器可读介质或计算机可用介质)。所述机器可读介质可以是任意合适的、有形的非暂时性介质，包括磁、光或电储存介质，包括磁盘、光盘只读存储器(CD-ROM)、存储装置(易失性或非易失性)、USB快闪磁盘或类似的储存机构。所述机器可读介质可以容纳各种指令集、代码序列、配置信息或其他数据，当这些得到执行时，会使得处理器执行符合本公开的实施例的方法中的步骤。本领域普通技术人员将要理解的是，所述机器可读介质上也可存储实施所述实施方式所必需的其他指令和操作。所述机器可读介质上所存储的指令可由处理器或其他合适的处理装置执行，并可与电路接口，以执行所述任务。

[0086] 上述实施例仅旨在示例。本领域普通技术人员可对具体实施例进行替换、修改和变形。权利要求的范围不应局限于本文所列具体实施例，而应以符合本说明书整体的方式加以解读。