计算复杂度

摘要： 近年来,基于联合训练的深度聚类方法,如DEC(Deep Embedding Clustering)和DDC(Deep Denoising Clustering)算法,使基于特征提取的图像聚类取得了很多新进展,带来了聚类性能的突破,而且特征提取环节对后续聚类任务有直接影响。但是,这些方法的泛化能力较差,在不同数据集使用不同的网络结构,聚类性能相比分类性能仍有很大的提升空间。为此,文中提出了一种基于自注意力的自监督深度聚类方法(Self-attention Based Self-supervised Deep Clustering,SADC)。首先设计一个深度卷积自编码器用于提取特征,并且用带噪声的输入数据训练该网络来增强模型的鲁棒性;其次引入自注意力机制,辅助网络捕获对聚类有用的信息;最后编码器部分结合K-means算法形成一个深度聚类器,用于进行特征表示和聚类分配,通过迭代更新网络参数来提高聚类精度和网络的泛化能力。在6个图像数据集上验证所提聚类算法的性能,并与深度聚类算法DEC,DDC等进行比较。实验结果表明,SADC能提供令人满意的聚类结果,而且聚类性能与DEC和DDC相当。总之,统一的网络结构在保证聚类精度的同时降低了深度聚类算法的复杂度。

摘要： 迭代学习模型预测控制(Iterative learning model predictive control,ILMPC)具备较强的批次学习能力及突出的时域跟踪性能,在批次过程控制中发挥了重要作用.然而对于具有强非线性的快动态批次过程,传统的迭代学习模型预测控制很难实现计算效率与跟踪精度之间的平衡,这给其应用带来了挑战.对此本文提出一种高效迭代学习预测函数控制策略,将原非线性系统沿参考轨迹线性化得到二维跟踪误差预测模型,并在控制器设计中补偿所产生的线性化误差,构造优化目标函数为真实跟踪误差的上界.为加强优化计算效率,在时域上结合预测函数控制以降低待优化变量维数,从而有效降低计算负担.结合终端约束集理论,分析了迭代学习预测函数控制的时域稳定性及迭代收敛性.通过对无人车和典型快速间歇反应器的仿真实验验证所提出算法的有效性.

摘要： 矩阵组常用于无线通信中的数据表示。在多输入多输出(Multiple⁃Input Multiple⁃Output,MIMO)通信模型中,基站利用信道数据设计适应信道的最小均方误差(Minimum Mean Square Error,MMSE)均衡器接收矩阵组,以低复杂度地处理来自多用户的上行数据。首先分析了矩阵数据的关联性,通过时谱图确定矩阵组在时间维所具有的强相关性;其次采用插值算法进行低复杂度的矩阵估计,并提出最大插值比搜索算法计算各类插值算法的性能及其复杂度;接着利用一种改进的Strassen矩阵求逆算法来降低MMSE求逆过程的复杂度。相比传统的接收矩阵组,显著降低了计算复杂度。

摘要： 密度峰值聚类(density peaks clustering,DPC)算法是聚类分析中基于密度的一种新兴算法,该算法考虑局部密度和相对距离绘制决策图,快速识别簇中心,完成聚类.DPC具有唯一的输入参数,且无需先验知识,也无需迭代.自2014年提出以来,DPC引起了学者们的极大兴趣,并得到了快速发展.首先阐述DPC的基本理论,并通过与经典聚类算法比较,分析了DPC的特点;其次,分别从聚类精度和计算复杂度两个角度分析了DPC的弊端及其优化方法,包括局部密度优化、分配策略优化、多密度峰优化以及计算复杂度优化,并介绍了每个类别的主要代表算法;最后介绍了DPC在不同领域中的相关应用研究.对DPC的优缺点提供了全面的理论分析,并对DPC的优化以及应用进行了全面阐述.还试图找出进一步的挑战来促进DPC研究发展.

摘要： 动态时间弯曲距离能度量不等长的时间序列、且具有较高的匹配精度,因此广泛应用在时间序列模式匹配中。但其计算复杂度较高,制约了在大规模数据集上的应用。为了实现时间序列模式度量结果和计算复杂度的平衡,提出一种基于特征点界标过滤的时间序列模式匹配方法。首先,提出一种特征点界标过滤的特征提取方法,保留时间序列主要特征,压缩时间维度;然后,利用动态时间弯曲距离对特征序列进行相似性度量;最后,在应用数据集上对所提方法进行有效性验证。实验结果表明,所提方法在保证高精度的前提下,能有效降低计算复杂度。

