Spectrum Estimation from a Few Entries

Ashish Khetan, Sewoong Oh

TL;DR

This paper introduces a novel, unbiased estimator for the singular values (spectrum) of a matrix when only a small fraction of its entries are observed. By estimating Schatten $k$-norms through a graph-theoretic approach—counting small structures like closed walks—the authors show that spectral properties can be recovered with significantly fewer samples than what is required to reconstruct the entire matrix.

What Problem Does This Paper Address?

In fields like recommendation systems (collaborative filtering) or network analysis, we often deal with massive matrices where most entries are unknown. Traditional matrix completion techniques aim to fill in these missing values, but they require a relatively high number of samples—typically $O(rd \log d)$ for a rank-$r$ matrix of size $d \times d$.

However, in many practical scenarios, we don't actually need the full matrix. We might only care about its spectral properties: the singular values that reveal the data's effective dimensionality, the underlying rank, or "spectral sum functions" (like the log-determinant or trace of the inverse). The core question this paper tackles is: Can we estimate the spectrum of a matrix using fewer samples than it takes to complete it?

Methods

The authors propose a framework that bypasses full matrix reconstruction by focusing on Schatten $k$-norms, which are defined as the $k$-th power sum of the singular values: $\|M\|_k^k = \sum \sigma_i(M)^k$.

Key technical components include:

  1. Trace-Walk Duality: For a positive semi-definite matrix, the Schatten $k$-norm is equal to the trace of $M^k$. This trace can be interpreted as the sum of weights of all "closed walks" of length $k$ in a graph where matrix entries are edge weights.
  2. Unbiased Estimator: Simply calculating the trace of the sampled matrix (with zeros for missing entries) is heavily biased. The authors introduce a de-biasing technique that rescales the weight of each walk pattern (or "pseudograph") by the inverse of its sampling probability.
  3. Efficient Counting: While counting all walks is generally hard, the authors provide a novel algorithm using matrix operations to exactly compute these estimates for $k \leq 7$ in $O(d^\alpha)$ time (where $\alpha$ is the matrix multiplication exponent).
  4. Spectrum Recovery: Once the first few Schatten norms (moments) are estimated, the authors use:
  5. Chebyshev Polynomials to approximate spectral sum functions (like rank).
  6. Moment Matching in Wasserstein Distance to reconstruct the distribution of singular values (the histogram of the spectrum).

Datasets

The paper primarily evaluates its methods using synthetic datasets to provide rigorous ground-truth comparisons:

  • Positive Semi-Definite Matrices: Generated with varying dimensions ($d=500, 1000$) and ranks ($r$ ranging from 50 to 500).
  • Singular Value Distributions: The authors tested "one-peak" (all singular values equal to 1) and "two-peak" (half at 1, half at 2) distributions to see how well the estimator recovers the spectral shape.
  • Sampling Models: They utilized both the standard Erdős-Rényi sampling (independent random entries) and a more general Graph Sampling model (fixed pattern with random node relabeling).

Key Insights and Ideas

  • The "Sub-linear" Advantage: The most striking insight is that Schatten norms can be recovered accurately in the "sub-linear" regime. Specifically, they show a sample complexity of $O(dr^{1-2/k})$, which is strictly smaller than the $O(rd \log d)$ threshold needed for matrix completion.
  • Moments are Enough: You don't need to see every entry to understand the global "shape" of the data. The first few moments of the singular value distribution contain enough information to reconstruct the spectrum's histogram.
  • Pattern Matters: Under the "Graph Sampling" model, the authors discovered that the specific structure of the sampling pattern (e.g., whether you sample a clique or a "clique-star") drastically changes the difficulty of the estimation problem.

Key Results

  • Superiority over Baselines: In numerical experiments, the proposed estimator significantly outperformed both "scaled sampled matrices" and state-of-the-art matrix completion algorithms (like AltMin) when the number of samples was low (see Figure 4 and 7 in the paper).
  • Rank Estimation: The method accurately estimated the "generalized rank" even when matrix completion failed to recover any entries correctly.
  • Spectrum Reconstruction: As the sampling probability $p$ increases, the estimated Cumulative Distribution Function (CDF) of the singular values converges rapidly to the true CDF, even with a small number of moments ($K=7$).

Limitations and Future Work

  • The $k=8$ Wall: The computational approach hits a complexity wall at $k=8$. Counting structures equivalent to $K_4$ (a 4-node clique) is fundamentally harder and likely requires $O(d^{\alpha+1})$ time, making it less practical for very large $k$.
  • Variance Bounds: The theoretical analysis assumes a "worst-case" where all weights are positive. In reality, matrices with negative entries might benefit from stochastic cancellations, which the current analysis doesn't fully capture.
  • Parameter Tuning: For rank estimation, the user must still choose thresholds ($c_1, c_2$) and the degree of polynomial approximation, which may require some domain knowledge.
  • Future Direction: Extending this to non-square matrices and exploring more complex real-world sampling patterns (beyond Erdős-Rényi) are noted as interesting next steps.

Summary updated

Abstract

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.
BibTeX
@article{khetan2019spectrum,
  author = {Ashish Khetan and Sewoong Oh},
  title = {{Spectrum Estimation from a Few Entries}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=JNhMHf2hEE},
}
Figure