本发明涉及通信技术， 尤其涉及一种基于压缩感知的信号重建方法及 装 置。 背景技术

在传统的信号处理理论中， 依据香农采样定理： 用于采集信号的采样速 率应至少等于两倍信号带宽才可以无失真地恢 复原信号， 并将该采样速率称 为奈奎斯特 （Nyquist) 采样速率。 但是， 随着当今对数据量的需求以及待处 理数据量的飞速增长， 承载数据的信号带宽将越来越宽， 导致所需的奈奎斯 特采样速率也越来越高， 而现有硬件设备的模数转换和信号处理能力尚 无法 满足对宽带信号需求的高速增长。 而且， 从另一个方面考虑， 即便未来硬件 实现水平得以大幅提高， 高能耗的海量数据采集也不是必不可少的。 以现有 的图像信号处理为例， 为降低存储和传输开销， 通常将采样后获得的数据进 行压缩， 以很少的数据表示图像中的重要信息， 即仅保留重要数据而丢弃其 余的非重要数据， 经存储或传输后再通过译码处理重建原有图像 。 这种先高 速采样再压缩丢弃的方法实际上造成了采样资 源的极大浪费。

为将采样和压缩合二为一同时进行，即直接以 低于 Nyquist的采样速率来 采集数据， 提出了压缩感知 （Compressive Sensing , 简称 CS ) 技术。 在 CS 技术中， 根据低速采样过程后获得的采样数据 （即降维的采样信号） 来重建 原始输入信息 （即高维的原始输入信号） ， 这一过程称为压缩感知的信号重 建过程。 CS信号重建方法主要包括贪婪搜索类方法， 该类方法最常用的子类 为正交匹配追踪 （Orthogonal Matching Pursuit, 简称 OMP ) ， 但是该类方法 信号重建的准确行不高。

现有技术中， 提出了 K-best-OMP信号重建方法来提高 CS信号重建的准 确性， K-best-OMP信号重建方法中， 每次迭代均搜索固定的 K条路径， 且保 留所有 K条路径， 并在每条路径的基础上再扩展 K条新的子搜索路径， 即共 条搜索路径，然后在 条搜索路径中保留满足条件的 K条路径，再进行新 一轮次的路径扩展， 直到迭代停止。

但是， 采用现有技术进行 CS信号重建， 复杂度高， 不易实现。 发明内容

本发明实施例提供一种基于压缩感知的信号重 建方法及装置， 用于解决 现有 CS信号重建复杂度高的问题。

本发明实施例第一方面提供一种基于压缩感知 的信号重建装置， 包 括：

计算模块， 用于计算残差向量与处理矩阵中所有列向量的 内积值； 确定模块， 用于确定出所述内积值中的最大内积值； 根据所述最大内积 值、 内积门限因子以及预设最大搜索路径数， 确定迭代中的搜索路径个数； 筛选模块， 用于在所述处理矩阵的所有列向量中， 按照所述内积值从大 到小依次挑选出对应的与所述搜索路径个数相 同个数的列向量；

更新模块， 用于根据所述与所述搜索路径个数相同个数的 列向量的索引 位置， 依次更新各搜索路径的索引集合， 获取更新后的索引集合；

迭代模块， 用于根据所述更新后的索引集合， 对各条搜索路径分别进行 迭代更新操作， 获取更新的残差向量。

结合第一方面， 在第一方面的第一种可能的实施方式中， 所述确定模 块， 具体用于根据所述最大内积值和内积门限因子 确定出内积门限值； 统 计出所有所述内积值中大于所述内积门限值的 内积值个数； 比较所述大于 所述内积门限值的内积值个数和所述预设最大 搜索路径数的大小， 将其中 较小的数值作为迭代中的搜索路径个数。

结合第一方面， 在第二方面的第二种可能的实施方式中， 所述计算模 块， 还用于在所述迭代更新操作为非首次迭代更新 操作时， 在根据所述更 新后的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的残 差向量之后， 计算所有所述搜索路径上所述更新的残差向量 的二范数， 并 确定所有所述二范数中的最小二范数；

