Fast Estimation of Approximate Matrix Ranks Using Spectral Densities

DOI10.1162/NECO_A_00951zbMATH Open1474.68318DBLPjournals/neco/UbaruSS17aarXiv1608.05754WikidataQ38883489 ScholiaQ38883489MaRDI QIDQ5380703FDOQ5380703

Authors: Shashanka Ubaru, Y. Saad, Abd-Krim Seghouane 

Publication date: 6 June 2019

Published in: Neural Computation (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1608.05754

Recommendations

• Randomized estimation of spectral densities of large matrices made accurate
• Approximating spectral densities of large matrices
• Estimating the Rank of the Spectral Density Matrix
• Fast gradient method for low-rank matrix estimation
• Estimation of high-dimensional low-rank matrices
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Rank Detection Methods for Sparse Matrices
• scientific article; zbMATH DE number 7008333
• Fast computation of low rank matrix approximations
• A fast and efficient algorithm for low-rank approximation of a matrix

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computational aspects of data analysis and big data (68T09) Numerical linear algebra (65F99)

Cites Work

• The University of Florida sparse matrix collection
• Bi-cross-validation of the SVD and the nonnegative matrix factorization
• Principal component analysis.
• Rang revealing QR factorizations
• Gaussian processes for machine learning.
• Title not available (Why is that?)
• Robust principal component analysis?
• Title not available (Why is that?)
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Multivariate reduced-rank regression
• Optimal selection of reduced rank estimators of high-dimensional matrices
• A novel M-estimator for robust PCA
• Numerical methods for large eigenvalue problems
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation
• Approximation theory and approximation practice
• Rank estimation in missing data matrix problems
• Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix
• On the Asymptotic Properties of LDU-Based Tests of the Rank of a Matrix
• TESTS OF RANK
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Matrices, moments and quadrature with applications
• Improved bounds on sample size for implicit matrix trace estimators
• Statistical Tests and Estimators of the Rank of a Matrix and Their Applications in Econometric Modelling
• Title not available (Why is that?)
• Rank estimation in reduced-rank regression
• Title not available (Why is that?)
• Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• The kernel polynomial method
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized low rank approximations of matrices
• Non-Parametric Detection of the Number of Signals: Hypothesis Testing and Random Matrix Theory
• Fast and Stable Subspace Tracking
• Optimal estimation and rank detection for sparse spiked covariance matrices
• Relations among some low-rank subspace recovery models
• Approximating spectral densities of large matrices
• Electronic structure calculations for plane-wave codes without diagonalization
• Dimension Selection for Feature Selection and Dimension Reduction with Principal and Independent Component Analysis
• Low-rank approximation. Algorithms, implementation, applications
• Least squares data fitting with applications
• Efficient estimation of eigenvalue counts in an interval.
• Active subspace: toward scalable low-rank learning
• Filtered Conjugate Residual‐type Algorithms with Applications
• Approximation of step functions in problems of mathematical modeling

Cited In (4)

• Fast randomized numerical rank estimation for numerically low-rank matrices
• Title not available (Why is that?)
• Approximating spectral densities of large matrices
• Fast estimation of \(\mathrm{tr}(f(A))\) via stochastic Lanczos quadrature

Uses Software

• SparseMatrix

This page was built for publication: Fast Estimation of Approximate Matrix Ranks Using Spectral Densities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5380703)