高度不均匀采样下低秩矩阵补全的逐项界限

Feb, 2024

高度不均匀采样下低秩矩阵补全的逐项界限

Entry-Specific Bounds for Low-Rank Matrix Completion under Highly Non-Uniform Sampling

Xumei Xi, Christina Lee Yu, Yudong Chen

TL;DR低秩矩阵补全问题关注使用稀疏观测的一组观测条目来估计矩阵中未观测的条目。我们考虑非均匀设置，其中观测条目根据高度变化的概率进行采样，可能具有不同的渐近尺度。我们证明了在结构化采样概率下，使用较小的子矩阵而不是整个矩阵上运行估计算法通常更好，有时是最优的。特别地，在某些条件下，我们证明了适用于每个条目的错误上界，这些错误上界与最小化下界相匹配。我们提供了数值实验证实了我们的理论发现。

Abstract

low-rank matrix completion concerns the problem of estimating unobserved entries in a matrix using a sparse set of observed entries. We consider the non-uniform setting where the observed entries are sampled with

low-rank matrix completion non-uniform setting structured sampling probabilities estimation algorithms minimax lower bounds

发现论文，激发创造

受限强凸性与加权矩阵补全：带噪声的最优界限

该研究针对一种形式的行 / 列加权采样的矩阵完成问题进行了分析，提出了一种基于 $M$-estimator 的技术，通过对解的秩和 spikiness 同时进行控制，在加权 Frobenius 范数下建立了一些误差界限，其中关于矩阵的 “spikiness” 和 “low-rankness” 的度量比以前的工作限制更少。

Sep, 2010

矩阵完成的简单方法

本文通过最小化矩阵的核范数，结合已知信息来重建未知的低秩矩阵，并证明了在满足特定的 “不连贯条件” 的情况下，所需的样本量等于参数数量的二次对数因子。这一结论是基于量子信息理论的最新工作，相较于之前的结果，提供了更好的界限。

Oct, 2009

来自一般确定性采样模式的矩阵补全

该论文针对低秩矩阵完成算法的理论保证存在严格且近似的情况，可以应用于任何确定性采样计划。通过引入一个图形来解决观察条目的性能问题，论文从理论和实验角度论证了算法的成功性。

Jun, 2023

自适应采样的低秩矩阵和张量补全

研究低秩矩阵和张量完成，提出了采用自适应抽样方案的新算法，它们具有强大的性能保证，并能够恢复具有噪声干扰的低秩矩阵。

Apr, 2013

有限样本下精确快速矩阵补全

该论文提出了一种矩阵完成问题的快速迭代算法，该算法观测到 O (nr^5log^3 n) 的条目，具有确定的样本复杂度，可以解决低秩矩阵恢复的问题。