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

DOI10.1093/IMAIAI/IAW004MaRDI QIDQ4603728zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(1)

• Learning directed acyclic graph SPNs in sub-quadratic time

Describes a project that uses

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)