Low-rank Matrix Recovery With Unknown Correspondence
Low-rank Matrix Recovery With Unknown Correspondence
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Zhiwei Tang;Tsung-Hui Chang;X. Ye;H. Zha
中科院分区：
文献类型：
--
作者：
Zhiwei Tang;Tsung-Hui Chang;X. Ye;H. Zha
研究了对应关系未知的矩阵恢复问题：给定观测矩阵$M_o=[A，\tilde P B]$，其中$\tilde P$是未知置换矩阵，我们的目标是恢复底层矩阵$M=[A，B]$.这样的问题通常出现在许多应用中，其中使用异构数据并且它们之间的对应关系是未知的，例如，因为隐私问题。我们证明了在适当的低秩条件下，通过求解核范数极小化问题，可以恢复M，并证明了恢复M的非渐近误差界。我们提出了一个算法，$\text{M}^3\text{O}$（矩阵恢复通过最小最大优化），将这个组合问题转化为一个连续的最小最大优化问题，并解决了它的近似梯度与最大甲骨文。$\text{M}^3\text{O}$也可以应用于更一般的场景，即我们在$M_o$中有缺失的条目，并且有多组数据具有不同的未知对应关系。在模拟数据、MovieLens 100 K数据集和Yale B数据库上的实验表明，$\text{M}^3\text{O}$在多个基线上实现了最先进的性能，并且可以高精度地恢复地面实况对应。
We study a matrix recovery problem with unknown correspondence: given the observation matrix $M_o=[A,\tilde P B]$, where $\tilde P$ is an unknown permutation matrix, we aim to recover the underlying matrix $M=[A,B]$. Such problem commonly arises in many applications where heterogeneous data are utilized and the correspondence among them are unknown, e.g., due to privacy concerns. We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. We propose an algorithm, $\text{M}^3\text{O}$ (Matrix recovery via Min-Max Optimization) which recasts this combinatorial problem as a continuous minimax optimization problem and solves it by proximal gradient with a Max-Oracle. $\text{M}^3\text{O}$ can also be applied to a more general scenario where we have missing entries in $M_o$ and multiple groups of data with distinct unknown correspondence. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $\text{M}^3\text{O}$ achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.