Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Randomized GCUR decompositions

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

By exploiting the random sampling techniques, this paper derives an efficient randomized algorithm for computing a generalized CUR decomposition, which provides low-rank approximations of both matrices simultaneously in terms of some of their rows and columns. For large-scale data sets that are expensive to store and manipulate, a new variant of the discrete empirical interpolation method known as L-DEIM, which needs much lower cost and provides a significant acceleration in practice, is also combined with the random sampling approach to further improve the efficiency of our algorithm. Moreover, adopting the randomized algorithm to implement the truncation process of restricted singular value decomposition (RSVD), combined with the L-DEIM procedure, we propose a fast algorithm for computing an RSVD based CUR decomposition, which provides a coordinated low-rank approximation of the three matrices in a CUR-type format simultaneously and provides advantages over the standard CUR approximation for some applications. We establish detailed probabilistic error analysis for the algorithms and provide numerical results that show the promise of our approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data Availability

All datasets are publicly available.

References

  1. Abid, A., Zhang, M.J., Bagaria, V.K., Zou, J.: Exploring patterns enriched in a dataset with contrastive principal component analysis, Nature. Communications 9, 1–7 (2018)

    Google Scholar 

  2. Bai, Z., Demmel, J.W.: Computing the generalized singular value decomposition. SIAM J. Sci. Comput. 14, 1464–1486 (1993)

    Article  MathSciNet  Google Scholar 

  3. Banfield, R.E., Hall, L.O., Bowyer, K.W., Kegelmeyer, W.P.: A comparison of decision tree ensemble creation techniques. IEEE Trans. Pattern Anal. Mach. Intell. 29, 173–180 (2006)

    Article  Google Scholar 

  4. Barrault, M., Maday, Y., Nguyen, N.C., Patera, A.T.: An ‘empirical interpolation’ method: application to efficient reduced-basis discretization of partial differential equations. Comptes Rendus Mathematique 339, 667–672 (2004)

    Article  MathSciNet  Google Scholar 

  5. Boileau, P., Hejazi, N.S., Dudoit, S.: Exploring high-dimensional biological data with sparse contrastive principal component analysis. Bioinformatics 36, 3422–3430 (2020)

    Article  Google Scholar 

  6. Boutsidis, C., Drineas, P.: Random projections for the nonnegative least-squares problem. Linear Algebra Appl. 431, 760–771 (2009)

    Article  MathSciNet  Google Scholar 

  7. Boutsidis, C., Woodruff, D.P.: Optimal CUR matrix decompositions. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 353–362 (2014)

  8. Cai, H., Hamm, K., Huang, L., Li, J., Wang, T.: Rapid robust principal component analysis: CUR accelerated inexact low rank estimation. IEEE Signal Process. Lett. 28, 116–120 (2020)

    Article  Google Scholar 

  9. Cai, H., Hamm, K., Huang, L., Needell, D.: Robust CUR decomposition: Theory and imaging applications. SIAM J. Imaging Sci. 14, 1472–1503 (2021)

    Article  MathSciNet  Google Scholar 

  10. Cai, H., Huang, L., Li, P., Needell, D.: Matrix completion with cross-concentrated sampling: Bridging uniform sampling and CUR sampling. IEEE Trans. Pattern Anal. Mach. Intell. 45, 10100–10113 (2023)

    Article  Google Scholar 

  11. Chaturantabut, S., Sorensen, D.C.: Nonlinear model reduction via discrete empirical interpolation. SIAM J. Sci. Comput. 32, 2737–2764 (2010)

    Article  MathSciNet  Google Scholar 

  12. Chen, J., Wang, G., Giannakis, G.B.: Nonlinear dimensionality reduction for discriminative analytics of multiple datasets. IEEE Trans. Signal Process. 67, 740–752 (2018)

    Article  MathSciNet  Google Scholar 

  13. Chu, D., De Lathauwer, L., De Moor, B.: On the computation of the restricted singular value decomposition via the cosine-sine decomposition. SIAM J. Matrix Anal. Appl. 22, 580–601 (2000)

    Article  MathSciNet  Google Scholar 

  14. De Moor, B.L., Golub, G.H.: The restricted singular value decomposition: properties and applications. SIAM J. Matrix Anal. Appl. 12, 401–425 (1991)

    Article  MathSciNet  Google Scholar 

  15. Drineas, P., Mahoney, M.W., Muthukrishnan, S.: Relative-error CUR matrix decompositions. SIAM J. Matrix Anal. Appl. 30, 844–881 (2008)

    Article  MathSciNet  Google Scholar 

  16. Drmač, Z., Saibaba, A.K.: The discrete empirical interpolation method: Canonical structure and formulation in weighted inner product spaces. SIAM J. Matrix Anal. Appl. 39, 1152–1180 (2018)

    Article  MathSciNet  Google Scholar 

  17. Gidisu, P.Y., Hochstenbach, M.E.: A generalized CUR decomposition for matrix pairs. SIAM J. Math. Data Sci. 4, 386–409 (2022)

    Article  MathSciNet  Google Scholar 

  18. Gidisu, P.Y., Hochstenbach, M.E.: A hybrid DEIM and leverage scores based method for CUR index selection. Progress in Industrial Mathematics at ECMI 2022, 147–153 (2021)

    Google Scholar 

  19. Gidisu, P.Y., Hochstenbach, M.E.: A restricted svd type CUR decomposition for matrix triplets. SIAM J. Sci. Comput., S401–S423, (2022)

  20. Goreinov, S.A., Tyrtyshnikov, E.E.: The maximal-volume concept in approximation by low-rank matrices. Contemp. Math. 280, 47–52 (2001)

    Article  MathSciNet  Google Scholar 

  21. Goreinov, S.A., Tyrtyshnikov, E.E., Zamarashkin, N.L.: A theory of pseudoskeleton approximations. Linear Algebra Appl. 261, 1–21 (1997)

    Article  MathSciNet  Google Scholar 

  22. Halko, N., Martinsson, P.-G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 217–288 (2011)

    Article  MathSciNet  Google Scholar 

  23. Hamm, K., Huang, L.: Perturbations of CUR decompositions. SIAM J. Matrix Anal. Appl. 42, 351–375 (2021)

    Article  MathSciNet  Google Scholar 

  24. Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems. Society for Industrial and Applied Mathematics, Philadelphia, PA (1998)

    Book  Google Scholar 

  25. Hendryx, E.P., Rivière, B.M., Rusin, C.G.: An extended DEIM algorithm for subset selection and class identification. Mach. Learn. 110, 621–650 (2021)

    Article  MathSciNet  Google Scholar 

  26. Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1991)

    Book  Google Scholar 

  27. Huang, J., Jia, Z.: Two harmonic Jacobi-Davidson methods for computing a partial generalized singular value decomposition of a large matrix pair. J. Sci. Comput. 93, 41 (2022)

    Article  MathSciNet  Google Scholar 

  28. James, G., Witten, D., Hastie, T., Tibshirani, R.: An introduction to statistical learning, vol. 112, Springer, (2013)

  29. Jolliffe, I.T.: Discarding variables in a principal component analysi i: Artificial data. J. R. Stat. Soc., C: Appl. Stat. 21, 160–173 (1972)

    MathSciNet  Google Scholar 

  30. Li, R.-C.: Bounds on perturbations of generalized singular values and of associated subspaces. SIAM J. Matrix Anal. Appl. 14, 195–234 (1993)

    Article  MathSciNet  Google Scholar 

  31. Mahoney, M.W., Drineas, P.: CUR matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. 106, 697–702 (2009)

    Article  MathSciNet  Google Scholar 

  32. Paige, C.C., Saunders, M.A.: Towards a generalized singular value decomposition. SIAM J. Numer. Anal. 18, 398–405 (1981)

    Article  MathSciNet  Google Scholar 

  33. Papailiopoulos, D., Kyrillidis, A., Boutsidis, C.: Provable deterministic leverage score sampling. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 997–1006 (2014)

  34. Peherstorfer, B., Drmač, Z., Gugercin, S.: Stability of discrete empirical interpolation and gappy proper orthogonal decomposition with randomized and deterministic sampling points. SIAM J. Sci. Comput. 42, A2837–A2864 (2020)

    Article  MathSciNet  Google Scholar 

  35. Rachkovskij, D., Revunova, E.: A randomized method for solving discrete ill-posed problems. Cybern. Syst. Anal. 48, 621–635 (2012)

    Article  MathSciNet  Google Scholar 

  36. Saibaba, A.K.: Randomized discrete empirical interpolation method for nonlinear model reduction. SIAM J. Sci. Comput. 42, A1582–A1608 (2020)

    Article  MathSciNet  Google Scholar 

  37. Saibaba, A.K., Hart, J., van Bloemen Waanders, B.: Randomized algorithms for generalized singular value decomposition with application to sensitivity analysis. Numer. Linear Algebra Appl. 28, e2364 (2021)

    Article  MathSciNet  Google Scholar 

  38. Saibaba, A.K., Lee, J., Kitanidis, P.K.: Randomized algorithms for generalized hermitian eigenvalue problems with application to computing Karhunen-Loève expansion. Numer. Linear Algebra Appl. 23, 314–339 (2016)

    Article  MathSciNet  Google Scholar 

  39. Sorensen, D.C., Embree, M.: A DEIM induced CUR factorization. SIAM J. Sci. Comput. 38, A1454–A1482 (2016)

    Article  MathSciNet  Google Scholar 

  40. Stewart, G.: Computing the CS decomposition of a partitioned orthonormal matrix. Numerische Mathematik 40, 297–306 (1982)

    Article  MathSciNet  Google Scholar 

  41. Stewart, G.W.: Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix. Numerische Mathematik 83, 313–323 (1999)

    Article  MathSciNet  Google Scholar 

  42. Sun, J.-G.: On the perturbation of generalized singular values. Math. Numer. Sinica 4, 229–233 (1982)

    MathSciNet  Google Scholar 

  43. Sun, J.-G.: Perturbation analysis for the generalized singular value problem. SIAM J. Numer. Anal. 20, 611–625 (1983)

    Article  MathSciNet  Google Scholar 

  44. Szyld, D.B.: The many proofs of an identity on the norm of oblique projections. Numer. Algorithms 42, 309–323 (2006)

    Article  MathSciNet  Google Scholar 

  45. Van Loan, C.F.: Generalizing the singular value decomposition. SIAM J. Numer. Anal. 13, 76–83 (1976)

    Article  MathSciNet  Google Scholar 

  46. Van Loan, C.F.: Computing the CS and the generalized singular value decompositions. Numerische Mathematik 46, 479–491 (1985)

    Article  MathSciNet  Google Scholar 

  47. Voronin, S., Martinsson, P.-G.: Efficient algorithms for cur and interpolative matrix decompositions. Adv. Comput. Math. 43, 495–516 (2017)

  48. Wang, S., Zhang, Z.: Improving CUR matrix decomposition and the Nyström approximation via adaptive sampling, The. J. Mach. Learn. Res. 14, 2729–2769 (2013)

    MathSciNet  Google Scholar 

  49. Wei, W., Zhang, H., Yang, X., Chen, X.: Randomized generalized singular value decomposition, Communications on. Appl. Math. Comput. 3, 137–156 (2021)

    MathSciNet  Google Scholar 

  50. Wei, Y., Stanimirović, P., Petković, M.: Numerical and Symbolic Computations of Generalized Inverses. Hackensack, World Scientific, NJ (2018)

    Book  Google Scholar 

  51. Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37, 649–675 (2016)

    Article  MathSciNet  Google Scholar 

  52. Xiang, H., Zou, J.: Regularization with randomized SVD for large-scale discrete inverse problems. Inverse Probl. 29, 085008 (2013)

    Article  MathSciNet  Google Scholar 

  53. Xie, P., Xiang, H., Wei, Y.: Randomized algorithms for total least squares problems. Numer. Linear Algebra Appl. 26, e2219 (2019)

    Article  MathSciNet  Google Scholar 

  54. Xu, C., Tao, D., Xu, C.: A survey on multi-view learning, arXiv:1304.5634, (2013)

  55. Zha, H.: The restricted singular value decomposition of matrix triplets. SIAM J. Matrix Anal. Appl. 12, 172–194 (1991)

    Article  MathSciNet  Google Scholar 

  56. Zha, H.: Computing the generalized singular values/vectors of large sparse or structured matrix pairs. Numerische Mathematik 72, 391–417 (1996)

    Article  MathSciNet  Google Scholar 

  57. Zhang, L., Wei, Y.: Randomized core reduction for discrete ill-posed problem. J. Comput. Appl. Math. 375, 112797 (2020)

    Article  MathSciNet  Google Scholar 

  58. Zhang, L., Wei, Y., Chu, E.K.-W.: Neural network for computing GSVD and RSVD. Neurocomputing 444, 59–66 (2021)

    Article  Google Scholar 

  59. Zwaan, I.N.: Towards a more robust algorithm for computing the restricted singular value decomposition, arXiv:2002.04828, (2020)

