Matrix Completion with Noisy Side Information

We study the matrix completion problem with side informatio n. Side information has been considered in several matrix completion applicati ons, and has been empirically shown to be useful in many cases. Recently, resear chers studied the effect of side information for matrix completion from a theoretica lv i e w p o i n t,s h o w i n g that sample complexity can be significantly reduced given co mpletely clean features. However, since in reality most given features are noi sy or only weakly informative, the development of a model to handle a general feature set, and investigation of how much noisy features can help matrix recovery, r emains an important issue. In this paper, we propose a novel model that balances b etween features and observations simultaneously in order to leverage feature i nformation yet be robust to feature noise. Moreover, we study the effect of general fe atures in theory and show that by using our model, the sample complexity can be low er than matrix completion as long as features are sufficiently informative .T h i s r e s u l t p r o v i d e s at h e o r e t i c a li n s i g h ti n t ot h eu s e f u l n e s so fg e n e r a ls i d ei n formation. Finally, we consider synthetic data and two applications -- relationshi pp r e d i c t i o na n ds e m i - supervised clustering -- and show that our model outperforms other methods for matrix completion that use features both in theory and pract ice.