The Sparse Matrix Transform for Covariance Estimation and Analysis of High Dimensional Signals

TLDR

Covariance estimation in high‑dimensional signal analysis is notoriously difficult, and the sparse matrix transform (SMT) extends the fast Fourier transform to enable fast eigen‑signal analysis of non‑stationary signals. The paper proposes a maximum‑likelihood covariance estimation method that incorporates a novel non‑linear sparsity constraint. The method constrains the covariance’s eigen‑decomposition to a sparse matrix transform built from Givens rotations, and estimates it by greedy optimization of the log‑likelihood with cross‑validated selection of the number of rotations. The SMT‑based estimator is positive definite, well‑conditioned with small samples, outperforms shrinkage and graphical lasso methods on simulated, hyperspectral, and face image data, and enables fast eigen‑transformation via its SMT representation.

Abstract

Covariance estimation for high dimensional signals is a classically difficult problem in statistical signal analysis and machine learning. In this paper, we propose a maximum likelihood (ML) approach to covariance estimation, which employs a novel non-linear sparsity constraint. More specifically, the covariance is constrained to have an eigen decomposition which can be represented as a sparse matrix transform (SMT). The SMT is formed by a product of pairwise coordinate rotations known as Givens rotations. Using this framework, the covariance can be efficiently estimated using greedy optimization of the log-likelihood function, and the number of Givens rotations can be efficiently computed using a cross-validation procedure. The resulting estimator is generally positive definite and well-conditioned, even when the sample size is limited. Experiments on a combination of simulated data, standard hyperspectral data, and face image sets show that the SMT-based covariance estimates are consistently more accurate than both traditional shrinkage estimates and recently proposed graphical lasso estimates for a variety of different classes and sample sizes. An important property of the new covariance estimate is that it naturally yields a fast implementation of the estimated eigen-transformation using the SMT representation. In fact, the SMT can be viewed as a generalization of the classical fast Fourier transform (FFT) in that it uses "butterflies" to represent an orthonormal transform. However, unlike the FFT, the SMT can be used for fast eigen-signal analysis of general non-stationary signals.