摘要： 分析了Grigoriev等提出的基于热带半环的密钥建立协议的安全性,提出了一种代数密码分析方法。从协议的公开信息构造热带矩阵方程,通过解热带半环上的线性方程组试图获得双方的共享密钥。为防止这种代数密码分析,应适当增大协议的参数。

摘要： 从信号处理角度考察Lubich系数,分析了Lubich系数的频域特性。设计了一种基于快速傅里叶逆变换(IFFT)的Lubich系数的快速算法。IFFT算法直接求解的Lubich系数不准确,在甚低阶运算时频域存在吉布斯效应,新算法利用零频赋值可有效减弱该效应。数值仿真结果表明,与Lubich准确系数相比,在一定真分数运算阶范围内,新算法求得的Lubich近似系数构建数字分数微分器有更好的效果,且新算法计算复杂度低,运算效率高。

摘要： 稀疏码分多址系统(sparse code multiple access,SCMA)作为一种码域的非正交多址技术,在相同时频资源条件下承载更多用户,能够满足5G通信的海量连接需求,但是接收端采用的消息传递算法(message passing algorithm,MPA)存在复杂度较高等问题。因此,该文提出了一种基于动态因子图更新率的消息传递算法(DFT-MPA),利用更新率衡量迭代前后因子图分支上信息的变化程度,选择收敛程度较高的分支加入收敛集合,通过减少迭代过程中更新分支的数目,降低了计算复杂度,当所有分支加入收敛集合或者达到最大迭代次数,则完成迭代输出译码。仿真结果表明,该算法能够有效平衡系统复杂度与误码率性能,满足不同的场景需求。

摘要： 针对基于密度的噪声应用空间聚类算法(density based spatial clustering of applications with noise,DBSCAN)计算复杂度较高以及无法聚类多密度数据集等问题,提出了一种网格聚类算法和DBSCAN相结合的融合聚类算法(G_FDBSCAN)。利用网格划分技术将数据集划分为稀疏区域和密集区域,分而治之,降低计算的时间复杂度和采用全局参数引起的聚类误差;改进传统的DBSCAN聚算法得到FDBSCAN,将密集区域中网格聚类的结果作为一个整体参与后续的聚类,在网格划分基础上进行邻域检索,减少邻域检索和类扩展过程中对象的无效查询和重复查询,进一步减少时间开销。理论分析和实验测试表明,改进后的算法与DBSCAN算法、DPC算法、KMEANS算法、BIRCH算法和CBSCAN算法相比,在聚类结果接近或达到最优的情况下,聚类效率分别平均提升了24倍、11倍、2倍、3倍和1倍。

摘要： 作为机器学习的一个分支,高斯过程回归在近年来越来越受到重视,在诸多领域得到了广泛的应用;该方法适用于非线性系统的建模,并可以自动在模型的复杂度和建模精度之间进行权衡;但是由于计算复杂度较高,其难以直接被应用于大数据量的学习任务,因此,很多近似方法被发展出来以降低其计算成本;根据是否将训练数据划分为子集,高斯过程回归的近似方法可以被分为全局近似方法和局部近似方法;文章首先阐述了高斯过程回归的理论基础,接下来对全局和局部这两种近似方法进行了分析,然后介绍了其在实际应用中的情况,特别是在软测量和控制领域,最后进行了总结和对其未来研究方向的展望。

摘要： 时频参考信号所使用的信道,比如GPS信道,通常会受到干扰而变得缺失或含有噪声,针对如何用有限的存储运算资源从不稳定信道恢复出稳定的时频参考,同时尽可能的缩短锁定时间并控制噪声通过频谱,本文提供了一种基于加权最小二乘算法的改进方案.在最小二乘的基础上,通过加权,对输入相位噪声进行等效滤波,控制抖动频谱,同时,通过权重的特殊选择以及快速处理方法的引入,有效的减小存储尺寸和计算复杂度.本文还讨论了通过对输入数据进行延迟使用以及利用历史存储进行回溯以剔除异常数据的处理方法,通过这些方法,提高了输出参考的稳定性和精确度,也为故障参考源无损下线提供了一种途径.

