来自一般确定性采样模式的矩阵补全
使用图极限理论规定的某一必要且充分条件,对于一系列矩阵补全问题,只需对 Candès-Recht 核范数最小化算法进行微小修改即可提供所需的渐近解,该理论是完全确定性的,没有随机性假设,同时列出了一些未解决的问题。
Oct, 2019
提出通过使用具有大切比雪夫谱差的二分图边集进行矩阵完成的广泛采样方案,可以精确地恢复所有满足一定不相干性条件的低秩矩阵,而只需 O(nr^2)个随机样本条目。同时改进了已有的矩阵完成算法和核范数方法的分析,与之相比,其样本复杂度为 O(nrlogn)
Feb, 2014
本文研究低秩矩阵完成问题,提出了一种用于确定有限可完成性的确定性采样条件,展示了在随机采样下,以 O(max(r,log d))的采样数完成矩阵的特定条件可以高概率满足,并探讨了该发现对 LRMC 的意义与应用。
Mar, 2015
本研究倡导并分析了一种基于 max-norm 的方法,在一般的采样模型下进行有噪声矩阵补全,该方法在解决低秩矩阵重构中具有最佳收敛速度,且面对不同采样分布显现出统一且稳健的近似恢复性能,同时也通过解决一阶算法来讨论该方法的计算有效性。
Mar, 2013
本文提出了一种特定偏向分布的采样方式,利用该采样方式可以从少量采样的数据中精确恢复任何秩为 r 的 nxn 的矩阵(无需满足之前已有的结构限制要求),而且在没有先验信息下本文建立了三种使用该采样方式的方法,其中还包括分析了针对非均匀采样情形中,加权核范数 / 迹范数惩罚的优点。
Jun, 2013
低秩矩阵补全问题关注使用稀疏观测的一组观测条目来估计矩阵中未观测的条目。我们考虑非均匀设置,其中观测条目根据高度变化的概率进行采样,可能具有不同的渐近尺度。我们证明了在结构化采样概率下,使用较小的子矩阵而不是整个矩阵上运行估计算法通常更好,有时是最优的。特别地,在某些条件下,我们证明了适用于每个条目的错误上界,这些错误上界与最小化下界相匹配。我们提供了数值实验证实了我们的理论发现。
Feb, 2024