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

DOI10.1093/imaiai/iaw004zbMath1386.94037arXiv1505.03001OpenAlexW2258814563MaRDI QIDQ4603728

Boaz Nadler, Ofer Shwartz

Publication date: 19 February 2018

Published in: Information and Inference (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)

Related Items (1)

Learning directed acyclic graph SPNs in sub-quadratic time

Uses Software

• MLPACK
• spcov

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparse estimation of a covariance matrix
• Combinatorial sublinear-time Fourier algorithms
• A note on compressed sensing and the complexity of matrix multiplication
• Covariance regularization by thresholding
• 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.
• A randomized approximate nearest neighbors algorithm
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
• Adaptive Thresholding for Sparse Covariance Matrix Estimation
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Estimation of a covariance matrix with zeros
• Near-optimal sparse fourier representations via sampling
• Similarity estimation techniques from rounding algorithms
• Multidimensional binary search trees used for associative searching
• On Consistency and Sparsity for Principal Components Analysis in High Dimensions
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Locality-sensitive hashing scheme based on p-stable distributions
• Nearly optimal sparse fourier transform
• Multiplying matrices faster than coppersmith-winograd
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Compressed matrix multiplication

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