Event Recovery by Faster Truncated Nuclear Norm Minimization

摘要

When we want to know an event we are concerned, it is likely that the collected information is incomplete which may severely affect the consequent analysis. In this paper, we focus on the event recovery problem that aims to discover missing historical information for a certain event based on the limited known information. We formulate an event as a two dimensional data matrix, which will be called the event matrix in this paper, and convert the original problem to matrix completion problem. We observe that the event matrix has low-rank structure due to the strong dependence between different event attributes. Then we adopt a recently proposed approach called Truncated Nuclear Norm Minimization (TNNM) to recover the event matrix. We also propose an early stopping strategy to further accelerate the optimization of TNNM. Experimental results on a collected event dataset demonstrate the effectiveness and the fast convergence rate of the proposed algorithm.