论文标题
矩阵完成，成本异质成本
Matrix Completion with Heterogonous Cost
论文作者
论文摘要
在许多基本条件下，矩阵完成问题已广泛研究。在自适应或非自适应，精确或估计，单相或多相以及许多其他类别的情况下，已经探索了该问题。在大多数情况下，每个入口的观察成本都是均匀的，并且在整个列之间的成本相同。但是，在许多现实生活中，我们可以期望来自不同列或不同位置的要素具有不同的成本。在本文中，我们在自适应条件下探讨了这种概括。我们在两个不同的成本模型下解决了问题。第一个是来自不同列的条目具有不同的观察成本，但是，在同一列中，每个条目的成本均匀。第二个是任何两个条目都有不同的观察成本，尽管相同或不同的列。我们提供算法的复杂性分析并提供紧密的保证。
The matrix completion problem has been studied broadly under many underlying conditions. The problem has been explored under adaptive or non-adaptive, exact or estimation, single-phase or multi-phase, and many other categories. In most of these cases, the observation cost of each entry is uniform and has the same cost across the columns. However, in many real-life scenarios, we could expect elements from distinct columns or distinct positions to have a different cost. In this paper, we explore this generalization under adaptive conditions. We approach the problem under two different cost models. The first one is that entries from different columns have different observation costs, but, within the same column, each entry has a uniform cost. The second one is any two entry has different observation cost, despite being the same or different columns. We provide complexity analysis of our algorithms and provide tightness guarantees.
