Spectrum Estimation from a Few Entries
Spectrum Estimation from a Few Entries
复制标题
从几个条目进行频谱估计
DOI：
10.1016/j.aml.2021.107342
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sewoong Oh
中科院分区：
文献类型：
--
作者：
A. Khetan;Sewoong Oh
矩阵形式数据的奇异值为数据结构、有效维度以及高级数据分析工具中超参数的选择提供了见解。然而，在许多实际应用中，比如协同过滤和网络分析，我们只能得到部分观测值。在这种情况下，我们考虑从矩阵元素的抽样中恢复基础矩阵的谱性质这一基本问题。我们尤其对直接恢复谱（即奇异值的集合）感兴趣，也对恢复谱和函数（即对每个奇异值应用相同函数后的总和）的高效抽样方法感兴趣。我们首先提出估计矩阵的Schatten $k$-范数，然后对谱和函数应用切比雪夫逼近，或者在瓦瑟斯坦距离中应用矩匹配来恢复奇异值。主要的技术挑战在于从矩阵抽样中准确估计Schatten范数。我们引入了一种基于计算图中小结构的新型无偏估计量，并提供了与其经验性能相符的保证。我们的理论分析表明，与恢复基础低秩矩阵所需的样本数量相比，从严格更少的样本中就能准确恢复Schatten范数。数值实验表明，我们相较于使用矩阵补全方法的竞争方法有显著改进。
Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis, we only get a partial observation. Under such scenarios, we consider the fundamental problem of recovering spectral properties of the underlying matrix from a sampling of its entries. We are particularly interested in directly recovering the spectrum, which is the set of singular values, and also in sample-efficient approaches for recovering a spectral sum function, which is an aggregate sum of the same function applied to each of the singular values. We propose first estimating the Schatten $k$-norms of a matrix, and then applying Chebyshev approximation to the spectral sum function or applying moment matching in Wasserstein distance to recover the singular values. The main technical challenge is in accurately estimating the Schatten norms from a sampling of a matrix. We introduce a novel unbiased estimator based on counting small structures in a graph and provide guarantees that match its empirical performance. Our theoretical analysis shows that Schatten norms can be recovered accurately from strictly smaller number of samples compared to what is needed to recover the underlying low-rank matrix. Numerical experiments suggest that we significantly improve upon a competing approach of using matrix completion methods.
影响因子：
30.8
作者：
Shen-Orr, SS;Milo, R;Alon, U
通讯作者：
Alon, U