摘要：图正则化(nonnegative matrix factorization,NMF)算法(graph regularization nonnegative matrix factorization,GNMF)仍存在一些不足之处:GNMF算法并没有考虑数据的低秩结构;在GNMF算法中,其拉普拉斯图是使用K近邻(K nearest neighbor,KNN)方法预先定义的,而KNN方法无法总是获得最优图解,从而使得GNMF算法的性能不能达到最优。为此,本文提出了一种自适应图正则化的非负矩阵分解算法(nonnegative low-rank matrix factorization with adaptive graph neighbors,NLMFAN)。一方面,通过引入低秩约束,使得NLMFAN可以获得原始数据集的有效低秩结构;另一方面,设计了一种通过自适应求解相似度矩阵的方法来进行图的构建,即图的构造和矩阵分解的结果被融入一个整体的框架中,使得图中节点的相似性是自动从数据中学习得到的。此外,本文还给出了一种求解NLMFAN的有效算法。在多种数据集上的实验验证了本文所提出的算法的有效性。

摘要：针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法.根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点.每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块.通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序.实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性.

摘要：随着芯片制程不断深入到亚微纳米级别,技术节点的持续缩小加速了片上网络中链路故障的发生。故障链路的增多降低了可用的路由路径数量,并可能导致严重的流量拥塞甚至系统崩溃。为了保证在遭遇故障链路时数据包的正常传输,该文提出一种基于自适应容错链路的片上网络设计(AFL_NoC),它能够将遭遇故障链路的数据包转发到另一条可逆链路上。该方案包括了可逆链路的具体实现以及相应的分布式控制协议。这种动态容错链路设计充分利用了网络中空闲的可用链路资源,确保了在遭遇链路故障的情况下网络通信不会中断。与先进的容错偏转路由算法QFCAR-W相比,AFL_NoC平均延迟降低10%,面积开销减少了14.2%,功耗开销减少了9.3%。

摘要：张量主成分分析(Tensor Principal Component Analysis,TPCA)是主成分分析(Principal Component Analysis,PCA)在多维空间上的推广,能充分利用图像/视频的空间关联,在图像分析和视频处理中扮演了重要的角色.传统的张量PCA方法提取的特征向量是非稀疏的,这使得其很难进行解释.近年来出现了众多稀疏PCA方法,能提取只包含少量非零元的特征.把稀疏特征提取引入到张量分析,提出一种鲁棒稀疏的张量PCA方法(TPCAL1S).首先,设计了能实现稀疏特征提取的目标函数.一方面,用L1范数代替Frobenius-范数,使得算法对异常数据更加鲁棒;另一方面,在目标函数中引入弹性网,联合使用Lasso与Ridge惩罚因子来实现稀疏化,增强了算法的语义解释性.然后,设计了一种基于二阶张量的投影矩阵交替求解算法,二阶张量便于数学描述,也易于推广到更高阶张量.此求解算法分为两个步骤(V,U分别表示左投影矩阵和右投影矩阵),先固定U优化V,再固定V的值优化U,两个步骤反复交替执行,直到收敛.每个步骤都采用贪心算法以迭代的方式逐个特征提取以求得U或V.最后,对迭代过程的单调性做了理论证明.基于ORL,Yale和Feret库,将TPCA-L1S应用于人脸图像分析并与其他常见方法作比较,实验结果验证了该模型的有效性.

摘要：最小二乘回归(Least Square Regression,LSR)算法是一种流行的子空间聚类方法,在处理计算机视觉和机器学习的相关问题中的应用十分普遍.然而,当数据含有噪声时,其求得的亲和矩阵不是块对角化的,还存在一定的噪声,这使亲和矩阵不够鲁棒可靠,因而降低了算法的聚类性能.为了解决以上不足,提出一种双重结构的最小二乘回归子空间聚类算法(Double Structure Least Squares Regression Subspace Clustering,DSLSR).首先对原始数据实施LSR算法,由于其生成的亲和矩阵往往不是块对角矩阵且含有噪声,需要对求得的亲和矩阵再次实施LSR算法来去除亲和矩阵中的噪声,使亲和矩阵更干净可靠,从而提升算法的聚类性能.最后,把两次LSR过程纳入一个统一的算法框架,设计一个统一的目标函数.此外,还采取了增广拉格朗日乘子方法对目标函数进行优化求解.在一些数据集上的实验证实,DSLSR算法比现有算法的性能更卓越.

