Timezone: »

 
Spotlight
Exact and Stable Recovery of Pairwise Interaction Tensors
Shouyuan Chen · Michael R Lyu · Irwin King · Zenglin Xu

Fri Dec 06 10:14 AM -- 10:18 AM (PST) @ Harvey's Convention Center Floor, CC
in Spotlight Session 1 »
Tensor completion from incomplete observations is a problem of significant practical interest. However, it is unlikely that there exists an efficient algorithm with provable guarantee to recover a general tensor from a limited number of observations. In this paper, we study the recovery algorithm for pairwise interaction tensors, which has recently gained considerable attention for modeling multiple attribute data due to its simplicity and effectiveness. Specifically, in the absence of noise, we show that one can exactly recover a pairwise interaction tensor by solving a constrained convex program which minimizes the weighted sum of nuclear norms of matrices from $O(nr\log^2(n))$ observations. For the noisy cases, we also prove error bounds for a constrained convex program for recovering the tensors. Our experiments on the synthetic dataset demonstrate that the recovery performance of our algorithm agrees well with the theory. In addition, we apply our algorithm on a temporal collaborative filtering task and obtain state-of-the-art results.

Author Information

Shouyuan Chen (CUHK)
Michael R Lyu (CUHK)
Irwin King (Chinese University of Hong Kong)
Zenglin Xu (Harbin Institute of Technology Shenzhen)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors