Additive Error Guarantees for Weighted Low Rank Approximation
Additive Error Guarantees for Weighted Low Rank Approximation
复制标题
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Aditya Bhaskara;Aravinda Kanchana Ruwanpathirana;Pruthuvi Maheshakya Wijewardena
中科院分区：
文献类型：
--
作者：
Aditya Bhaskara;Aravinda Kanchana Ruwanpathirana;Pruthuvi Maheshakya Wijewardena
低级别近似是数据分析中的经典工具，其目标是近似具有低级数矩阵L的矩阵A，以最大程度地减少误差（CID：107）A-L（CID：107）2 f。但是，在许多应用程序中，近似某些条目比其他条目更重要，这导致了加权近似问题。在重量矩阵上的其他结构假设下（例如低等级和适当的块结构），我们研究一种天然的贪婪算法。算法中的添加因子涉及适当变化的矩阵的顶部奇异向量，因此很容易在我们的情况下实现方法还使我们能够研究（CID：96）P规范误差之下低等级近似问题的问题。
Low-rank approximation is a classic tool in data analysis, where the goal is to approximate a matrix A with a low-rank matrix L so as to minimize the error (cid:107) A − L (cid:107) 2 F . However in many applications, approximating some entries is more important than others, which leads to the weighted low rank approximation problem. However, the addition of weights makes the low-rank approximation problem intractable. Thus many works have obtained efficient algorithms under additional structural assumptions on the weight matrix (such as low rank, and appropriate block structure). We study a natural greedy algorithm for weighted low rank approximation and develop a simple condition under which it yields bi-criteria approximation up to a small additive factor in the error. The algorithm involves iteratively computing the top singular vector of an appropriately varying matrix, and is thus easy to implement at scale. Our methods also allow us to study the problem of low rank approximation under (cid:96) p norm error.