Spectrum Estimation from a Few Entries
This addresses a fundamental challenge in applications like collaborative filtering and network analysis where only partial data is available, offering a more sample-efficient way to recover spectral properties, though it is incremental as it builds on existing norm estimation techniques.
The paper tackles the problem of estimating the singular value spectrum of a matrix from only a few observed entries, proposing a method that uses Schatten norm estimation and Chebyshev approximation or moment matching, with theoretical guarantees showing accurate recovery from fewer samples than needed for full matrix completion and numerical experiments indicating significant improvement over competing approaches.
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.