Efficient Spectrum-Revealing CUR Matrix Decomposition

Cheng Chen, Ming Gu, Zhihua Zhang, Weinan Zhang, Yong Yu
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:766-775, 2020.

Abstract

The CUR matrix decomposition is an important tool for low-rank matrix approximation. It approximates a data matrix though selecting a small number of columns and rows of the matrix. Those CUR algorithms with gap-dependent approximation bounds can obtain high approximation quality for matrices with good singular value spectrum decay, but they have impractically high time complexities. In this paper, we propose a novel CUR algorithm based on truncated LU factorization with an efficient variant of complete pivoting. Our algorithm has gap-dependent approximation bounds on both spectral and Frobenius norms while maintaining high efficiency. Numerical experiments demonstrate the effectiveness of our algorithm and verify our theoretical guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-chen20a, title = {Efficient Spectrum-Revealing CUR Matrix Decomposition}, author = {Chen, Cheng and Gu, Ming and Zhang, Zhihua and Zhang, Weinan and Yu, Yong}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {766--775}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/chen20a/chen20a.pdf}, url = {https://proceedings.mlr.press/v108/chen20a.html}, abstract = {The CUR matrix decomposition is an important tool for low-rank matrix approximation. It approximates a data matrix though selecting a small number of columns and rows of the matrix. Those CUR algorithms with gap-dependent approximation bounds can obtain high approximation quality for matrices with good singular value spectrum decay, but they have impractically high time complexities. In this paper, we propose a novel CUR algorithm based on truncated LU factorization with an efficient variant of complete pivoting. Our algorithm has gap-dependent approximation bounds on both spectral and Frobenius norms while maintaining high efficiency. Numerical experiments demonstrate the effectiveness of our algorithm and verify our theoretical guarantees.} }
Endnote
%0 Conference Paper %T Efficient Spectrum-Revealing CUR Matrix Decomposition %A Cheng Chen %A Ming Gu %A Zhihua Zhang %A Weinan Zhang %A Yong Yu %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-chen20a %I PMLR %P 766--775 %U https://proceedings.mlr.press/v108/chen20a.html %V 108 %X The CUR matrix decomposition is an important tool for low-rank matrix approximation. It approximates a data matrix though selecting a small number of columns and rows of the matrix. Those CUR algorithms with gap-dependent approximation bounds can obtain high approximation quality for matrices with good singular value spectrum decay, but they have impractically high time complexities. In this paper, we propose a novel CUR algorithm based on truncated LU factorization with an efficient variant of complete pivoting. Our algorithm has gap-dependent approximation bounds on both spectral and Frobenius norms while maintaining high efficiency. Numerical experiments demonstrate the effectiveness of our algorithm and verify our theoretical guarantees.
APA
Chen, C., Gu, M., Zhang, Z., Zhang, W. & Yu, Y.. (2020). Efficient Spectrum-Revealing CUR Matrix Decomposition. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:766-775 Available from https://proceedings.mlr.press/v108/chen20a.html.

Related Material