Fast estimation of approximate matrix ranks using spectral densities

Abstract

In many machine learning and data related applications, it is required to have the knowledge of approximate ranks of large data matrices at hand. In this paper, we present two computationally inexpensive techniques to estimate the approximate ranks of such large matrices. These techniques exploit approximate spectral densities, popular in physics, which are probability density distributions that measure the likelihood of finding eigenvalues of the matrix at a given point on the real line. Integrating the spectral density over an interval gives the eigenvalue count of the matrix in that interval. Therefore the rank can be approximated by integrating the spectral density over a carefully selected interval. Two different approaches are discussed to estimate the approximate rank, one based on Chebyshev polynomials and the other based on the Lanczos algorithm. In order to obtain the appropriate interval, it is necessary to locate a gap between the eigenvalues that correspond to noise and the relevant eigenvalues that contribute to the matrix rank. A method for locating this gap and selecting the interval of integration is proposed based on the plot of the spectral density. Numerical experiments illustrate the performance of these techniques on matrices from typical applications.

References in corpus (9)

• The Kernel Polynomial Method
• Optimal selection of reduced rank estimators of high-dimensional matrices
• Bi-cross-validation of the SVD and the nonnegative matrix factorization
• A Novel M-Estimator for Robust PCA
• Improved bounds on sample size for implicit matrix trace estimators
• Minimax rank estimation for subspace tracking
• Efficient estimation of eigenvalue counts in an interval
• Principal Component Projection Without Principal Component Analysis
• Optimal Estimation and Rank Detection for Sparse Spiked Covariance Matrices

Cited by in corpus (7)

• Towards quantum advantage via topological data analysis
• Quantum utility -- definition and assessment of a practical quantum advantage
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Analysis of stochastic Lanczos quadrature for spectrum approximation
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Low rank approximation and decomposition of large matrices using error correcting codes
• Spectrum-Adapted Polynomial Approximation for Matrix Functions