We present two computationally inexpensive techniques for estimating the numerical rank of a matrix, combining powerful tools from computational linear algebra. These techniques exploit three key ingredients. The first is to approximate the projector on the non-null invariant subspace of the matrix by using a polynomial filter. Two types of filters are discussed, one based on Hcrmite interpolation and the other based on Chebyshev expansions. The second ingredient employs stochastic trace estimators to compute the rank of this wanted eigen-projector, which yields the desired rank of the matrix. In order to obtain a good filter, it is necessary to detect a gap between the eigenvalues that correspond to noise and the relevant eigenvalues that correspond to the non-null invariant subspace. The third ingredient of the proposed approaches exploits the idea of spectral density, popular in physics, and the Lanczos spectroscopic method to locate this gap.
|Original language||English (US)|
|Title of host publication||33rd International Conference on Machine Learning, ICML 2016|
|Editors||Maria Florina Balcan, Kilian Q. Weinberger|
|Publisher||International Machine Learning Society (IMLS)|
|Number of pages||15|
|State||Published - 2016|
|Event||33rd International Conference on Machine Learning, ICML 2016 - New York City, United States|
Duration: Jun 19 2016 → Jun 24 2016
|Name||33rd International Conference on Machine Learning, ICML 2016|
|Other||33rd International Conference on Machine Learning, ICML 2016|
|City||New York City|
|Period||6/19/16 → 6/24/16|
Copyright 2017 Elsevier B.V., All rights reserved.