Consider a movie recommendation system where apart from the ratings
information, side information such as user's age or movie's genre is also
available. Unlike standard matrix completion, in this setting one should be
able to predict inductively on new users/movies. In this paper, we study the
problem of inductive matrix completion in the exact recovery setting. That is,
we assume that the ratings matrix is generated by applying feature vectors to a
low-rank matrix and the goal is to recover back the underlying matrix.
Furthermore, we generalize the problem to that of low-rank matrix estimation
using rank-1 measurements. We study this generic problem and provide conditions
that the set of measurements should satisfy so that the alternating
minimization method (which otherwise is a non-convex method with no convergence
guarantees) is able to recover back the {\em exact} underlying low-rank matrix.
In addition to inductive matrix completion, we show that two other low-rank
estimation problems can be studied in our framework: a) general low-rank matrix
sensing using rank-1 measurements, and b) multi-label regression with missing
labels. For both the problems, we provide novel and interesting bounds on the
number of measurements required by alternating minimization to provably
converges to the {\em exact} low-rank matrix. In particular, our analysis for
the general low rank matrix sensing problem significantly improves the required
storage and computational cost than that required by the RIP-based matrix
sensing methods \cite{RechtFP2007}. Finally, we provide empirical validation of
our approach and demonstrate that alternating minimization is able to recover
the true matrix for the above mentioned problems using a small number of
measurements.

本论文研究了基于用户年龄或电影类型等内容信息，预测新用户或新电影评分的电影推荐系统，提出了使用低秩矩阵加特征向量生成评分矩阵的方法，并探讨了使用基于排名的测量值进行低秩矩阵恢复的问题和方法，并在具体三个问题上进行了应用和实验验证。