A converse to low-rank matrix completion
A converse to low-rank matrix completion
复制标题
低秩矩阵完成的逆过程
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Nowak
中科院分区：
文献类型：
--
作者：
Daniel L. Pimentel;R. Nowak
在许多实际应用中，给定d × N数据矩阵X中元素的子集Ω，并旨在推断所有缺失元素。低秩矩阵完备化（LRMC）中的现有理论提供了关于X的条件（例如，有界相干性或通用性）和Ω（例如，均匀随机采样或确定性组合条件），以保证如果X是秩r，则X是与所观察的条目一致的唯一秩r矩阵，并且因此X可以通过某种方法唯一地恢复（例如，核范数或交替最小化）。然而，在许多情况下，人们事先并不知道X的秩，并且根据X和Ω，即使X不是rank-r，也可能存在与观察到的条目一致的rank-r矩阵。因此，人们可能会被欺骗，认为X是秩r，而实际上它不是。在本文中，我们给出了关于X的条件（genericity）和关于Ω的确定性条件，以保证如果存在一个rank-r矩阵与观察到的元素一致，则X确实是rank-r。虽然我们对Ω的条件是组合的，我们提供了一个确定性的有效算法来验证是否满足条件。此外，在每列只有O（max{r，log d}）个样本的均匀随机抽样方案下，该条件以高概率满足。这加强了LRMC中的现有结果，允许放弃X先验已知为低秩的假设。
In many practical applications, one is given a subset Ω of the entries in a d × N data matrix X, and aims to infer all the missing entries. Existing theory in low-rank matrix completion (LRMC) provides conditions on X (e.g., bounded coherence or genericity) and Ω (e.g., uniform random sampling or deterministic combinatorial conditions) to guarantee that if X is rank-r, then X is the only rank-r matrix that agrees with the observed entries, and hence X can be uniquely recovered by some method (e.g., nuclear norm or alternating minimization). In many situations, though, one does not know beforehand the rank of X, and depending on X and Ω, there may be rank-r matrices that agree with the observed entries, even if X is not rank-r. Hence one can be deceived into thinking that X is rank-r when it really is not. In this paper we give conditions on X (genericity) and a deterministic condition on Ω to guarantee that if there is a rank-r matrix that agrees with the observed entries, then X is indeed rank-r. While our condition on Ω is combinatorial, we provide a deterministic efficient algorithm to verify whether the condition is satisfied. Furthermore, this condition is satisfied with high probability under uniform random sampling schemes with only O(max{r, log d}) samples per column. This strengthens existing results in LRMC, allowing to drop the assumption that X is known a priori to be low-rank.