Structure and reversibility of 2D hexagonal cellular automata

Cellular automata are used to model dynamical phenomena by focusing on their local behavior which depends on the neighboring cells in order to express their global behavior. The geometrical structure of the models suggests the algebraic structure of cellular automata. After modeling the dynamical phenomena, it is sometimes an important problem to be able to move backwards in order to understand it better. This is only possible if cellular automata is reversible. In this paper, 2D finite cellular automata defined by local rules based on hexagonal cell structure are studied. Rule matrix of the hexagonal finite cellular automaton is obtained. The rank of rule matrices representing the 2D hexagonal finite cellular automata via an algorithm is computed. It is a well known fact that determining the reversibility of a 2D cellular automata is a very difficult problem in general. Here, the reversibility problem of this family of 2D hexagonal cellular automata is also resolved completely.     

An alternative Kalman-Yakubovich-Popov lemma and some extensions

This paper introduces an alternative formulation of the Kalman-Yakubovich-Popov (KYP) Lemma, relating an infinite dimensional Frequency Domain Inequality (FDI) to a pair of finite dimensional Linear Matrix Inequalities (LMI). It is shown that this new formulation encompasses previous generalizations of the KYP Lemma which hold in the case the coefficient matrix of the FDI does not depend on frequency. In addition, it allows the coefficient matrix of the frequency domain inequality to vary affinely with the frequency parameter. One application of this results is illustrated in an example of computing upper bounds to the structured singular value with frequency-dependent scalings.     

The quantum query complexity of the determinant

In this paper we give tight quantum query complexity bounds of some important linear algebra problems. We prove Θ(n²) quantum query bounds for verify the determinant, rank, matrix inverse and the matrix power problem.     

基于非负矩阵分解的中文文本主题分类

提出基于非负矩阵分解（NMF）的中文文本主题分类方法,应用NMF算法分解词．文本矩阵获取词之间的相关性,有效地解决同义词、多义词的影响。实验结果表明,与基于奇异值分解的潜在语义索引方法相比,该方法计算速度快、占用存储空间较少。在潜在语义数据降低较大的情况下,NMF方法具有更好的分类精度。     

基于NMF分组策略的人脸识别

提出一种运用非负矩阵分解（NMF）分组策略进行人脸识别的方法。将训练图像分组,分别对每组图像作NMF,获取每组图像的基图像构成的非负特征子空间,将训练图像和测试图像分别向各个特征子空间进行投影,将每组图像提取出的特征系数混合,根据最近邻原则进行识别。基于ORL人脸数据库上的实验证明了该方法的有效性。     

一种基于受限约束范围标签传播的半监督学习算法

提出一种基于受限约束范围标签传播的半监督学习算法。首先利用相似性矩阵计算得出概率转移矩阵,进而通过概率转移矩阵得出受限约束范围。然后在约束范围内利用半监督学习框架下的标签传播算法计算基于路径的相似性,路径相似性决定了标签传播的重要路径。由于只使用几条重要的传播路径使得算法中省去计算每一条路径的相似度,计算复杂度大大减少。最终使得标签在带标签数据与未标签数据之间通过几条重要的路径之间传播。实验已经证明此算法的有效性。     

基于矩阵完整化的分块整合推荐算法

传统的推荐系统往往是通过使用协同过滤或基于内容的方式来实现的,而文中将矩阵完整化的方法应用到推荐系统中。由于数据的稀疏性,直接使用矩阵完整化的方法会给推荐结果带来不小的误差。考虑到使用用户中存在一些活跃用户,挖掘出这些特殊用户,由他们组成的数据会降低稀疏性,而且对活跃用户提高 推荐质量,会产生更大的商业价值。提出了一种分块整合推荐的方法,实验结果表明该方法能够提升推荐精度。     

Solving differential matrix Riccati equations by a piecewise-linearized method based on diagonal Padé approximants

Differential Matrix Riccati Equations (DMREs) appear in several branches of science such as applied physics and engineering. For example, these equations play a fundamental role in control theory, optimal control, filtering and estimation, decoupling and order reduction, etc. In this paper a new method based on a theorem proved in this paper is described for solving DMREs by a piecewise-linearized approach. This method is applied for developing two block-oriented algorithms based on diagonal Padé approximants. MATLAB versions of the above algorithms are developed, comparing, under equal conditions, accuracy and computational costs with other piecewise-linearized algorithms implemented by the authors. Experimental results show the advantages of solving stiff or non-stiff DMREs by the implemented algorithms.     

Dynamic normal forms and dynamic characteristic polynomial

We present the first fully dynamic algorithm for computing the characteristic polynomial of a matrix. In the generic symmetric case, our algorithm supports rank-one updates in O(n²logn) randomized time and queries in constant time, whereas in the general case the algorithm works in O(n²klogn) randomized time, where k is the number of invariant factors of the matrix. The algorithm is based on the first dynamic algorithm for computing normal forms of a matrix such as the Frobenius normal form or the tridiagonal symmetric form. The algorithm can be extended to solve the matrix eigenproblem with relative error 2^−b in additional O(nlog²nlogb) time. Furthermore, it can be used to dynamically maintain the singular value decomposition (SVD) of a generic matrix. Together with the algorithm, the hardness of the problem is studied. For the symmetric case, we present an Ω(n²) lower bound for rank-one updates and an Ω(n) lower bound for element updates.