摘要： 传统密码算法在设计时并未考虑算法运行平台的安全风险.Chow等在2002年提出了白盒攻击模型,假定攻击者具有完全控制算法运行过程的能力,可以获取算法的运行状态、更改算法运行的中间值等.此模型更符合密码设备在失控环境下的应用情况,因为一个合法的用户也可能变为一个潜在的攻击者.在这种环境下,传统攻击模型中设计的密码算法将不再安全.如何保护密码算法在白盒环境下的安全性,在数字版权保护、移动终端安全等领域具有强烈的现实需求.Chow等使用混淆与查找表等方式设计了AES、DES白盒方案,肖雅莹等在2009年使用类似方法设计了SM4算法的白盒方案(肖-来方案),白鲲鹏等进一步通过复杂化内部解码编码过程以及引入更多随机数的方式设计了一个新的SM4白盒方案(白-武方案).本文分析了这两个SM4白盒方案.首先指出林婷婷等对肖-来方案分析的复杂度计算存在偏差(林-来分析).具体来讲,该分析中唯一确定了编码矩阵及仿射常数,而实质上根据该分析方法,编码矩阵与仿射常数存在215.9·232种可能取值.进一步地,改进了林-来的分析方法,通过调整仿射常数的恢复顺序,大幅降低了计算复杂度.如恢复查找表外部编码的仿射常数时,通过搜索等价密钥再确定仿射常数的方式只需不超过210次查表运算就可确定该仿射常数,而林-来分析中获取该仿射常数的计算复杂度为246.同时,提出了首个针对白-武方案的第三方分析,恢复其密钥的复杂度为215.9.2128.分析表明,肖-来、白-武方案的安全性主要依赖外部编码中仿射常数的安全性.两个方案的线性变换部分对安全性的影响有限,且复杂化内部编码解码过程并不能有效提高线性变换的安全性.另外,通过对仿射矩阵或仿射常数进行拆分来增大白盒多样性的策略只会增大白盒方案的实现难度,而对方案的安全性并无明显加强.这一系列发现将对白盒密码的分析与设计提供借鉴作用.

摘要： 为降低块稀疏最小均方算法(BS-NLMS)在系统辨识中的计算复杂度,在分析了声学回波消除等块稀疏系统的基础上,提出了一种利用语音活动检测方法来提高计算复杂度的新算法.该算法首先利用基于高阶统计量的语音活动检测法区分有无语音段,然后采用最小欧式距离范数作为更新标准,从而克服了传统抽头系数在每次迭代时需要全部更新而导致的计算复杂度的问题.文中给出了算法的计算复杂度分析,系统辨识的仿真结果表明本方法与传统块稀疏最小均方算法相比有更小的计算复杂度.

摘要： 在已有的大多数基于身份代理重签名方案中,签名验证需要执行耗时的双线性对运算,在计算能力较弱的低端计算设备上适用性比较低.为了提高签名验证效率,结合服务器辅助验证签名和基于身份代理重签名,提出了基于身份的服务器辅助验证代理重签名体制,并给出了基于身份服务器辅助验证代理重签名的安全性定义.基于Wang方案,构造了一种基于身份的服务器辅助验证代理重签名方案,并证明了新方案在合谋攻击、自适应选择身份和消息攻击下是安全的.分析结果表明,新方案将签名验证的大部分计算任务委托服务器执行,有效减少了双线性对的计算量,大大降低了签名验证算法的计算复杂度,在效率上优于已有的基于身份代理重签名方案.

摘要： 流密码算法Phelix是ESTREAM计划的一个候选算法,文中给出了模2"加环节X田y=Z的一个基于单比特故障的差分方程组求解算法.利用该算法采用面向比特的故障诱导模型对Phelix进行了差分故障攻击,该攻击理论上只需652个单比特故障就能完全恢复256 bit的工作密钥,计算复杂度为O(220).实验结果显示,Phelix算法对差分故障攻击是不安全的.

摘要： HEVC帧内模式采用穷举方法搜索最佳编码模式提高了编码效率,但引入较高的计算复杂度.本文通过分级的方式,大大降低编码单元(CU)大小的候选数量,提出一种快速编码单元提前判决算法.该方法利用时空相邻帧间相关性预测最佳阈值,通过分析纹理代价与非纹理代价相对于编码单元深度之间的关系,提前中止编码深度判决,有效的降低计算复杂度.实验结果显示本文方法实现了平均37％的计算复杂度降低,同时相比于HM参考软件穷举搜索结果,只是降低了0.21％的BD-Rate.

