摘要翻译：
Nystrom方法是一种通过生成低秩近似来加快大规模学习应用的有效技术。对于这种技术的性能至关重要的是这样一个假设，即矩阵可以通过独占地处理其列的子集来很好地近似。在本工作中，我们将这一假设与矩阵相干性的概念联系起来，并将矩阵相干性与Nystrom方法的性能联系起来。利用压缩感知领域的相关工作和矩阵补全文献，我们在低秩条件下给出了Nystrom方法的新的基于相干性的边界。然后，我们给出了实证结果，证实了这些理论界限。最后，我们给出了更一般的全秩设置的实证结果，这些结果令人信服地证明了矩阵一致性能够度量从一个列子集中提取信息的程度。
---
英文标题：
《Matrix Coherence and the Nystrom Method》
---
作者：
Ameet Talwalkar and Afshin Rostamizadeh
---
最新提交年份：
2010
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  The Nystrom method is an efficient technique to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this assumption to the concept of matrix coherence and connect matrix coherence to the performance of the Nystrom method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystrom method in the low-rank setting. We then present empirical results that corroborate these theoretical bounds. Finally, we present more general empirical results for the full-rank setting that convincingly demonstrate the ability of matrix coherence to measure the degree to which information can be extracted from a subset of columns.
---
PDF链接：
https://arxiv.org/pdf/1004.2008