Abstract
A technique that has recently become popular in data analysis and machine learning is the CUR decomposition of a large matrix. Existing approaches for CUR decomposition are usually slow, so that they are not applicable to large real-world matrices. In this paper, we propose a method to efficiently compute a CUR decomposition of a matrix. In our method, we use the fast CUR method as a basis and improve its runtime by estimating approximate Frobenius norms, rather than computing their exact values. We compare our method against several state of the art algorithms for CUR decomposition and show that it outperforms the other methods, in terms of running time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Availability of data and materials
The used data are publicly available and their links are provided in Sect. 4.2.
Notes
References
Worldometers 09 June 2020. Countries in the world by population, 2020
Akoglu L, Tong H, Koutra D (2015) Graph-based anomaly detection and description: a survey. Data Min Knowl Discov 29:626–688
Boutsidis C, Woodruff David P (2017) Optimal CUR matrix decompositions. SIAM J Comput 46(2):543–589
Cai H, Hamm K, Huang L, Li J, Wang T (2021) Rapid robust principal component analysis: CUR accelerated inexact low rank estimation. IEEE Signal Process Lett 28:116–120
Cai H, Hamm K, Huang L, Needell D (2021) Robust CUR decomposition: theory and imaging applications. SIAM J Imag Sci 14(4):1472–1503
Candès E, Recht B (2012) Exact matrix completion via convex optimization. Commun ACM 55(6):111–119
Chiu J, Demanet L (2013) Sublinear randomized algorithms for skeleton decompositions. SIAM J Matrix Anal Appl 34(3):1361–1383
Drineas P, Kannan R, Mahoney MW (2006) Fast Monte Carlo algorithms for matrices III: computing a compressed approximate matrix decomposition. SIAM J Comput 36(1):184–206
Dua D, Graff C (2017) UCI machine learning repository
Goreinov SA, Tyrtyshnikov EE, Zamarashkin NL (1997) A theory of pseudoskeleton approximations. Linear Algebr Appl 261(1):1–21
Guennebaud G, Jacob B et al (2020) Eigen v 3.3.9. http://eigen.tuxfamily.org,
Hamm Keaton, Huang Longxiu (2020) Perspectives on CUR decompositions. Appl Comput Harmonic Anal 48(3):1088–1099
Hamm K, Huang L (2020) Stability of sampling for CUR decompositions. Found Data Sci 2(2):83–99
Keshavan RH, Montanari A, Sewoong Oh (2010) Matrix completion from a few entries. IEEE Trans Inf Theor 56(6):2980–2998
Khetan A, Oh S (2017) Matrix norm estimation from a few entries. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6424–6433
Klema V, Laub A (1980) The singular value decomposition: its computation and some applications. IEEE Trans Autom Control 25(2):164–176
Li Yi, Woodruff David P(2020) Input-sparsity low rank approximation in schatten norm. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pages 6001–6009
Li Yi, Woodruff David P (2022) Tight bounds for sketching the operator norm, schatten norms, and subspace embeddings. CoRR, abs/2202.09797
Mahoney Michael W, Drineas Petros (2009) CUR matrix decompositions for improved data analysis. Proc Nat Acad Sci 106(3):697–702
Mitrovic N, Asif Muhammad T, Rasheed U, Dauwels J, Jaillet P (2013) CUR decomposition for compression and compressed sensing of large-scale traffic data. In 16th International IEEE Conference on Intelligent Transportation Systems, ITSC 2013, The Hague, The Netherlands, October 6-9, 2013, pages 1475–1480. IEEE
Song Z, Woodruff David P, Zhong P (2017) Low rank approximation with entrywise l\({}_{\text{1}}\)-norm error. In STOC, pages 688–701. ACM
Song Z, Woodruff DP, Zhong P (2019) Relative error tensor low rank approximation. In SODA, pages 2772–2789. SIAM
Sun J, Xie Y, Zhang H, Faloutsos C (2008) Less is more: sparse graph mining with compact matrix decomposition. Stat Anal Data Min 1(1):6–22
Voronin S, Martinsson PG (2017) Efficient algorithms for CUR and interpolative matrix decompositions. Adv Comput Math 43(3):495–516
Wang S, Zhang Z (2013) Improving CUR matrix decomposition and the nyström approximation via adaptive sampling. J Mach Learn Res 14(1):2729–2769
Williams Christopher KI, Seeger M (2001) Using the nyström method to speed up kernel machines. In T.K. Leen, T.G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13 (NIPS 2000), pages 682–688. MIT Press
Funding
Not applicable.
Author information
Authors and Affiliations
Contributions
MHC: developed ideas, analyzed results, wrote paper, supervised work. ZY: implemented algorithms, ran experiments.
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no competing interests as defined by Springer, or other interests that might be perceived to influence the results and/or discussion reported in this paper.
Ethical approval
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Haghir Chehreghani, M., Yaghoobi, Z. Improving empirical efficiency of CUR decomposition. J Supercomput 79, 9350–9366 (2023). https://doi.org/10.1007/s11227-022-05039-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11227-022-05039-5