所述确定模块， 还用于根据所述最小二范数、 二范数门限因子、 最大 搜索路径， 确定迭代中的搜索路径保留个数； 在所述搜索路径中， 按照所 述二范数从小到大保留与所述搜索路径保留个 数相同个数的搜索路径， 作 为保留搜索路径； 在所述迭代更新操作的次数等于预设参数信号 稀疏度 时， 从所述保留搜索路径中筛选出对应的所述二范 数最小的搜索路径， 并 将所述二范数最小的搜索路径所对应的迭代更 新信号作为重建信号。

结合第一方面， 在第二方面的第三种可能的实施方式中， 所述装置还 包括： 检查模块； 所述检查模块， 用于在迭代更新操作为非首次迭代更新 操作时， 在根据所述与所述搜索路径个数相同个数的列 向量的索引位置， 依次更新各搜索路径的索引集合， 获取更新后的索引集合之后， 检查所有 所述搜索路径的所述索引集合， 判断是否存在重复路径， 若存在， 则将重 复路径删除， 并根据删除后剩余的搜索路径再次更新索引集 合， 获取二次 更新的索引集合。

本发明实施例第二方面提供一种基于压缩感知 的信号重建方法， 包 括：

计算残差向量与处理矩阵中所有列向量的内积 值；

确定出所述内积值中的最大内积值；

根据所述最大内积值、 内积门限因子以及预设最大搜索路径数， 确定 迭代中的搜索路径个数；

在所述处理矩阵的所有列向量中， 按照所述内积值从大到小依次挑选 出对应的与所述搜索路径个数相同个数的列向 量；

根据所述与所述搜索路径个数相同个数的列向 量的索引位置， 依次更 新各搜索路径的索引集合， 获取更新后的索引集合；

根据所述更新后的索引集合， 对各条搜索路径分别进行迭代更新操 作， 获取更新的残差向量。

结合第二方面， 在第二方面的第一种可能的实施方式中， 所述根据所 述最大内积值、 内积门限因子以及预设最大搜索路径数， 确定迭代中的搜 索路径个数， 包括：

根据所述最大内积值和内积门限因子确定出内 积门限值；

统计出所有所述内积值中大于所述内积门限值 的内积值个数； 比较所述大于所述内积门限值的内积值个数和 所述预设最大搜索路 径数的大小， 将其中较小的数值作为迭代中的搜索路径个数 。

结合第二方面， 在第二方面的第二种可能的实施方式中， 所述迭代更 新操作为非首次迭代更新操作， 相应地，

所述根据所述更新后的索引集合， 对各条搜索路径分别进行迭代更新 操作， 获取更新的残差向量之后， 还包括：

计算所有所述搜索路径上所述更新的残差向量 的二范数， 并确定所有 所述二范数中的最小二范数；

根据所述最小二范数、 二范数门限因子、 最大搜索路径， 确定迭代中 的搜索路径保留个数；

在所述搜索路径中， 按照所述二范数从小到大保留与所述搜索路径 保 留个数相同个数的对应搜索路径， 作为保留搜索路径；

若所述迭代更新操作的次数等于预设参数信号 稀疏度， 则从所述保留 搜索路径中筛选出对应的所述二范数最小的搜 索路径， 并将所述二范数最 小的搜索路径所对应的迭代更新信号作为重建 信号。

结合第二方面， 在第二方面的第三种可能的实施方式中， 所述迭代更 新操作为非首次迭代更新操作， 相应地，

所述根据所述与所述搜索路径个数相同个数的 列向量的索引位置， 依 次更新各搜索路径的索引集合， 获取更新后的索引集合之后， 还包括： 检查所有所述搜索路径的所述索引集合， 判断是否存在重复路径， 若 存在， 则将重复路径删除， 再次更新搜索路径以及索引集合， 获取二次更 新的搜索路径和索引集合。

本发明实施例第三方面提供一种基于压缩感知 的信号重建装置， 包 括：

存储器， 用于存储指令；

