Fast methods for estimating the Numerical rank of large matrices

Shashanka Ubaru, Yousef Saad
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:468-477, 2016.

Abstract

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 Hermite 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-ubaru16, title = {Fast methods for estimating the Numerical rank of large matrices}, author = {Ubaru, Shashanka and Saad, Yousef}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {468--477}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/ubaru16.pdf}, url = {https://proceedings.mlr.press/v48/ubaru16.html}, abstract = {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 Hermite 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.} }
Endnote
%0 Conference Paper %T Fast methods for estimating the Numerical rank of large matrices %A Shashanka Ubaru %A Yousef Saad %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-ubaru16 %I PMLR %P 468--477 %U https://proceedings.mlr.press/v48/ubaru16.html %V 48 %X 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 Hermite 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.
RIS
TY - CPAPER TI - Fast methods for estimating the Numerical rank of large matrices AU - Shashanka Ubaru AU - Yousef Saad BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-ubaru16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 468 EP - 477 L1 - http://proceedings.mlr.press/v48/ubaru16.pdf UR - https://proceedings.mlr.press/v48/ubaru16.html AB - 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 Hermite 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. ER -
APA
Ubaru, S. & Saad, Y.. (2016). Fast methods for estimating the Numerical rank of large matrices. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:468-477 Available from https://proceedings.mlr.press/v48/ubaru16.html.

Related Material