Sufficient ensemble size for random matrix theory-based handling of singular covariance matrices

Ata KabánAnalysis 2020 · DOI

Abstract

Singular covariance matrices are frequently encountered in both machine learning and optimization problems, most commonly due to high dimensionality of data and insufficient sample sizes. Among many methods of regularization, here we focus on a relatively recent random matrix-theoretic approach, the idea of which is to create well-conditioned approximations of a singular covariance matrix and its inverse by taking the expectation of its random projections. We are interested in the error of a Monte Carlo implementation of this approach, which allows subsequent parallel processing in low dimensions in practice. We find that $O(d)$ random projections, where $d$ is the size of the original matrix, are sufficient for the Monte Carlo error to become negligible, in the sense of expected spectral norm difference, for both covariance and inverse covariance approximation, in the latter case under mild assumptions.

Introduction

In the contemporary landscape of high-dimensional machine learning and optimization, practitioners frequently encounter the "small $n$, large $d$" problem. When the number of features ($d$) exceeds the number of samples ($n$), the resulting sample covariance matrix is inherently singular. This lack of full rank poses significant challenges for algorithms that rely on matrix inversion, such as Gaussian classifiers, least-squares regression, and various optimization routines.

Traditional regularization techniques, such as Ledoit-Wolf shrinkage or Lasso-based sparsity constraints, are often employed to mitigate these issues. However, a more recent approach rooted in Random Matrix Theory (RMT) offers a compelling alternative. This method involves approximating the covariance matrix (or its inverse) by averaging its projections into lower-dimensional subspaces. While the theoretical expectation of these projections yields a well-conditioned, non-singular approximation, practical implementations must rely on a finite Monte Carlo average. The critical question for the viability of this method is the required ensemble size ($m$): how many projections are necessary to ensure a negligible approximation error?

Methodology

The study focuses on two primary approximators derived from random projections:

  1. $\hat{cov}_k(M)$: An approximation of the covariance matrix $M$.
  2. $\hat{cov}_k^{-1}(M)$: An approximation of the inverse covariance (precision) matrix.

The core idea is to project a high-dimensional matrix $M$ into a $k$-dimensional space ($k < d$) using a random matrix $R$, and then "lift" the result back to the original $d$-dimensional space. By repeating this process $m$ times and taking the average, we obtain a Monte Carlo estimate of the true expectation.

To establish the necessary ensemble size, the author utilizes the Matrix Strong Regularity (MSR) condition. The proof strategy involves a "splitting device" that decomposes the random matrices into components corresponding to the range space (where the signal resides) and the null space (the dimensions containing noise or no data).

For the covariance approximator, the analysis leverages the properties of log-concave distributions, which exhibit strong concentration of measure. The inverse covariance approximator presents a greater challenge, as the inversion process introduces heavy-tailed distributions—specifically, matrix-variate T-distributions. To handle this, the author applies Chernoff-type bounds to demonstrate that these distributions still satisfy the MSR condition under certain conditions.

Theoretical Results

The primary contribution of this work is the formal proof that an ensemble size of $m = O(d)$ is sufficient to make the expected spectral norm difference between the finite Monte Carlo average and the true expectation negligible.

This result is significant for several reasons:

  • Elimination of the Logarithmic Factor: Standard matrix concentration inequalities often suggest a scaling of $O(d \log d)$. By exploiting the specific structure of random projection ensembles, this work proves that the $\log d$ factor is unnecessary, leading to a tighter linear bound.
  • Conditions for Inverses: The $O(d)$ bound for the inverse approximation holds under the "mild assumption" that the rank of the original matrix ($\rho$) is at least logarithmic relative to the dimension of the null space. This ensures the matrix is not "too empty" to be effectively approximated.
  • Invariance to Projection Dimension: The linear scaling $O(d)$ remains robust regardless of the chosen projection dimension $k$, although the specific constant of proportionality may vary.

Numerical Verification

To validate the theoretical findings, numerical experiments were conducted using synthetic singular matrices with a fixed rank of $\rho = 50$. The ambient dimension $d$ was varied from 60 to 140. The experiments measured the ensemble size $m$ required to achieve a specific error threshold ($\epsilon = 0.5$).

The results confirmed a clear linear relationship between the dimension $d$ and the required ensemble size $m$. In practical applications, such as continuous optimization, the author observes that a constant factor as low as $1d$ or $2d$ often provides sufficient accuracy, offering a concrete rule of thumb for implementation.

Conclusion and Future Directions

This research provides a rigorous theoretical foundation for the use of random projection ensembles in handling singular covariance matrices. By proving that $O(d)$ projections are sufficient, the work guarantees the computational efficiency and scalability of these methods. Furthermore, because the Monte Carlo average is a sum of independent projections, the approach is inherently parallelizable.

Future work may address the determination of the optimal projection dimension $k$, which currently involves a trade-off between computational overhead and approximation precision. Additionally, while the current proofs rely on Gaussian projections, extending these results to broader classes of log-concave distributions remains an open area for investigation. Finally, reducing the hidden constants in the $O(d)$ bound would further enhance the method's applicability to extremely high-dimensional problems.

Summary updated

Abstract

Singular covariance matrices are frequently encountered in both machine learning and optimization problems, most commonly due to high dimensionality of data and insufficient sample sizes. Among many methods of regularization, here we focus on a relatively recent random matrix-theoretic approach, the idea of which is to create well-conditioned approximations of a singular covariance matrix and its inverse by taking the expectation of its random projections. We are interested in the error of a Monte Carlo implementation of this approach, which allows subsequent parallel processing in low dimensions in practice. We find that [Formula: see text] random projections, where [Formula: see text] is the size of the original matrix, are sufficient for the Monte Carlo error to become negligible, in the sense of expected spectral norm difference, for both covariance and inverse covariance approximation, in the latter case under mild assumptions.
BibTeX
@inproceedings{kaban2020sufficient,
  author = {Ata Kabán},
  title = {{Sufficient ensemble size for random matrix theory-based handling of singular covariance matrices}},
  booktitle = {Analysis},
  year = {2020},
  doi = {10.1142/s0219530520400072},
}
Figure