Community structure detection in social networks based on dictionary learning

Discovering community structures is a fundamental problem concerning how to understand the topology and the functions of complex network. In this paper, we propose how to apply dictionary learning algorithm to community structure detection. We present a new dictionary learning algorithm and systematically compare it with other state-of-the-art models/algorithms. The results show that the proposed algorithm is highly effectively at finding the community structures in both synthetic datasets, including three types of data structures, and real world networks coming from different areas.     

Radiance-based color calibration for image-based modeling with multiple cameras

Photo-consistency estimation is an important part for many image-based modeling techniques.This paper presents a novel radiance-based color calibration method to reduce the uncertainty of photo-consistency estimation across multiple cameras.The idea behind our method is to convert colors into a uniform radiometric color space in which multiple image data are corrected.Experimental results demonstrate that our method can achieve comparable color calibration effect without adjusting camera parameters and is more robust than other existing method.Additionally,we obtain an auto-determined threshold for photo-consistency check,which will lead to a better performance than existing photo-consistency based reconstruction algorithms.     

Successively alternate least square for low-rank matrix factorization with bounded missing data

The problem of low-rank matrix factorization with missing data has attracted many significant attention in the fields related to computer vision. The previous model mainly minimizes the total errors of the recovered low-rank matrix on observed entries. It may produce an optimal solution with less physical meaning. This paper gives a theoretical analysis of the sensitivities of the original model and proposes a modified constrained model and iterative methods for solving the constrained problem. We show that solutions of original model can be arbitrarily far from each others. Two kinds of sufficient conditions of this catastrophic phenomenon are given. In general case, we also give a low bound of error between an ?-optimal solution that is practically obtained in computation and a theoretically optimal solution. A constrained model on missing entries is considered for this missing data problem. We propose a two-step projection method for solving the constrained problem. We also modify the method by a successive alternate technique. The proposed algorithm, named as SALS, is easy to implement, as well as converges very fast even for a large matrix. Numerical experiments on simulation data and real examples are given to illuminate the algorithm behaviors of SALS.     

Incremental subspace learning via non-negative matrix factorization

In this paper we introduce an incremental non-negative matrix factorization (INMF) scheme in order to overcome the difficulties that conventional NMF has in online processing of large data sets. The proposed scheme enables incrementally updating its factors by reflecting the influence of each observation on the factorization appropriately. This is achieved via a weighted cost function which also allows controlling the memorylessness of the factorization. Unlike conventional NMF, with its incremental nature and weighted cost function the INMF scheme successfully utilizes adaptability to dynamic data content changes with a lower computational complexity. Test results reported for two video applications, namely background modeling in video surveillance and clustering, demonstrate that INMF is capable of online representing data content while reducing dimension significantly.     

矩阵的Doolittle递归分解算法及符号程序设计

将矩阵An×n的Doolittle分解推广到Am×n上，并在常规的迭代算法上加以创新，给出了递归的分解算法．在实现算法的过程中，对数据进行了巧妙处理，使中间数据及最终计算结果都具有分数形式，提高了结果的精确度，而且更符合人们阅读的习惯．经过运行测试，算法设计合理，程序运行高效准确．程序是对MathSoft公司的交互式的数学文字软件Mathcad的矩阵分解的数值计算扩充到符号运算．     

Large margin based nonnegative matrix factorization and partial least squares regression for face recognition

In this paper, we present a new method, called large margin based nonnegative matrix factorization (LMNMF), to encode latent discriminant information in training data. LMNMF seeks a nonnegative subspace such that k nearest neighbors of each sample always belong to same class and samples from different classes are separated by a large margin. In the subspace, the local separation structure of data is explicit. The large-margin criterion leads to a new objective function, and a convergency provable multiplicative nonnegative updating rule is derived to learn the basis matrix and encoding vectors. Then, partial least squares regression (PLSR) learns the mapping from the original data to low dimensional representations in order to capture local separation information. PLSR offers a unified solution to out-of-sample extension problem. Extensive experimental results demonstrate LMNMF with PLSR leads significant improvements on classification than several other commonly used NMF-based algorithms.     

Generalized Lyapunov equation and factorization of matrix polynomials

This paper presents an algorithm for the construction of a solution of the generalized Lyapunov equation. It is proved that the polynomial matrix factorization relative to the imaginary axis may be reduced to the successive solution of Lyapunov equations, i.e. the factorization is reduced to the solution of a sequence of generalized Lyapunov equations, not to the solution of generalized Riccati equation.     

Collaborative filtering with interlaced generalized linear models

Collaborative filtering (CF) is a data analysis task appearing in many challenging applications, in particular data mining in Internet and e-commerce. CF can often be formulated as identifying patterns in a large and mostly empty rating matrix. In this paper, we focus on predicting unobserved ratings. This task is often a part of a recommendation procedure. We propose a new CF approach called interlaced generalized linear models (GLM); it is based on a factorization of the rating matrix and uses probabilistic modeling to represent uncertainty in the ratings. The advantage of this approach is that different configurations, encoding different intuitions about the rating process can easily be tested while keeping the same learning procedure. The GLM formulation is the keystone to derive an efficient learning procedure, applicable to large datasets. We illustrate the technique on three public domain datasets.     

非负矩阵分解的复杂网络社团检测方法

为有效地检测复杂网络中的社团结构,优化了评估与发现社团的模块密度函数(即D值).通过模块密度的优化进程,证明了模块函数的最大化与非负矩阵分解目标函数(SNMF)的等价性.基于这种等价性,设计了一种新的基于模块密度函SNMF算法,并且讨论了该算法的复杂性.在一个经典的计算机产生的随机网络中检验了该算法,特别地,当社团结构变模糊时,实验结果表明该算法在发现复杂网络社团上是有效的.     

Non-negative matrix factorization: Ill-posedness and a geometric algorithm

Non-negative matrix factorization (NMF) has been proposed as a mathematical tool for identifying the components of a dataset. However, popular NMF algorithms tend to operate slowly and do not always identify the components which are most representative of the data. In this paper, an alternative algorithm for performing NMF is developed using the geometry of the problem. The computational costs of the algorithm are explored, and it is shown to successfully identify the components of a simulated dataset. The development of the geometric algorithm framework illustrates the ill-posedness of the NMF problem and suggests that NMF is not sufficiently constrained to be applied successfully outside of a particular class of problems.     

The direct solution of banded linear systems by a new matrix factorization procedure

In the finite difference/element discretisation of boundary value problems involving partial differential equations there occurs the problem of solving large order systems of banded linear systems.

Previously, direct methods of solution considered were the usual Gaussian elimination and LU decomposition strategies. In this paper an alternative factorization strategy is presented.     

An explicit solution to polynomial matrix right coprime factorization with application in eigenstructure assignment

In this paper, an explicit solution to polynomial matrix right coprime factorization of input-state transfer function is obtained in terms of the Krylov matrix and the Pseudo-controllability indices of the pair of coefficient matrices. The proposed approach only needs to solve a series of linear equations. Applications of this solution to a type of generalized Sylvester matrix equations and the problem of parametric eigenstructure assignment by state feedback are investigated. These new solutions are simple, they possess better structural properties and are very convenient to use. An example shows the effect of the proposed results.