May, 2024

核矩阵的低秩逼近入元误差界限

PDF
TL;DR通过截断奇异值分解，我们推导了低秩近似核矩阵的逐元素误差界。尽管这种近似在谱范数和弗罗贝尼乌斯范数误差方面是最优的，但对于单个元素的统计行为知之甚少。我们的误差界填补了这一空白。关键的技术创新是对应于小特征值的核矩阵的特征向量的非定位化结果，这得益于随机矩阵理论领域的启发。最后，我们通过对一系列合成数据集和真实数据集的实证研究验证了我们的理论。
发现论文，激发创造
  • 期望低秩随机矩阵的逐项特征向量分析

    本文通过证明一类随机矩阵的特征向量的近似线性关系，为完全恢复固定堆砌模型的谱算法提供了第一种严格无修剪方法。

    Sep, 2017

  • 低秩强化学习光谱逐项矩阵估计

    研究低秩结构引发的强化学习中的矩阵估计问题，通过简单的基于谱的方法高效地恢复矩阵的奇异子空间并实现最小的逐项误差，从而设计了充分利用低秩结构的强化学习算法，包括低秩赌博机问题的最小遗憾算法和低秩马尔可夫决策过程中的无奖励 RL 的最佳策略识别算法，两种算法均具有最先进的性能保证。

    Oct, 2023

  • 从最少数量的随机测量中紧凑的针对低秩矩阵恢复的预言界限

    本文研究了低秩矩阵通过线性组合测量进行恢复的方法，结果表明经过妥善约束的核范数最小化可以从恒定数量的带有噪声的测量中稳定地恢复低秩矩阵，从噪声数据中恢复误差不超过三个目标。同时，本文对低秩矩阵的误差界限进行了扩展，并基于限制等距性质进行了分析。

    Jan, 2010

  • 入项变换矩阵乘积的低秩逼近难度

    在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。

    Nov, 2023

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

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

    Feb, 2024

  • 低秩矩阵分解的随机算法：尖锐性能界限

    本文研究文献中关于维数约减最常讨论的算法之一，即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人（2008）中算法的新颖分析方法，可以得出尖锐的估计和关于其性能的新见解。通过实验，我们证明了我们预测的紧密性与经验观测的一致性。

    Aug, 2013

  • 关于核学习的复杂性

    本文主要研究降低核矩阵计算成本的方法，并针对观测的核矩阵条目数或近似核矩阵的秩，确定这些方法在错误达到下限的条件。研究结果表明损失函数，正则化参数，期望预测器的范数和核矩阵秩等参数与问题难度有关，同时提出了更高效的核学习可能的情况。

    Nov, 2014

  • 样本协方差矩阵最小特征值的下界

    本研究推导了一个中心各向同性随机向量的样本协方差矩阵最小特征值的下界，即使对其构成部分没有强假设或无假设时也成立。

    Sep, 2014

  • 一种 l∞特征值扰动界及其在鲁棒协方差估计中的应用

    该论文针对矩阵扰动中的特征向量进行了研究，证明了当矩阵是低秩和不相干的时候，奇异向量的（或对称情况下的特征向量）l∞范数扰动界限比 l2 范数扰动界限更小一个因子。作者在稳健协方差估计方面提出了新的建模方法，并利用所开发的扰动界限确立其渐近性质。

    Mar, 2016

  • 矩阵完成的简单方法

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

    Oct, 2009