×

A DEIM induced CUR factorization. (English) Zbl 1382.65121

Summary: We derive a CUR approximate matrix factorization based on the discrete empirical interpolation method (DEIM). For a given matrix \({\mathbf A}\), such a factorization provides a low-rank approximate decomposition of the form \({\mathbf A} \approx \mathbf {CUR}\), where \({\mathbf C}\) and \({\mathbf R}\) are subsets of the columns and rows of \({\mathbf A}\), and \({\mathbf U}\) is constructed to make \(\mathbf {CUR} \) a good approximation. Given a low-rank singular value decomposition \({\mathbf A} \approx \mathbf {VSW}^{\mathbf T}\), the DEIM procedure uses \({\mathbf V}\) and \({\mathbf W}\) to select the columns and rows of \({\mathbf A}\) that form \({\mathbf C}\) and \({\mathbf R}\). Through an error analysis applicable to a general class of CUR factorizations, we show that the accuracy tracks the optimal approximation error within a factor that depends on the conditioning of submatrices of \({\mathbf V}\) and \({\mathbf W}\). For very large problems, \({\mathbf V}\) and \({\mathbf W}\) can be approximated well using an incremental QR algorithm that makes only one pass through \({\mathbf A}\). Numerical examples illustrate the favorable performance of the DEIM-CUR method compared to CUR approximations based on leverage scores.

MSC:

65F30 Other matrix algorithms (MSC2010)
15A23 Factorization of matrices
47A58 Linear operator approximation theory
65F35 Numerical computation of matrix norms, conditioning, scaling
68W25 Approximation algorithms

Software:

