Can matrix coherence be efficiently and accurately estimated?

Mehryar Mohri, Ameet TalwalkarAISTATS 2011 · OpenReview

Introduction

In the era of massive datasets, low-rank approximations like the Nyström method or column-sampling are essential for handling matrices that exceed memory capacity. These techniques rely on a critical property called coherence. Coherence measures how evenly information is distributed across a matrix. If a matrix is "incoherent," random sampling works effectively; if it is "highly coherent," important information may be concentrated in a few entries, causing sampling-based methods to fail.

This creates a "chicken-and-egg" problem: to determine if a matrix is incoherent enough for fast algorithms to be reliable, one traditionally needs to perform a Singular Value Decomposition (SVD) on the entire matrix. However, a full SVD is the very expensive computation these algorithms aim to avoid. This paper investigates whether matrix coherence can be accurately estimated by examining only a small subset of columns.

The ESTIMATE-COHERENCE Algorithm

The authors propose a straightforward sampling-based approach to resolve this bottleneck. The ESTIMATE-COHERENCE algorithm follows four primary steps:

  1. Sample: Select a small number of columns ($l$) from the original matrix.
  2. Decompose: Perform an SVD on this reduced submatrix.
  3. Truncate: Retain only the top $r$ singular vectors, where $r$ is the target rank.
  4. Calculate: Estimate the coherence ($\gamma$) based on the maximum row norms of these singular vectors.

This algorithm runs in $O(nl^2)$ time, where $n$ is the number of rows. This is significantly more efficient than the $O(n^2m)$ or $O(nm^2)$ required for a full SVD on an $n \times m$ matrix.

Theoretical Bounds and the Worst Case

The paper establishes that the coherence estimate is monotonically increasing, meaning it serves as a "safe" lower bound. If the estimate is already high, the matrix is definitely coherent, and approximation methods will likely fail.

However, theoretical analysis also reveals a "pathological" lower bound. For certain adversarial matrices, no sampling-based method can accurately estimate coherence without observing nearly the entire matrix.

Theoretical worst-case scenario where coherence estimation remains inaccurate until the entire matrix is sampled.

Empirical Performance on Real-World Data

While the worst-case theory suggests potential failure, the authors find a significant "theory-practice gap." On real-world datasets—ranging from text (NIPS, Dexter) and images (MNIST, PIE) to protein data (Essential) and robotics (KIN-8nm)—the algorithm performs remarkably well.

Estimation accuracy and its correlation with reconstruction error across various real-world datasets.

As shown in the experimental results, the estimated coherence converges to the true value rapidly, often requiring only a few hundred sampled columns. Furthermore, the estimated coherence serves as an excellent diagnostic tool, accurately predicting the "Normalized Error" one would encounter when applying Nyström or column-sampling approximations. Even under significant noise, the algorithm remains robust, particularly when the number of samples $l$ is approximately four times the target rank $r$.

Conclusion

Despite the existence of theoretical worst-case scenarios, the ESTIMATE-COHERENCE algorithm proves to be a highly effective tool for practitioners. It allows for the efficient validation of low-rank approximation methods, ensuring that massive datasets can be processed reliably without the prohibitive cost of a full matrix decomposition. Future work may involve using variance across multiple samples to provide confidence intervals, further enhancing the tool's utility as a diagnostic for machine learning pipelines.

Summary updated

BibTeX
@inproceedings{mohri2011can,
  author = {Mehryar Mohri and Ameet Talwalkar},
  title = {{Can matrix coherence be efficiently and accurately estimated?}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=tzL1EID1mNG},
}
Figure