摘要： 空间调制技术(SM)作为一种新颖的多天线传输方案,近年来受到业界的广泛注意.它将输入信息比特分为两部分,一部分用于激活天线,另一部分用于信号调制,来共同承载发送信息.由于SM系统的最大似然(ML)最优检测算法需要穷举搜索激活天线序号和发送的数字调制符号的所有可能情况,它的检测复杂度很高.为此,人们相继提出了一些简化算法.与这些算法思路不同,本文从传统ML最优表达式出发,引入极坐标得到关于星座点幅度和相角的ML等价表达式,同时根据星座点相角的分布特性对相角进行近似,得到了一种新的次最优检测算法.新算法的检测性能比其他次优算法更接近ML,而且计算复杂度低.最后本文通过计算机仿真,验证了新算法的有效性.

摘要： Altair Feko提供了强大而丰富的电磁场等效源仿真技术,并已经在实际工程上得到广泛的应用,尤其在反射面天线、透镜天线、天线阵列(阵列互耦)、天线布局与天线罩透波特性等应用方向.采用等效源技术可以极大地降低计算的复杂度且能够保证工程精度,更为重要的是可以回避知识产权所带来的问题.

摘要： Altair Feko提供了强大而丰富的电磁场等效源仿真技术,并已经在实际工程上得到广泛的应用,尤其在反射面天线、透镜天线、天线阵列(阵列互耦)、天线布局与天线罩透波特性等应用方向.采用等效源技术可以极大地降低计算的复杂度且能够保证工程精度,更为重要的是可以回避知识产权所带来的问题.

摘要： Altair Feko提供了强大而丰富的电磁场等效源仿真技术,并已经在实际工程上得到广泛的应用,尤其在反射面天线、透镜天线、天线阵列(阵列互耦)、天线布局与天线罩透波特性等应用方向.采用等效源技术可以极大地降低计算的复杂度且能够保证工程精度,更为重要的是可以回避知识产权所带来的问题.

摘要： 本发明包括一种用于操作数据处理系统以计算对第一向量与第二向量之间的标量积的近似的方法，其中，每个向量由N个分量来表征。所述方法包括：由第三向量代替所述第一向量，所述第三向量是由以下各项表征的金字塔整数向量：N个分量；以及等于所述N个分量的绝对值之和的整数K；以及计算所述第三向量与所述第二向量的标量积，以提供对所述第一向量与所述第二向量之间的所述标量积的所述近似。可以通过K次加法然后一次浮点乘法来执行计算所述第二向量与所述第三向量的所述标量积。

摘要： 后向整形映射表最初作为前向整形映射表的逆生成。后向整形映射表通过利用前向整形的亮度码字替换内容映射的亮度码字来更新，前向整形的亮度码字通过对采样的亮度码字应用亮度前向映射来生成。亮度前向映射从前向整形映射表构造。后向整形映射表和亮度前向映射被用于生成后向整形映射以从前向整形的图像创建重构的图像。前向整形的图像与指定后向整形映射的图像元数据一起被编码在视频信号中。视频信号的接收方设备对前向整形的图像应用后向整形映射以创建第二动态范围的重构的图像。

摘要： 公开了用于无线通信的技术。在一个方面，用户设备(UE)向网络实体发送指示UE的定位能力的报告，该定位能力指示UE每单位时间、每单位频率或两者可以执行的定位计算的数量，以及执行定位参考信号(PRS)资源集合的定位相关测量的第一集合，以及基于所报告的UE的定位能力、将用于定位相关测量的第一和第二集合的PRS资源集合、报告参数集合、精度配置、等待时间配置或其任何组合来报告定位相关测量的第二集合。

摘要： 一种用于认证人的生物特征认证设备(30)，其通过比较人的身体部位(4)的生物特征与多个注册人的身体部位的预存储生物特征来认证人，该生物特征认证设备(30)配置为：捕获人的身体部位(4)的图像数据；从捕获的图像数据确定人的身体部位(4)的至少一个特征几何身体部位属性(Sf、Wf、Wh)以及人的身体部位(4)的生物特征；限定人的身体部位(4)的生物特征与多个注册人的身体部位的预存储生物特征的比较，该预存储生物特征具有关于人的至少一个特征几何身体部位属性(Sf、Wf、Wh)的预定的相似度水平。