摘要：针对多叉树任务数据流图的划分映射问题,基于粗粒度行并行可重构架构,提出一种行列剪枝映射算法.首先分析和比较了二维没有跳变近邻点点互连和行并行互连的可重构单元阵列的映射性能,通过3种类型的一次循环四阶多叉树映射实验结果表明(RCA4×4),行并行架构执行总周期最大减少了63个周期,最少减少了20个周期;然后设计实现了行列剪枝映射算法,先按行剪枝映射,再对已映射节点的依赖后继进行列剪枝映射,在满足面积和互连等约束下考虑运算节点层次和入度等因素构造了排队函数,通过该函数值动态调整就绪列表节点的调度次序.实验结果表明,与放置路由算法相比,文中算法执行时间平均减少了15.7%(RCA4×4)和18.4%(RCA5×5);与分裂压缩内核算法相比,该算法执行时间平均减少了30.0%(RCA4×4)和29.8%(RCA5×5):从而验证了文中提出解决多叉树行并行可重构单元阵列及映射算法有效性.

摘要：比特币引入了一种新的P2P(Peer to Peer)交易方法,并依靠其底层协议实现去中心化交易.然而,由于目前缺乏对比特币各底层协议的细粒度形式化分析和系统建模,比特币安全性并未被保证.本文通过设计多维度的比特币安全模型引理和细粒度的比特币模型规则,系统地抽象了多协议组合运行考虑下的比特币协议实体交互,完成了对比特币的形式化符号建模与自动化安全分析.与以前的工作相比,本文更细粒度地建模了比特币协议实体及其相关操作,并全面设计了满足比特币各实体需求的安全属性.此外,本文利用自动化形式化验证系统SmartVerif实现了无需额外手工推导证明的形式化验证实验,通过将本文所建模的符号模型规则与引理作为SmartVerif的输入,发现了比特币底层协议算力盗取攻击.

摘要：在大型无线传感器网络中,如何有效实时监控系统中的故障链接是研究中的一个难点。链路故障检测和网络诊断起着至关重要的作用。链路故障检测还可以发现其他潜在的网络瓶颈,如网络分裂、路由错误等,而且故障节点还将影响其链接性能,包括发送和接收。然而依次检查所有潜在链接会导致过高的传输存储成本,现有方法往往侧重于正在使用中的链接,忽略潜在链接,这样将无法为故障检测提供更多的支持。提出一种新型实时监测无线链路的链接扫描方案,该方案会在网络中发出探测报文,收集传感器节点接收到此报文的跳数,其中故障链路会出现接收的跳数与网络拓扑结构不匹配的现象,结合概率模型则能够推导出所有链路的状态。经过实验证明,该方案能够有效对无线传感器网络实施监控。

摘要：现有的非负矩阵分解(NMF)算法往往基于欧氏距离来设计目标函数,对噪声比较敏感。为了增强算法的鲁棒性,提出一种基于干净数据的流形正则化非负矩阵分解(MRNMF/CD)算法。在MRNMF/CD算法中,把低秩约束、流形正则化和NMF技术无缝地融为一体,使算法性能较为优异。首先,通过添加低秩约束,MRNMF/CD可以从噪声数据中恢复干净数据,并获得数据的全局结构;其次,为了利用数据的局部几何结构信息,MRNMF/CD把流形正则化融入目标函数中。此外,还提出了一种求解MRNMF/CD的迭代算法,并从理论上分析了该求解算法的收敛性。在ORL、Yale和COIL20数据集上的实验结果表明,MRNMF/CD算法比现有的k-means、主成分分析(PCA)、NMF和图正则化非负矩阵分解(GNMF)算法具有更好的识别准确性。

摘要：针对低秩表示(LRR)子空间聚类算法没有考虑数据局部结构,在学习中可能会造成局部相似信息丢失的问题,提出了一种基于Hessian正则化和非负约束的低秩表示子空间聚类算法(LRR-HN),用来探索数据的全局结构和局部结构。首先,利用Hessian正则化良好的推测能力来保持数据的局部流形结构,使数据局部拓扑结构的表达能力更强;其次,考虑到获得的系数矩阵往往有正有负,而负值往往没有实际意义的特点,引入非负约束来保证模型解的有效性,使其在数据局部结构描述上更有意义;最后,通过最小化核范数寻求数据全局结构的低秩表示,从而更好地聚类高维数据。此外,利用自适应惩罚的线性交替方向法设计了一种求解LRR-HN的有效算法,并在一些真实数据集上,采用正确率(AC)和归一化互信息(NMI)对所提出的算法进行了评估。在ORL数据集上聚类数目为20时的实验中,LRR-HN与LRR算法相比,AC和NMI分别提高了11%和9.74%;与自适应低秩表示(ALRR)算法相比,AC和NMI分别提高了5%和1.05%。实验结果表明,LRR-HN与现有的一些算法相比,AC和NMI均有较大的提升,有较好的聚类性能。