Detecting the large entries of a sparse covariance matrix in sub-quadratic time

DOI10.1093/IMAIAI/IAW004zbMATH Open1386.94037arXiv1505.03001OpenAlexW2258814563MaRDI QIDQ4603728FDOQ4603728

Authors: Ofer Shwartz, Boaz Nadler 

Publication date: 19 February 2018

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: The covariance matrix of a $p$-dimensional random variable is a fundamental quantity in data analysis. Given $n$ i.i.d. observations, it is typically estimated by the sample covariance matrix, at a computational cost of $O(n{p}^2)$ operations. When $n,p$ are large, this computation may be prohibitively slow. Moreover, in several contemporary applications, the population matrix is approximately sparse, and only its few large entries are of interest. This raises the following question, at the focus of our work: Assuming approximate sparsity of the covariance matrix, can its large entries be detected much faster, say in sub-quadratic time, without explicitly computing all its $p^2$ entries? In this paper, we present and theoretically analyze two randomized algorithms that detect the large entries of an approximately sparse sample covariance matrix using only $O(npextpolylogp)$ operations. Furthermore, assuming sparsity of the population matrix, we derive sufficient conditions on the underlying random variable and on the number of samples $n$, for the sample covariance matrix to satisfy our approximate sparsity requirements. Finally, we illustrate the performance of our algorithms via several simulations.

Full work available at URL: https://arxiv.org/abs/1505.03001

Recommendations

• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Sparse PCA via covariance thresholding
• An empirical estimator for the sparsity of a large covariance matrix under multivariate normal assumptions
• Statistical and computational limits for sparse matrix detection
• Large-scale sparse inverse covariance matrix estimation

zbMATH Keywords

sparse covariance matrixmulti-scale group testingsub-quadratic time complexity

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Detection theory in information and communication theory (94A13)

Cites Work

• Sparse estimation of a covariance matrix
• Title not available (Why is that?)
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Covariance regularization by thresholding
• Title not available (Why is that?)
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Operator norm consistent estimation of large-dimensional sparse covariance matrices
• Spectrum estimation for large dimensional covariance matrices using random matrix theory
• Adaptive estimation of a quadratic functional by model selection.
• Adaptive Thresholding for Sparse Covariance Matrix Estimation
• Similarity estimation techniques from rounding algorithms
• Near-optimal sparse fourier representations via sampling
• Nearly optimal sparse fourier transform
• Multiplying matrices faster than coppersmith-winograd
• Combinatorial sublinear-time Fourier algorithms
• Estimation of a covariance matrix with zeros
• Multidimensional binary search trees used for associative searching
• Locality-sensitive hashing scheme based on p-stable distributions
• Approximate nearest neighbor: towards removing the curse of dimensionality
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• A randomized approximate nearest neighbors algorithm
• A note on compressed sensing and the complexity of matrix multiplication
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• Compressed matrix multiplication

Cited In (1)

• Learning directed acyclic graph SPNs in sub-quadratic time

Uses Software

• MLPACK
• spcov

This page was built for publication: Detecting the large entries of a sparse covariance matrix in sub-quadratic time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603728)