正交投影非负矩阵的交替方向乘子分解方法

Orthogonal projection non-negative matrix factorization using alternating direction method of multipliers

目的目前非负矩阵分解一般使用乘性规则进行更新,乘性更新规则虽实现简单,但更新时收敛较慢,而且容易陷入局部最优解。当数据规模较大时,乘性规则的时效性很低,难以应用于一些实时性较强的问题中。针对乘性更新规则的这些缺点,提出一种使用交替方向乘子求解正交投影非负矩阵分解的方法。方法首先,基于正交投影非负矩阵的正交性和稀疏性特征,将原始的目标函数优化问题分解为各子问题的交替优化求解过程。通过引入辅助变量建立原目标函数的增广拉格朗日方程,完成对原问题的子问题等价表示;然后,对转换后方程的主变量和对偶变量进行交替优化求解,从而找到原问题最优解。结果不同规模矩阵分解仿真实验结果表明,与乘性更新规则相比,本文所提方法在收敛速度和精度上具有明显优势,特别是在矩阵规模很大时,收敛速度明显优于乘性规则。同时,将本文方法应用于目标跟踪问题中,提出一种基于交替方向乘子方法的模版更新策略,并与乘性规则以及其他3种经典目标跟踪算法进行比较。本文方法在目标跟踪效果上与基于乘性更新规则方法相当,且优于其他3种方法,重叠率约0.73,且帧处理速度约是乘性规则的3.8倍。结论本文方法在数据规模较大时,处理速度明显优于乘性规则。在目标跟踪应用中,因其分解过程中的稀疏性和正交性,与常用跟踪算法相比能较好地应对视频场景中的遮挡、尺度变化及光照变化等干扰,其跟踪性能更加稳定。

Objective The multiplicative update rule is generally used in non-negative matrix factorization （NMF）. Such rule exhibits simple implementation characteristics, and thus, the linear complexity for each iteration is frequently applied because it is more stable than Newton＇ s method. However, the multiplicative update rule also has disadvantages, such as slow convergence, asymptotic convergence to zero, and poor local optima. In particular, when the size of the data to be processed is large, the multiplicative update rule exhibits extremely low timeliness, and thus, it cannot be applied to sever- al real-time applications, such as online object tracking. To address these limitations, an orthogonal projection NMF meth- od based on alternating direction method of multipliers is proposed. The traditional NMF algorithm does not guarantee the availability of good partial-based representation; hence, a non-negative projection matrix and an orthogonal constraint are introduced. An orthogonal projection NMF （OPNMF）, which can reduce computation complexity, is applied. Simultane- ously, the bases exhibit high orthogonality due to the orthogonal and sparse characteristics of OPNMF. Therefore, obtaining an excellent part-based representation of the object becomes possible. Method As a new development of the Lagrange aug- mentation algorithm, the alternative direction method of multipliers （ADMM） is a simple and effective approach to solve the separable convex programming problem （ particularly large-scale problems）. One of the advantages of ADMM is that it can separate the objective function of the original problem into several sub-problems, which are easier to find local solutions via the separability of original function, and thus, an optimal solution is obtained. Compared with the NMF based multiplica- rive update rule, OPNMF based on the alternative direction method of multipliers does not only converge to the global solu- tion, but also requires less convergence time. The derivation of the proposed algorithm is presented in this study. First, the solution of the original objective function is decomposed into the alternative optimization of different sub-problems based on the orthogonality and sparsity of OPNMF. The augmented Lagrangian equation of the original objective function is estab- lished to equally represent the sub-problems of the original problem by introducing auxiliary variables. Then, the main and dual variables of the transformed equation are optimized alternately. In particular, the partial derivatives of these variables are used for each equation to find the current optimal solution. Finally, the corresponding update rules are derived and the iterative process of each variable is updated alternately to obtain the optimal solution. Result Four matrices with different si- zes are selected for the simulation to compare the performance of the ADMM algorithm with the muhiplicative update rule in OPNMF. Experimental results show that the proposed method clearly outperforms the traditional approach in terms of con- vergence speed and accuracy. In particular, as the size of the matrix increases, the convergence rate of the algorithm be- comes considerably higher than that of the multiplicative update rule. In the second experiment, we apply the proposed method to object tracking, which is a classical study area in computer vision. The observation model of the moving object is represented by the bases of OPNMF, i. e. , the candidate object in each frame is represented by the linear combination of the basis vectors. During the tracking stage, the observation model is updated on time to avoid tracking drift due to the con- tinuous appearance changes of the target object. A new template-updating strategy based on ADMM, which combines OPNMF part-based representation and ADMM update speed, is also proposed. Compared with the multiplicative update rule and three other state-of-the-art object tracking algorithms, the experimental results show that the proposed method is effec- tive with OPNMF based on the multiplicative updating rule. The tracking speed is approximately 3.8 times that based on the muhiplicative updating rule. The overlap rate of the proposed method is approximately 0. 73, which is better than those of the other three object tracking algorithms. Conclusion The proposed method is considerably superior when the size of the matrix is large. The ADMM method can achieve faster convergence rate and higher convergence precision when p is appro- priately selected. Moreover, object tracking based on OPNMF, which benefits from the sparseness and orthogonality of this algorithm, can address certain interference situations, such as occlusion, scale change, and illumination change, thereby achieving robust tracking.