处理器， 与所述存储器耦合， 被配置为执行存储在所述存储器中的指 令， 用于计算残差向量与处理矩阵中所有列向量的 内积值； 确定出所述内 积值中的最大内积值； 根据所述最大内积值、 内积门限因子以及预设最大 搜索路径数， 确定迭代中的搜索路径个数； 在所述处理矩阵的所有列向量 中， 按照所述内积值从大到小依次挑选出对应的与 所述搜索路径个数相同 个数的列向量； 根据所述与所述搜索路径个数相同个数的列向 量的索引位 置， 依次更新各搜索路径的索引集合， 获取更新后的索引集合； 根据所述 更新后的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的 残差向量。

结合第三方面，在第三方面的第一种可能的实 施方式中，所述处理器， 具体用于根据所述最大内积值和内积门限因子 确定出内积门限值； 统计出 所有所述内积值中大于所述内积门限值的内积 值个数； 比较所述大于所述 内积门限值的内积值个数和所述预设最大搜索 路径数的大小， 将其中较小 的数值作为迭代中的搜索路径个数。

结合第三方面，在第三方面的第二种可能的实 施方式中，所述处理器， 还用于在所述迭代更新操作为非首次迭代更新 操作时， 在根据所述更新后 的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的残差向 量之后， 计算所有所述搜索路径上所述更新的残差向量 的二范数， 并确定 所有所述二范数中的最小二范数；根据所述最 小二范数、二范数门限因子、 最大搜索路径， 确定迭代中的搜索路径保留个数； 在所述搜索路径中， 按 照所述二范数从小到大保留与所述搜索路径保 留个数相同个数的搜索路 径， 作为保留搜索路径； 在所述迭代更新操作的次数等于预设参数信号 稀 疏度时， 从所述保留搜索路径中筛选出对应的所述二范 数最小的搜索路 径， 并将所述二范数最小的搜索路径所对应的迭代 更新信号作为重建信 号。

结合第三方面，在第三方面的第三种可能的实 施方式中，所述处理器， 还用于在迭代更新操作为非首次迭代更新操作 时， 在根据所述与所述搜索 路径个数相同个数的列向量的索引位置， 依次更新各搜索路径的索引集 合，获取更新后的索引集合之后，检查所有所 述搜索路径的所述索引集合， 判断是否存在重复路径， 若存在， 则将重复路径删除， 并根据删除后剩余 的搜索路径再次更新索引集合， 获取二次更新的索引集合。

本发明实施例中， 根据所述最大内积值、 内积门限因子以及预设最大 搜索路径数， 确定迭代中的搜索路径个数， 即对搜索路径进行的筛选， 并 根据确定的搜索路径个数确定索引集合， 因此后续迭代更新的处理对象减 少， 工作量和复杂度也就大大降低。 附图说明

为了更清楚地说明本发明实施例或现有技术中 的技术方案， 下面将对 实施例或现有技术描述中所需要使用的附图作 一简单地介绍， 显而易见 地， 下面描述中的附图是本发明的一些实施例， 对于本领域普通技术人员 来讲， 在不付出创造性劳动性的前提下， 还可以根据这些附图获得其他的 附图。

图 1 为本发明提供的基于压缩感知的信号重建装置 实施例一的结构示意 图；

图 2为本发明提供的基于压缩感知的信号重建装� �实施例二的结构示意 图；

图 3为本发明提供的基于压缩感知的信号重建方� �实施例一的流程示意 图；

图 4为本发明提供的基于压缩感知的信号重建方� �实施例二的流程示意 图；

图 5为本发明提供的基于压缩感知的信号重建装� �实施例三的结构示意 图。 具体实施方式 为使本发明实施例的目的、 技术方案和优点更加清楚， 下面将结合本 发明实施例中的附图， 对本发明实施例中的技术方案进行清楚、 完整地描 述， 显然，所描述的实施例是本发明一部分实施例 ， 而不是全部的实施例。 基于本发明中的实施例， 本领域普通技术人员在没有作出创造性劳动前 提 下所获得的所有其他实施例， 都属于本发明保护的范围。

