Sketching for Simultaneously Sparse and Low-Rank Covariance Matrices

2015/10/06 by Bahmani, Sohail, Romberg, Justin
#FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Numerical Analysis (math.NA) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1510.01670

Abstract

We introduce a technique for estimating a structured covariance matrix from observations of a random vector which have been sketched. Each observed random vector \boldsymbolx_t is reduced to a single number by taking its inner product against one of a number of pre-selected vector \boldsymbola_ℓ. These observations are used to form estimates of linear observations of the covariance matrix \boldsymbol\varSigma, which is assumed to be simultaneously sparse and low-rank. We show that if the sketching vectors \boldsymbola_ℓ have a special structure, then we can use straightforward two-stage algorithm that exploits this structure. We show that the estimate is accurate when the number of sketches is proportional to the maximum of the rank times the number of significant rows/columns of \boldsymbol\varSigma. Moreover, our algorithm takes direct advantage of the low-rank structure of \boldsymbol\varSigma by only manipulating matrices that are far smaller than the original covariance matrix.

Related

• Robust recovery of low-rank matrices and low-tubal-rank tensors from noisy sketches
• Precise expressions for random projections: Low-rank approximation and\n randomized Newton
• Matrix Product Sketching via Coordinated Sampling
• Sparse sketches with small inversion bias
• Sketching Low-Rank Plus Diagonal Matrices