Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
复制标题
DOI：
--
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Xiao Zhang;S. Du;Quanquan Gu
中科院分区：
文献类型：
--
作者：
Xiao Zhang;S. Du;Quanquan Gu
我们重新审视归纳矩阵补全问题，该问题旨在恢复一个具有环境维数d的秩r矩阵，给定n个特征作为边先验信息。目标是利用已知的$n$特征来减少样本和计算复杂性。我们提出并分析了一种新的基于梯度的非凸优化算法，该算法以线性速率收敛到真正的底层矩阵，样本复杂度仅线性依赖于$n$，对数依赖于$d$。据我们所知，所有以前的算法要么对样本复杂性的特征数量有二次依赖，要么有次线性的计算收敛速度。此外，我们提供了合成和真实世界数据的实验来证明我们提出的算法的有效性。
We revisit the inductive matrix completion problem that aims to recover a rank-$r$ matrix with ambient dimension $d$ given $n$ features as the side prior information. The goal is to make use of the known $n$ features to reduce sample and computational complexities. We present and analyze a new gradient-based non-convex optimization algorithm that converges to the true underlying matrix at a linear rate with sample complexity only linearly depending on $n$ and logarithmically depending on $d$. To the best of our knowledge, all previous algorithms either have a quadratic dependency on the number of features in sample complexity or a sub-linear computational convergence rate. In addition, we provide experiments on both synthetic and real world data to demonstrate the effectiveness of our proposed algorithm.