图 1为本发明提供的基于压缩感知的信号重建装� �实施例一的结构示意 图， 如图 1所示， 该装置包括： 计算模块 101、 确定模块 102、 筛选模块 103、 更新模块 104和迭代模块 105， 其中：

计算模块 101， 用于计算残差向量与处理矩阵中所有列向量的 内积值。 该残差向量可以是初始化残差向量， 也可以指后续迭代过程中的残差向量。 ， 以初始化残差向量为例， 记为 r ^[ ° ^] ， 上角标中的 0表示初始化。 r ^[ ° ^] 与处理矩阵 A的每一个列向量逐一进行内积计算， 表示为〈 ,4〉 ， 其中， A„表示处 理矩阵 A的第 n歹 U， 该处理矩阵 A—共有 N列， n可以为 1,2,...,N， 〈〉表示 内积操作。 最后得到 N个内积值。 确定模块 102， 用于确定出上述内积值中的最大内积值； 并根据最大 内积值、 内积门限因子以及预设最大搜索路径数， 确定迭代中的搜索路径 个数。

筛选模块 103， 用于在上述处理矩阵的所有列向量中， 按照上述内积 值从大到小依次挑选出对应的与上述搜索路径 个数相同个数的列向量。

更新模块 104， 用于根据上述与上述搜索路径个数相同个数的 列向量 的索引位置， 依次更新各搜索路径的索引集合， 获取更新后的索引集合。

迭代模块 105， 用于根据上述更新后的索引集合， 对各条搜索路径分 别进行迭代更新操作， 获取更新的残差向量。

本实施例中， 根据所述最大内积值、 内积门限因子以及预设最大搜索 路径数， 确定迭代中的搜索路径个数， 即对搜索路径进行的筛选， 并根据 确定的搜索路径个数确定索引集合， 因此后续迭代更新的处理对象减少， 工作量和复杂度也就大大降低。且根据实验表 明采用本发明实施例的方法 获得的重建信号准确度很高。

进一步地， 确定模块 102， 具体用于根据所述最大内积值和内积门限因 子确定出内积门限值； 统计出所有所述内积值中大于所述内积门限值 的内 积值个数； 比较所述大于所述内积门限值的内积值个数和 所述预设最大搜 索路径数的大小， 将其中较小的数值作为迭代中的搜索路径个数 。

计算模块 101， 还用于在所述迭代更新操作为非首次迭代更新 操作时， 在根据所述更新后的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的残差向量之后， 计算所有所述搜索路径上所述更新的残差向量 的二范数，并确定所有所述二范数中的最小二 范数。相应地，确定模块 102， 还用于根据所述最小二范数、 二范数门限因子、 最大搜索路径， 确定迭代 中的搜索路径保留个数； 在所述搜索路径中， 按照所述二范数从小到大保 留与所述搜索路径保留个数相同个数的搜索路 径， 作为保留搜索路径； 在 所述迭代更新操作的次数等于预设参数信号稀 疏度时， 从所述保留搜索路 径中筛选出对应的所述二范数最小的搜索路径 ， 并将所述二范数最小的搜 索路径所对应的迭代更新信号作为重建信号。

图 2为本发明提供的基于压缩感知的信号重建装� �实施例二的结构示意 图， 如图 2所示， 在图 1的基础上， 该装置还包括： 检查模块 106， 用于在 迭代更新操作为非首次迭代更新操作时， 在根据所述与所述搜索路径个数 相同个数的列向量的索引位置， 依次更新各搜索路径的索引集合， 获取更 新后的索引集合之后， 检查所有所述搜索路径的所述索引集合， 判断是否 存在重复路径， 若存在， 则将重复路径删除， 并根据删除后剩余的搜索路 径再次更新索引集合， 获取二次更新的索引集合。

该装置用于执行下述方法实施例。

图 3为本发明提供的基于压缩感知的信号重建方� �实施例一的流程示意 图， 如图 3所示， 该方法包括：

S301、 计算残差向量与处理矩阵中所有列向量的内积 值。