ARPACK; PROPACK
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Baglama and L. Reichel, {\it An implicitly restarted block Lanczos bidiagonalization method using Leja shifts}, BIT, 53 (2013), pp. 285-310. · Zbl 1269.65038
[2] C. G. Baker, {\it A Block Incremental Algorithm for Computing Dominant Singular Subspaces}, Master’s thesis, Florida State University, Tallahassee, FL, 2004.
[3] C. G. Baker, K. A. Gallivan, and P. Van Dooren, {\it Low-rank incremental methods for computing dominant singular subspaces}, Linear Algebra Appl., 436 (2012), pp. 2866-2888. · Zbl 1241.65036
[4] M. Barrault, Y. Maday, N. C. Nguyen, and A. T. Patera, {\it An “empirical interpolation” method: Application to efficient reduced-basis discretization of partial differential equations}, C. R. Math. Acad. Sci. Paris, 339 (2004), pp. 667-672. · Zbl 1061.65118
[5] C. Boutsidis and D. P. Woodruff, {\it Optimal CUR matrix decompositions}, in Proceedings of the 2014 ACM Symposium on Theory of Computing, ACM, New York, 2014, pp. 353-362. · Zbl 1315.65042
[6] S. Chaturantabut and D. C. Sorensen, {\it Nonlinear model reduction via discrete empirical interpolation}, SIAM J. Sci. Comput., 32 (2010), pp. 2737-2764, http://dx.doi.org/10.1137/090766498. · Zbl 1217.65169
[7] H. Cheng, Z. Gimbutas, P. G. Martinsson, and V. Rokhlin, {\it On the compression of low rank matrices}, SIAM J. Sci. Comput., 26 (2005), pp. 1389-1404, http://dx.doi.org/10.1137/030602678. · Zbl 1083.65042
[8] J. W. Daniel, W. B. Gragg, L. Kaufman, and G. W. Stewart, {\it Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization}, Math. Comp., 30 (1976), pp. 772-795. · Zbl 0345.65021
[9] J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst, {\it Numerical Linear Algebra for High-Performance Computers}, Software Environ. Tools 7, SIAM, Philadelphia, 1998. · Zbl 0914.65014
[10] P. Drineas, M. W. Mahoney, and S. Muthukrishnan, {\it Relative-error {\it CUR} matrix decompositions}, SIAM J. Matrix Anal. Appl., 30 (2008), pp. 844-881, http://dx.doi.org/10.1137/07070471X. · Zbl 1183.68738
[11] Z. Drmač and S. Gugercin, {\it A new selection operator for the discrete empirical interpolation method–Improved a priori error bound and extensions}, SIAM J. Sci. Comput. 38 (2016), pp. A631-A648, http://dx.doi.org/10.1137/15M1019271. · Zbl 1382.65193
[12] E. Gabrilovich and S. Markovitch, {\it Text categorization with many redundant features: Using aggressive feature selection to make SVMs competitive with} C4.5, in The 21st International Conference on Machine Learning (ICML), ACM, New York, 2004, pp. 321-328.
[13] L. Giraud, J. Langou, M. Rozložník, and J. van den Eshof, {\it Rounding error analysis of the classical Gram-Schmidt orthogonalization process}, Numer. Math., 101 (2005), pp. 87-100. · Zbl 1075.65060
[14] S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, {\it A theory of pseudoskeleton approximations}, Linear Algebra Appl., 261 (1997), pp. 1-21. · Zbl 0877.65021
[15] M. Gu and S. C. Eisenstat, {\it Efficient algorithms for computing a strong rank-revealing QR factorization}, SIAM J. Sci. Comput., 17 (1996), pp. 848-869, http://dx.doi.org/10.1137/0917055. · Zbl 0858.65044
[16] N. Halko, P. G. Matinsson, and J. A. Tropp, {\it Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions}, SIAM Rev., 53 (2011), pp. 217-288, http://dx.doi.org/10.1137/090771806. · Zbl 1269.65043
[17] M. E. Hochstenbach, {\it A Jacobi-Davidson type SVD method}, SIAM J. Sci. Comput., 23 (2001), pp. 606-628, http://dx.doi.org/10.1137/S1064827500372973. · Zbl 1002.65048
[18] I. C. F. Ipsen and T. Wentworth, {\it Sensitivity of Leverage Scores}, preprint arXiv:1402.0957 [math.NA], 2014.
[19] A. Kundu, S. Nambirajan, and P. Drineas, {\it Identifying influential entries in a matrix}, preprint arXiv:1310.3556 [cs.nA], 2013.
[20] R. M. Larsen, {\it PROPACK: Software for Large and Sparse SVD Calculations}, Version 2.1, http://sun.stanford.edu/ rmunk/PROPACK/, 2005.
[21] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK Users’ Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[22] M. W. Mahoney and P. Drineas, {\it CUR matrix decompositions for improved data analysis}, Proc. Natl. Acad. Sci. USA, 106 (2009), pp. 697-702. · Zbl 1202.68480
[23] G. W. Stewart, {\it Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix}, Numer. Math., 83 (1999), pp. 313-323. · Zbl 0957.65031
[24] D. B. Szyld, {\it The many proofs of an identity on the norm of oblique projections}, Numer. Algorithms, 42 (2006), pp. 309-323. · Zbl 1102.47002
[25] C. Thurau, K. Kersting, and C. Bauckhage, {\it Deterministic CUR for improved large-scale data analysis: An empirical study}, in Proceedings of the 2012 SIAM International Conference on Data Mining, SIAM, Philadelphia, 2012, pp. 684-695.
[26] L. N. Trefethen and D. Bau, III, {\it Numerical Linear Algebra}, SIAM, Philadelphia, 1997. · Zbl 0874.65013
[27] L. N. Trefethen and R. S. Schreiber, {\it Average-case stability of Gaussian elimination}, SIAM J. Matrix Anal. Appl., 11 (1990), pp. 335-360, http://dx.doi.org/10.1137/0611023. · Zbl 0703.65015
[28] S. Wang and Z. Zhang, {\it Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling}, J. Mach. Learn. Res., 14 (2013), pp. 2729-2769. · Zbl 1318.65023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.