摘要： 一种根据计算资源单元的最大可用数量调整图像和视频处理计算复杂度的方法，该方法包括以下步骤：执行多个处理数字图像和视频数据的数据乘法，每个数据乘法具有与数据无关值相乘的数据相关值，每个数据乘法的执行均需要预定数量的计算资源单元；选择数据乘法之一；选择移位/加、移位/减或移位运算，这些运算采用与所选乘法相关的数据无关值，所需计算资源单元的数量少于执行所选乘法所需的计算资源单元的预定数量；以及用所选运算来执行所选乘法。另外，一种使视频和静止图像解码计算复杂度与可用计算资源成比例的解码器。该解码器包括：变长解码器；使从变长解码器接收的信号去量化的逆量化器；根据上述方法调整解码计算复杂度的近似离散余弦反变换；以及运动补偿器。

摘要： 本发明属于阵列信号处理技术领域，具体涉及一种低计算复杂度的远场和近场混合信号源参数估计方法。本发明不需要进行奇异值分解、特征值分解以及矩阵求逆等计算复杂度较高的矩阵运算，具有较低的计算复杂度。本发明在利用正交匹配追踪算法进行近场距离参数的估计时，由于只对距离参数进行了网格划分，因此将以往的二维参数搜索转变成了一维参数搜索，进一步降低了参数估计算法的计算复杂度。由于本发明在计算远‑近场混合信号源参数时，所采用的离散分数阶傅里叶变换算法和正交匹配追踪算法都对环境噪声和接收数据的快拍数不敏感，因此本发明相对以往算法在低信噪比、小快拍数的环境下有更好的估计性能。

摘要： 本发明涉及一种降低计算复杂度和硬件成本的硬判决译码方法，基于CS‑RiBM算法进行改进，包括下面几个方面：(1)在保证得到正确译码结果的前提下，采用新的初始化条件，直接将新数据流中的第1次迭代的结果赋值为初始值进行运算；(2)加入判断校验子的0次项s0是否为0的机制；(3)删除每次迭代中必然出现的一个零值，即减少一个冗余的处理单元；(4)为实现在合适的时机将输出设为0，对原处理单元进行一定的修改，修改后的处理单元与原来处理单元相比，加入一个二路选择器用以在合适的时机将输出设置为0。

摘要： 一种减少在乘法器‑累加器(MAC)具有有限位宽的系统中进行操作的定点神经网络的计算复杂度的方法，包括：在计算该定点神经网络中的激活时减少移位操作的数目。该方法还包括：在计算该定点神经网络中的激活时平衡量化误差的量和溢出误差。

摘要： 本发明涉及一种低计算复杂度粒子平滑估计的多机动目标轨迹跟踪方法，针对多机动目标跟踪应用场景，建立具有未知混合状态的混杂系统模型，对多机动目标进行机动方式与运动状态的识别。设计出一种在粒子权重未退化时的低复杂度平滑计算方法，结合吉布斯采样、马尔可夫链蒙特卡洛方法估计未知的目标机动方式以及运动状态。与传统粒子平滑算法相比，本发明方法通过引入参考轨迹提高了目标机动方式和运动状态的估计精度，并通过低计算复杂度的粒子平滑算法提高了计算效率，因此该方法可在更短时间内达到相同精度的跟踪精度。

摘要： 本发明公开了一种常数级授权计算复杂度的属性基可搜索加密方法及系统，本发明方法包括：创建包含公钥和私钥的混合加密环境；基于混合加密环境，为待搜索的文档集合D构造加密的可搜索安全索引，为查询者构造嵌入查询者属性信息的私钥构件，设计概率性的查询陷门加密算法生成查询陷门；利用查询陷门，实现在文档集合D的可搜索安全索引上执行常数级授权计算复杂度的隐私搜索。本发明旨在解决传统属性基可搜索加密方法中存在的高搜索复杂度问题，本发明推动了属性基可搜索加密技术从理论研究到实际应用的发展，由于其常数级搜索复杂度，能够将其应用于云计算、物联网、大数据平台的真实环境中，实现加密数据的访问控制和高效搜索。