Download references

Acknowledgements

The authors would like to thank the handling editor and two anonymous reviewers for their very insightful and constructive comments which helped greatly in improving the manuscript. Z. Cao is supported by the National Natural Science Foundation of China under Grant 11801534. Y. Wei is supported by the National Natural Science Foundation of China under Grant 12271108 and Ministry of Science and Technology of China under grant G2023132005L. P. Xie is supported by the National Natural Science Foundation of China under Grants 12271108, 11801534, Fundamental Research Funds for the Central Universities (No. 202264006), Laoshan Laboratory (LSKJ202202302) and Qingdao Natural Science Foundation 23-2-1-158-zyyd-jch..

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Ocean University of China, 266100, Qingdao, China

    Zhengbang Cao & Pengpeng Xie

  2. School of Mathematical Sciences and and Key Laboratory of Mathematics for Nonlinear Sciences, Fudan University, 200433, Shanghai, China

    Yimin Wei

Authors
  1. Zhengbang Cao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yimin Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pengpeng Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pengpeng Xie.

Ethics declarations

Conflicts of interest

The authors have no conflicts of interest to declare.

Additional information

Communicated by: Peter Benner

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cao, Z., Wei, Y. & Xie, P. Randomized GCUR decompositions. Adv Comput Math 50, 77 (2024). https://doi.org/10.1007/s10444-024-10168-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10444-024-10168-x

Keywords

Mathematics Subject Classification (2010)

Search

Navigation