Active covariance estimation by random sub-sampling of variables

Eduardo Pavez, Antonio OrtegaarXiv 2018 · arXiv

TL;DR

This paper introduces an active learning framework for estimating covariance matrices from partially observed data. By deriving a new error bound that links sampling probabilities to the underlying covariance structure, the authors develop an adaptive algorithm that learns how to sample variables optimally, significantly outperforming uniform sampling in scenarios where the data has a low effective rank.

What Problem Does This Paper Address?

Estimating a covariance matrix is a cornerstone of multivariate statistics, but in many real-world scenarios, we cannot observe every variable simultaneously. This happens due to physical limitations (e.g., a sensor network with limited bandwidth) or intentional design to reduce costs (active learning).

While previous work often focused on "Missing Completely at Random" (MCAR) models where every variable has the same probability of being lost, this paper tackles a more flexible and controllable scenario. The authors ask: if we have a fixed "budget" for how many variables we can sample on average, how should we distribute that budget across different variables to minimize our estimation error?

Methods

The authors model the observation process using a Bernoulli sub-sampling approach. For a random vector $x$, they observe $y = \delta \odot x$, where $\delta$ is a vector of 0-1 Bernoulli variables. Each variable $x_i$ is observed with a known probability $p_i$.

Key components of their approach include:

  • Unbiased Estimator: They use an entry-wise unbiased estimator that scales the empirical products of observed variables by the inverse of their joint observation probabilities.
  • Theoretical Error Bound: The core contribution is Theorem 1, which provides an error bound for the Frobenius norm of the estimation error. This bound explicitly relates the error to the sampling probabilities $p_i$ and the sub-exponential norms of the variables.
  • Active Learning Algorithm: Based on their theoretical bound, they propose Algorithm 1 (Active Covariance Estimation). This is a batch-based iterative process:
  • Sample a batch of data using current probabilities.
  • Update the covariance estimate.
  • Solve a "scaled projection problem" to refine the sampling probabilities $p$ for the next batch, prioritizing variables that contribute most to the potential error.
Algorithm 1: Covariance estimation with adaptive sampling

Datasets

The authors evaluated their method using the MNIST dataset, specifically focusing on the set of 5,851 images of the digit "8". The images were vectorized and mean-centered. To test the robustness of the algorithm, they added varying levels of Gaussian noise to the data, which allowed them to control the effective rank of the resulting covariance matrix.

Key Insights and Ideas

  • Variance-Driven Sampling: The error bound suggests that variables with higher variance (larger diagonal entries in the covariance matrix) should be sampled more frequently.
  • The Power of Low Rank: A major finding is that if a covariance matrix is approximately low-rank (meaning most of its energy is concentrated in a few principal components), active sampling can perform nearly as well as an estimator that sees the full data.
  • Effective Rank as a Difficulty Metric: The authors use the ratio $r(\Sigma) = \text{tr}(\Sigma)/\|\Sigma\|$ to quantify difficulty. A lower effective rank means the data is more "structured," making active learning more beneficial.
  • Closing the Gap: The active algorithm doesn't need to know the true covariance upfront. It starts with uniform sampling and quickly "learns" the optimal non-uniform distribution, eventually matching the performance of an "oracle" that knows the true covariance from the start.

Key Results

The experimental results, visualized in the paper's figures, demonstrate several key points:

  • Non-uniform vs. Uniform: Non-uniform sampling consistently outperforms uniform sampling. For example, with a budget of 75% of the variables ($m=0.75n$), non-uniform sampling closely matches the performance of full-data estimation.
  • Adaptivity: As shown in the active learning plots, the proposed algorithm (A) quickly converges to the performance of the optimal non-uniform sampling strategy (P).
  • Impact of Rank: When the effective rank is increased (by adding more noise), the advantage of active sampling over uniform sampling diminishes, as the "information" is spread more thinly across all variables.
Performance of different covariance estimators in relative Frobenius norm. (a) compares uniform vs non-uniform, (b) shows the active method matching the oracle, and (c) shows performance with higher effective rank.

Limitations and Future Work

The authors acknowledge that while their method is effective, its advantages are limited when the effective rank of the matrix is high or when the diagonal entries of the covariance matrix have very similar magnitudes.

Future work could involve developing more precise methods for updating the sampling probabilities $p$ beyond the current scaled projection heuristic. Additionally, exploring how these bounds apply to other norms (like the spectral norm) or different observation models (like sparse projections) remains an open area for research.

Summary updated

Abstract

We study covariance matrix estimation for the case of partially observed random vectors, where different samples contain different subsets of vector coordinates. Each observation is the product of the variable of interest with a $0-1$ Bernoulli random variable. We analyze an unbiased covariance estimator under this model, and derive an error bound that reveals relations between the sub-sampling probabilities and the entries of the covariance matrix. We apply our analysis in an active learning framework, where the expected number of observed variables is small compared to the dimension of the vector of interest, and propose a design of optimal sub-sampling probabilities and an active covariance matrix estimation algorithm.
BibTeX
@misc{pavez2018active,
  author = {Eduardo Pavez and Antonio Ortega},
  title = {{Active covariance estimation by random sub-sampling of variables}},
  year = {2018},
  eprint = {1804.01620},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.01620},
}

Loading related content...

Figure