Exact and stable recovery of pairwise interaction tensors
Refereed conference paper presented and published in conference proceedings


Times Cited

Other information
AbstractTensor 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.
All Author(s) ListChen S., Lyu M.R., King I., Xu Z.
Name of Conference27th Annual Conference on Neural Information Processing Systems, NIPS 2013
Start Date of Conference05/12/2013
End Date of Conference10/12/2013
Place of ConferenceLake Tahoe, NV
Country/Region of ConferenceUnited States of America
Proceedings TitleProceedings of the 2013 Annual Conference on Advances in Neural Information Processing Systems (NIPS 2013)
Year2013
Month1
Day1
PublisherNIPS Inc
ISSN1049-5258
LanguagesEnglish-United Kingdom

Last updated on 2020-02-09 at 00:55