该残差向量可以是初始化残差向量， 也可以指后续迭代过程中的残差向 量， 以初始化残差向量为例， 记为 r ^[ ° ^] ， 上角标中的 0表示初始化。 r ^[ ° ^] 与处理 矩阵 A的每一个列向量逐一进行内积计算， 表示为〈 \ ,4 ⁿ 〉 I ， 其中， 表 示处理矩阵 A的第 n列， 该处理矩阵 A—共有 N列， n可以为 1,2,..., N, ( > 表示内积操作。 最后得到 N个内积值。

5302、 确定出上述内积值中的最大内积值。 从上述 N各内积值中选出最 大的一个， 记为 v ^[1] = ma _X ( [〈 , 〉])， 上标 1表示是首次进行的步骤。

5303、 根据上述最大内积值、 内积门限因子以及预设最大搜索路径数， 确定迭代中的搜索路径个数。

S304、 在上述处理矩阵的所有列向量中， 按照上述内积值从大到小依次 挑选出对应的与上述搜索路径个数相同个数的 列向量。

假设首次确定的搜索路径个数为 ^1] ， 那么在上述处理矩阵 Α 中， 按照 上述 N个内积值从大到小挑选出对应的 ^个列向量。

S305、 根据与上述搜索路径个数相同个数的列向量的 索引位置， 依次更 新各搜索路径的索引集合， 获取更新后的索引集合。

与上述搜索路径个数相同个数的列向量的索引 位置， 即这些列向量的编 号， 将 ^ ^[1] 个索引位置逐一更新到 个索引集合中， 得到 ^ ^[1] 个更新后的索引 集合 {Ω ， 下标 k表示第 k条搜索路径， 其中 fc = l,2,..., ^ ^1] ， 即将每个索引位 置对应添加到其相应的搜索路径的索引集合中 。

S306、根据更新后的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的残差向量。

以第 k条搜索路径为例， 先根据该搜索路径的索引集合 {Ω ， 来获取迭 代更新信号向量^，该迭代更新过程可表示为� �式^ A y，其中 y为预先输入的采样信号向量， A为预先输入的处理矩阵， A 为处理矩阵 A 中由索引集合 {Ω 所包含的索引位置所对应的列向量组成的矩阵 ， 为 A 的共轭转置矩阵， （Α^ Α _Ω 为 Α _Ω 的逆矩阵。然后根据 ^进行残差向量更 新， 具体可以根据公式 i = y-A 计算获取更新的残差向量 i 。 进一步地采用更新后的残差向量进入到下一次 迭代循环中， 直到最后获 取重建信号， 下文再详细介绍。

本实施例中， 根据所述最大内积值、 内积门限因子以及预设最大搜索 路径数， 确定迭代中的搜索路径个数， 即对搜索路径进行的筛选， 并根据 确定的搜索路径个数确定索引集合， 因此后续迭代更新的处理对象减少， 工作量和复杂度也就大大降低。且根据实验表 明采用本发明实施例的方法 获得的重建信号准确度很高。

上述根据上述最大内积值、 内积门限因子以及最大搜索路径数， 确定迭 代中的搜索路径个数， 具体为： 根据上述最大内积值和内积门限因子确定出 内积门限值； 统计出所有上述内积值中大于该内积门限值的 内积值个数； 比 较上述大于上述内积门限值的内积值个数和上 述预设最大搜索路径数的大 小， 将其中较小的数值作为迭代中的搜索路径个数 。

仍以首次迭代过程为例， 将上述最大内积值 max /" ^[ ° „ 和内积门 限因子《相乘的乘积作为内积门限值， 并统计出上述所有内积值大于该内积 门限值的内积值的个数 ， 比较; 7 ^[1] 和 K 的大小， 将比较小的那个数值作为 首次迭代中的搜索路径个数。 其中; 7 ^[1] 可以采用公式 = {[< r ^[0] ,A >] > v ^m a 此处 {[ < r ^[0] ,A >1 > v ^[1] a ；集合 {[ < r ^[0] ,A >1 > v ^[1] a 中元素的个数 ₍ 进一步地， 如果迭代更新操作为非首次迭代更新操作， 那么， 上述根据 与上述搜索路径个数相同个数的列向量的索引 位置， 依次更新各搜索路径的 索引集合， 获取更新后的索引集合之后， 还可以检查所有搜索路径的索引集 合， 判断是否存在重复路径， 若存在， 则将重复路径删除， 并根据删除后剩 余的搜索路径更新搜索集合， 获取二次更新的索引集合。 这样进行筛选后， 可以避免后续迭代操作时进行不必要的计算， 以降低复杂度。

对于迭代更新操作为非首次迭代更新操作， 根据更新后的索引集合， 对 各条搜索路径分别进行迭代更新操作， 获取更新的残差向量之后， 还包括： 计算所有搜索路径上上述更新的残差向量的二 范数， 并确定所有二范数中的 最小二范数； 根据该最小二范数、 二范数门限因子、 最大搜索路径， 确定迭 代中的搜索路径保留个数； 在搜索路径中， 按照上述二范数从小到大保留与 上述搜索路径保留个数相同个数的对应搜索路 径， 作为保留搜索路径； 若上 述迭代更新操作的次数等于预设参数信号稀疏 度 S , 则从上述保留搜索路径 中筛选出对应的上述二范数最小的搜索路径， 并将该二范数最小的搜索路径 所对应的迭代更新信号作为重建信号。

图 4为本发明提供的基于压缩感知的信号重建方� �实施例二的流程示意 图， 如图 4所示， 本发明实施例提供的信号重建方法整个过程包 括：

5401、 接收输入的数据和参数。 具体地， 可以由用户人工输入， 或者由 其它设备导入。 上述数据包括： 采样信号 （记为 y， y是一个向量） 、 处理矩 阵 （记为 ； 上述参数包括： 预设信号稀疏度 （记为 、 预设最大搜索路 径数 (记为 J 、 内积门限因子 （记为"） 以及二范数门限因子 （记为 。

5402、 初始化残差向量和索引集合。 其中， 初始化残差向量， 就是将残 差向量的初始值赋值为上述输入的采样信号， 即 r ^[ ° ^] = _{y ;} 初始化索引集合， 就是将索引集合的初始值赋值为空集， 即 Ω = 0。

S403、 求初始残差向量和处理矩阵中所有列向量的内 积值。 即通过公式

(r ^[01 , A ) 求得 N个内积值。 S404、 在上述内积值中确定出最大内积值。 将该最大内积值记为

S405、 根据上述最大内积值、 内积门限因子以及预设最大搜索路径数， 确定首次迭代中的搜索路径个数。 具体地， 将 V (r ^[0] , A ) 和《的乘积 作为内积门限值， 并确定上述 Ν各内积值中大于该内积门限值的个数 ;/ ^[1] ， 将 和 中较小的那个作为首次迭代中的搜索路径个数 ， 并记为 ^[1] ， 即 Κ ^ί1] = Ώΐιη (η ^ί1] , κ)。

5406、 从上述处理矩阵的所有向量中， 按照上述内积值从大到小依次挑 选出对应的与上述首次迭代中的搜索路径个数 相同个数的列向量。 具体地， 在处理矩阵 A中挑选出 ^ ^1] 个对应内积值较大的列向量。

5407、 根据上述挑选出的列向量的索引位置， 依次更新各搜索路径的索 引集合。上述挑选出的列向量的索引位置即各 列向量的对应位置编号。将 ^1] 个索引位置逐一更新到 ^ ^[1] 个索引集合中， 得到 ^1] 个更新后的索引集合 {Ω ， 下标 k表示第 k条搜索路径， 其中 = 1,υ ^[1] 。

5408、根据更新后的索引集合， 对各条搜索路径分别进行迭代更新操作， 获取更新的残差向量。 采用前述实施例的方法， 每条搜索路径都获取更新的 残差向量 i 。

5409、 在每一条搜索路径中， 采用上述更新后的残差向量， 求更新后的 残差向量与上述处理矩阵所有列向量的内积值 。 即通过公式〈ιΤ ^1] ,Α^ _ 求 得 N个内积值。 s表示本次迭代的次数（即表示当前为第 s次迭代） ， -"表 示上次迭代更新后获得的残差向量； 下标 k表示在第 k条路径中。

