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:
- 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.
- 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.
- 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).
- Spectrum Recovery: Once the first few Schatten norms (moments) are estimated, the authors use:
- Chebyshev Polynomials to approximate spectral sum functions (like rank).
- 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