需要说明的是， 每条路径中平行进行， 互不干扰， 下述方法中同理。 S410、 在上述每一条搜索路径中， 在上述内积值中确定出最大内积值。 将该最大内积值记为 v ^s] = 。

s表示本次迭代的次数 （即表示当 前为第 S次迭代）

S411、 根据上述最大内积值、 内积门限因子以及预设最大搜索路径数， 确定本次迭代中的每条搜索路径下的子搜索路 径个数。 具体地， 将 v _k = max — - ^1] ,4〉])和 "的乘积作为内积门限值， 并确定上述 N各内积值中 大于该内积门限值的个数;^， 其中；^ = {[<r ^] ,A„ >] > v^a) 将 和^中较 小的那个作为本次迭代中的子搜索路径个数， 并记为 ^s] ， ^s] =min(;^, 。

S412、 从上述处理矩阵的所有向量中， 按照上述内积值从大到小依次挑 选出对应的与上述子搜索路径个数相同个数的 列向量。即在每条搜索路径中， 从上述处理矩阵 A中挑选出 ^s] 个对应内积值较大的列向量。

S413、 根据上述挑选出的列向量的索引位置， 依次更新各搜索路径的索 引集合。 即将 ^个索引位置逐一更新到 个索引集合中， 得到 ^s] 个更新 后的索引集合 {Ω _Α ,.}.， j = l,2,...,K _k ^[s

5414、 检查所有搜索路径中当前索引集合， 判断是否存在重复路径， 若 存在， 则删除重复路径， 并返回执行 S413, 即根据删除后剩余的搜索路径再 次索引集合； 若不存在， 则执行 S415。

5415、 根据更新后的索引集合， 对各条子搜索路径分别进行各自的迭代 更新操作， 获取更新的残差向量。

以第 k条路径的第 j条子搜索路径为例， 首先， 根据索引集合 {Ω^.}.， 来 获取迭代更新信号向量 ， 其中 =(Α^Α ·)— ¹ A^.y， A _ntj 为处理矩阵 A 中由索引集合 {Ω^.}.所包含的索引位置所对应的列向量组成� �矩。 然后根据 进行残差向量更新， 本次更新的残差向量为 = - ^A n ^[ nl。

5416、 计算所有搜索路径上上述更新的残差向量的二 范数， 并确定所有 二范数中的最小二范数。 该最小二范数记为^

的二范数。 需要说明的是， 所有搜索路径包括上述所有搜索路径以及每 一条搜索路径下的每一条子搜索路径。

S417、 根据该最小二范数、 二范数门限因子、 最大搜索路径， 确定迭代 中的搜索路径保留个数。 具体地， 将 ^] = min | 和 的比值作为二范数 门限值， 从上述二范数中确定出小于等于该二范数门限 值的二范数个数 ^[5] ， 即 1 ^[ 然后将 ^和 K 中的较小值作为本次迭代中的搜索路

径保留个数， 记为 t/ ^[s] ， ί/ ^Μ = ηιίη( ^] ,^ί：)。

5418、 在上述所有搜索路径中， 按照上述二范数从小到大保留与上述搜 索路径保留个数相同个数的搜索路径， 作为保留搜索路径。 即在所有搜索路 径中， 按照二范数从小到大保留 t/ ^[s] 条搜索路径作为保留搜索路径。

5419、 判断是否满足迭代停止条件， 若是， 则执行 S420; 若否， 则返回 执行 S409。 返回执行 S409时， 采用 S415中更新的残差向量。

其中， 判断是否满足迭代停止条件， 具体为， 判断当前已进行的迭代更 新次数是否等于预设信号稀疏度 S， 表示不满足迭代停止条件； s = S表 示满足迭代停止条件。

5420、从上述保留搜索路径中筛选出对应的上� �二范数最小的搜索路径， 并将该二范数最小的搜索路径所对应的迭代更 新信号作为重建信号。

上述对应的上述二范数最小的搜索路径可表示 为 = ar _g mi _n [S] arg min [S] 为获取对应的上述二范数最小的搜索路径的标 识， 该条搜索路 径所对应的迭代更新信号作为最终的重建信号 δ ， 具体为

0[ ^s] ,when e Ω

Θ, =

0, when i i. Ω- 本实施例中， 通过 S405、 S411、 S414、 S417 依次对后续步骤的工作对 象进行筛选， 使得后续步骤的工作量逐步减少， 以使整个信号重建过程的复 杂度大大降低。 且根据大量实验数据表明， 本发明实施例提供的方法得到的 重建信号准确度也可以得到保证。 图 5为本发明提供的基于压缩感知的信号重建装� �实施例三的结构示意 图， 如图 5所示， 该装置包括： 存储器 501和处理器 502， 其中：

存储器 501， 用于存储指令； 处理器 502， 与存储器 501耦合， 被配 置为执行存储在存储器 501中的指令， 用于计算残差向量与处理矩阵中所 有列向量的内积值； 确定出所述内积值中的最大内积值； 根据所述最大内 积值、 内积门限因子以及预设最大搜索路径数， 确定迭代中的搜索路径个 数； 在所述处理矩阵的所有列向量中， 按照所述内积值从大到小依次挑选 出对应的与所述搜索路径个数相同个数的列向 量； 根据所述与所述搜索路 径个数相同个数的列向量的索引位置， 依次更新各搜索路径的索引集合， 获取更新后的索引集合； 根据所述更新后的索引集合， 对各条搜索路径分 别进行迭代更新操作， 获取更新的残差向量。

进一步地， 处理器 502， 具体用于根据所述最大内积值和内积门限因 子确定出内积门限值； 统计出所有所述内积值中大于所述内积门限值 的内 积值个数； 比较所述大于所述内积门限值的内积值个数和 所述预设最大搜 索路径数的大小， 将其中较小的数值作为迭代中的搜索路径个数 。

具体实现过程中， 处理器 502， 还用于在所述迭代更新操作为非首次 迭代更新操作时， 在根据所述更新后的索引集合， 对各条搜索路径分别进 行迭代更新操作， 获取更新的残差向量之后， 计算所有所述搜索路径上所 述更新的残差向量的二范数， 并确定所有所述二范数中的最小二范数； 根 据所述最小二范数、 二范数门限因子、 最大搜索路径， 确定迭代中的搜索 路径保留个数； 在所述搜索路径中， 按照所述二范数从小到大保留与所述 搜索路径保留个数相同个数的搜索路径， 作为保留搜索路径； 在所述迭代 更新操作的次数等于预设参数信号稀疏度时， 从所述保留搜索路径中筛选 出对应的所述二范数最小的搜索路径， 并将所述二范数最小的搜索路径所 对应的迭代更新信号作为重建信号。

更进一步地， 处理器 502， 还用于在迭代更新操作为非首次迭代更新操 作时， 在根据所述与所述搜索路径个数相同个数的列 向量的索引位置， 依 次更新各搜索路径的索引集合， 获取更新后的索引集合之后， 检查所有所 述搜索路径的所述索引集合， 判断是否存在重复路径， 若存在， 则将重复 路径删除， 并根据删除后剩余的搜索路径再次更新索引集 合， 获取二次更 新的索引集合。

本领域普通技术人员可以理解： 实现上述方法实施例的全部或部分步骤 可以通过程序指令相关的硬件来完成， 前述的程序可以存储于一计算机可读 取存储介质中， 该程序在执行时， 执行包括上述方法实施例的步骤； 而前述 的存储介质包括： ROM、 RAM, 磁碟或者光盘等各种可以存储程序代码的介 质。

最后应说明的是： 以上各实施例仅用以说明本发明的技术方案， 而非对 其限制； 尽管参照前述各实施例对本发明进行了详细的 说明， 本领域的普通 技术人员应当理解：其依然可以对前述各实施 例所记载的技术方案进行修改， 或者对其中部分或者全部技术特征进行等同替 换； 而这些修改或者替换， 并 不使相应技术方案的本质脱离本发明各实施例 技术方案的范围。