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

Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions

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

Abstract

Matrix skeletonizations like the interpolative and CUR decompositions provide a framework for low-rank approximation in which subsets of a given matrix’s columns and/or rows are selected to form approximate spanning sets for its column and/or row space. Such decompositions that rely on “natural” bases have several advantages over traditional low-rank decompositions with orthonormal bases, including preserving properties like sparsity or non-negativity, maintaining semantic information in data, and reducing storage requirements. Matrix skeletonizations can be computed using classical deterministic algorithms such as column-pivoted QR, which work well for small-scale problems in practice, but suffer from slow execution as the dimension increases and can be vulnerable to adversarial inputs. More recently, randomized pivoting schemes have attracted much attention, as they have proven capable of accelerating practical speed, scale well with dimensionality, and sometimes also lead to better theoretical guarantees. This manuscript provides a comparative study of various randomized pivoting-based matrix skeletonization algorithms that leverage classical pivoting schemes as building blocks. We propose a general framework that encapsulates the common structure of these randomized pivoting-based algorithms and provides an a-posteriori-estimable error bound for the framework. Additionally, we propose a novel concretization of the general framework and numerically demonstrate its superior empirical efficiency.

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

References

  1. Goreinov, S.A., Tyrtyshnikov, E.E., Zamarashkin, N.L.: A theory of pseudoskeleton approximations. Linear Algebra Appl. 261(1), 1–21 (1997). https://doi.org/10.1016/S0024-3795(96)00301-1

    Article  MathSciNet  MATH  Google Scholar 

  2. Golub, G.H., Van Loan, C.F.: Matrix Computations. JHU press, Baltimore, MD, USA (2013)

    Book  MATH  Google Scholar 

  3. Trefethen, L.N., Bau, D.: Numerical Linear Algebra, vol. 181. Siam, Philadelphia, PA, USA (2022)

    MATH  Google Scholar 

  4. Kezhong Zhao, Vouvakis, M.N., Jin-Fa Lee: The adaptive cross approximation algorithm for accelerated method of moments computations of emc problems. IEEE Trans. Electromagn. Compatibility 47(4), 763–773 (2005). https://doi.org/10.1109/TEMC.2005.857898

  5. Gu, M., Eisenstat, S.C.: Efficient algorithms for computing a strong rankrevealing qr factorization. SIAM J. Sci. Comput. 17(4), 848–869 (1996). https://doi.org/10.1137/0917055

    Article  MathSciNet  MATH  Google Scholar 

  6. Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2011). https://doi.org/10.1137/090771806

    Article  MathSciNet  MATH  Google Scholar 

  7. Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., Tygert, M.: Randomized algorithms for the low-rank approximation of matrices. Proceedings of the National Academy of Sciences 104(51), 20167–20172 (2007) https://arxiv.org/abs/https://www.pnas.org/content/104/51/20167.full.pdf. https://doi.org/10.1073/pnas.0709640104

  8. Drmač, Z., Gugercin, S.: A new selection operator for the discrete empirical interpolation method–improved a priori error bound and extensions. SIAM J. Sci. Comput. 38(2), 631–648 (2016). https://arxiv.org/abs/https://doi.org/10.1137/15M1019271. https://doi.org/10.1137/15M1019271

  9. Sorensen, D.C., Embree, M.: A deim induced cur factorization. SIAM J. Sci. Comput. 38(3), 1454–1482 (2016). https://arxiv.org/abs/https://doi.org/10.1137/140978430. https://doi.org/10.1137/140978430

  10. Anderson, D., Gu, M.: An efficient, sparsity-preserving, online algorithm for low-rank approximation. In: International Conference on Machine Learning, pp. 156–165 (2017). PMLR

  11. Chen, C., Gu, M., Zhang, Z., Zhang, W., Yu, Y.: Efficient spectrum-revealing cur matrix decomposition. In: International Conference on Artificial Intelligence and Statistics, pp. 766–775 (2020). PMLR

  12. Cohen, M.B., Lee, Y.T., Musco, C., Musco, C., Peng, R., Sidford, A.: Uniform sampling for matrix approximation. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science. ITCS ’15, pp. 181–190. Association for Computing Machinery, New York, NY, USA (2015). https://doi.org/10.1145/2688073.2688113

  13. Derezinski, M., Khanna, R., Mahoney, M.W.: Improved guarantees and a multiple-descent curve for the column subset selection problem and the nyström method. arXiv:2002.09073 (2020)

  14. Dereziński, M., Mahoney, M.: Determinantal point processes in randomized numerical linear algebra. Notices Am. Math. Soc. 68, 1 (2021). https://doi.org/10.1090/noti2202

    Article  MathSciNet  MATH  Google Scholar 

  15. Drineas, P., Magdon-Ismail, M., Mahoney, M.W., Woodruff, D.P.: Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res. 13(1), 3475–3506 (2012)

    MathSciNet  MATH  Google Scholar 

  16. Mahoney, M.W., Drineas, P.: Cur matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences 106(3), 697–702 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Voronin, S., Martinsson, P.-G.: Efficient algorithms for cur and interpolative matrix decompositions. Adv. Computat. Math. 43(3), 495–516 (2017). https://doi.org/10.1007/s10444-016-9494-8

    Article  MathSciNet  MATH  Google Scholar 

  18. Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC ’98, pp. 604–613. Association for Computing Machinery, New York, NY, USA (1998). https://doi.org/10.1145/276698.276876

  19. Martinsson, P.-G., Tropp, J.A.: Randomized numerical linear algebra: foundations and algorithms. Acta Numerica 29, 403–572 (2020). https://doi.org/10.1017/S0962492920000021

    Article  MathSciNet  MATH  Google Scholar 

  20. Woodruff, D.P.: Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. 10(1–2), 1–157 (2014). https://doi.org/10.1561/0400000060

  21. Boutsidis, C., Gittens, A.: Improved matrix algorithms via the subsampled randomized hadamard transform. SIAM J. Matrix Anal. Appl. 34(3), 1301–1340 (2013). https://doi.org/10.1137/120874540

  22. Rokhlin, V., Tygert, M.: A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences 105(36), 13212–13217 (2008) https://arxiv.org/abs/https://www.pnas.org/content/105/36/13212.full.pdf. https://doi.org/10.1073/pnas.0804869105

  23. Tropp, J.A.: Improved analysis of the subsampled randomized hadamard transform. Adv. Adaptive Data Anal. 03(01n02), 115–126 (2011). https://doi.org/10.1142/S1793536911000787

  24. Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Appl. Computat. Harmonic Anal. 25(3), 335–366 (2008). https://doi.org/10.1016/j.acha.2007.12.002

  25. Clarkson, K.L., Woodruff, D.P.: Low-rank approximation and regression in input sparsity time. J. ACM 63(6) (2017). https://doi.org/10.1145/3019134

  26. Meng, X., Mahoney, M.W.: Low-distortion subspace embeddings in inputsparsity time and applications to robust linear regression. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing. STOC ’13, pp. 91–100. Association for Computing Machinery, New York, NY, USA (2013). https://doi.org/10.1145/2488608.2488621

  27. Nelson, J., Nguyên, H.L.: Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 117–126 (2013). https://doi.org/10.1109/FOCS.2013.21

  28. Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Fixed-rank approximation of a positive-semidefinite matrix from streaming data. Adv. Neural Inf. Process. Syst. 30 (2017)

  29. Kahan, W.: Numerical linear algebra. Canadian Math. Bull. 9(5), 757–801 (1966). https://doi.org/10.4153/CMB-1966-083-2

    Article  Google Scholar 

  30. Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika 1(3), 211–218 (1936). https://doi.org/10.1007/BF02288367

    Article  MATH  Google Scholar 

  31. Anderson, D., Du, S., Mahoney, M., Melgaard, C., Wu, K., Gu, M.: Spectral gap error bounds for improving CUR matrix decomposition and the Nyström method. In: Lebanon, G., Vishwanathan, S.V.N. (eds.) Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, 38, pp. 19–27. PMLR, San Diego, California, USA (2015). https://proceedings.mlr.press/v38/anderson15.html

  32. Civril, A., Magdon-Ismail, M.: Exponential inapproximability of selecting a maximum volume sub-matrix. Algorithmica 65(1), 159–176 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  33. Çivril, A., Magdon-Ismail, M.: On selecting a maximum volume sub-matrix of a matrix and related problems. Theor. Comput. Sci. 410(47), 4801–4811 (2009). https://doi.org/10.1016/j.tcs.2009.06.018

    Article  MathSciNet  MATH  Google Scholar 

  34. Deshpande, A., Rademacher, L., Vempala, S., Wang, G.: Matrix approximation and projective clustering via volume sampling. Theory Comput. 2(12), 225–247 (2006). https://doi.org/10.4086/toc.2006.v002a012

    Article  MathSciNet  MATH  Google Scholar 

  35. Deshpande, A., Rademacher, L.: Efficient volume sampling for row/column subset selection. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 329–338 (2010). https://doi.org/10.1109/FOCS.2010.38

  36. Cortinovis, A., Kressner, D.: Low-rank approximation in the frobenius norm by column and row subset selection. SIAM J. Matrix Anal. Appl. 41(4), 1651–1673 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  37. Tropp, J.A., Yurtsever, A., Udell, M., Cevher, V.: Streaming low-rank matrix approximation with an application to scientific simulation. SIAM J. Sci. Comput. 41(4), 2430–2463 (2019). https://doi.org/10.1137/18M1201068

    Article  MathSciNet  MATH  Google Scholar 

  38. Musco, C., Musco, C.: Randomized block krylov methods for stronger and faster approximate singular value decomposition. In: Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1. NIPS’15, pp. 1396–1404. MIT Press, Cambridge, MA, USA (2015)

  39. Davidson, K.R., Szarek, S.J.: Local operator theory, random matrices and Banach spaces. Handbook of the Geometry of Banach Spaces 1(317–366), 131 (2001)

    MATH  Google Scholar 

  40. Rudelson, M.: Invertibility of random matrices: norm of the inverse. Annal. Math. 168(2), 575–600 (2008). Accessed 2022-08-09

  41. Householder, A.S.: Unitary triangularization of a nonsymmetric matrix. J. ACM 5(4), 339–342 (1958). https://doi.org/10.1145/320941.320947

    Article  MathSciNet  MATH  Google Scholar 

  42. Trefethen, L.N., Schreiber, R.S.: Average-case stability of gaussian elimination. SIAM Journal on Matrix Analysis and Applications 11(3), 335–360 (1990). https://doi.org/10.1137/0611023

    Article  MathSciNet  MATH  Google Scholar 

  43. Chan, T.F.: Rank revealing QR factorizations. Linear Algebra and its Applications 88–89, 67–82 (1987). https://doi.org/10.1016/0024-3795(87)90103-0

  44. Hong, Y.P., Pan, C.-T.: Rank-revealing QR factorizations and the singular value decomposition. Math. Computat. 58(197), 213–232 (1992)

    MathSciNet  MATH  Google Scholar 

  45. Peters, G., Wilkinson, J.H.: On the stability of Gauss-Jordan elimination with pivoting. Commun. ACM 18(1), 20–24 (1975). https://doi.org/10.1145/360569.360653

    Article  MathSciNet  MATH  Google Scholar 

  46. Geist, G.A., Romine, C.H.: \(lu\) factorization algorithms on distributed memory multiprocessor architectures. SIAM J. Sci. Stat. Comput. 9(4), 639–649 (1988). https://doi.org/10.1137/0909042

    Article  MathSciNet  MATH  Google Scholar 

  47. Kurzak, J., Luszczek, P., Faverge, M., Dongarra, J.: Lu factorization with partial pivoting for a multicore system with accelerators. IEEE Trans. Parallel Distribut. Syst. 24(8), 1613–1621 (2013). https://doi.org/10.1109/TPDS.2012.242

    Article  Google Scholar 

  48. Grigori, L., Demmel, J.W., Xiang, H.: Calu: A communication optimal LU factorization algorithm. SIAM J. Matrix Anal. Appl. 32(4), 1317–1350 (2011). https://doi.org/10.1137/100788926

  49. Solomonik, E., Demmel, J.: Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011 Parallel Processing, pp. 90–109. Springer, Berlin, Heidelberg (2011)

  50. Pan, V.Y., Qian, G., Yan, X.: Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation. Linear Algebra Appl. 481, 202–234 (2015). https://doi.org/10.1016/j.laa.2015.04.021

    Article  MathSciNet  MATH  Google Scholar 

  51. Pan, V.Y., Zhao, L.: Numerically safe Gaussian elimination with no pivoting. Linear Algebra Appl. 527, 349–383 (2017). https://doi.org/10.1016/j.laa.2017.04.007

    Article  MathSciNet  MATH  Google Scholar 

  52. Bebendorf, M.: Approximation of boundary element matrices. Numerische Mathematik 86, 565–589 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  53. Tyrtyshnikov, E.: Incomplete cross approximation in the mosaic-skeleton method. Computing 64(4), 367–380 (2000). https://doi.org/10.1007/s006070070031

    Article  MathSciNet  MATH  Google Scholar 

  54. Pan, C.-T.: On the existence and computation of rank-revealing LU factorizations. Linear Algebra and its Applications 316(1), 199–222 (2000). https://doi.org/10.1016/S0024-3795(00)00120-8. Special Issue: Conference celebrating the 60th birthday of Robert J. Plemmons

  55. Miranian, L., Gu, M.: Strong rank revealing LU factorizations. Linear Algebra Appl. 367, 1–16 (2003). https://doi.org/10.1016/S0024-3795(02)00572-4

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  57. Bien, J., Xu, Y., Mahoney, M.: Cur from a sparse optimization viewpoint. Annual Advances in Neural Information Processing Systems 24: Proceedings of the 2010 Conference (2010)

  58. Wang, S., Zhang, Z.: A scalable cur matrix decomposition algorithm: Lower time complexity and tighter bound. In: Proceedings of the 25th International Conference on Neural Information Processing Systems - 1. NIPS’12, pp. 647–655. Curran Associates Inc., Red Hook, NY, USA (2012)

  59. Boutsidis, C., Woodruff, D.P.: Optimal cur matrix decompositions. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing. STOC ’14, pp. 353–362. Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2591796.2591819

  60. Boutsidis, C., Drineas, P., Magdon-Ismail, M.: Near-optimal column-based matrix reconstruction. SIAM J. Comput. 43(2), 687–717 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  61. Aizenbud, Y., Shabat, G., Averbuch, A.: Randomized LU decomposition using sparse projections. Comput. & Math. Appl. 72(9), 2525–2534 (2016). https://doi.org/10.1016/j.camwa.2016.09.014

    Article  MathSciNet  MATH  Google Scholar 

  62. Shabat, G., Shmueli, Y., Aizenbud, Y., Averbuch, A.: Randomized LU decomposition. Appl. Computat. Harmonic Anal. 44(2), 246–272 (2018). https://doi.org/10.1016/j.acha.2016.04.006

    Article  MathSciNet  MATH  Google Scholar 

  63. Batson, J.D., Spielman, D.A., Srivastava, N.: Twice-ramanujan sparsifiers. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. STOC ’09, pp. 255–262. Association for Computing Machinery, New York, NY, USA (2009). https://doi.org/10.1145/1536414.1536451

  64. Ho, K., Olver, S., Kelman, T., Jarlebring, E., TagBot, J., Slevinsky, M.: LowRankApprox,jl: v0.4.3. GitHub (2020)

  65. Meszaros, C.: Meszaros/large, LP sequence: large000 to large036. http://old.sztaki.hu/~meszaros/public_ftp/lptestset/ (2004)

Download references

Acknowledgements

The work reported was supported by the Office of Naval Research (N00014-18-1-2354), by the National Science Foundation (DMS-1952735 and DMS-2012606), and by the Department of Energy ASCR (DE-SC0022251). The authors wish to thank Chao Chen, Ke Chen, Yuji Nakatsukasa, and Rachel Ward for valuable discussions.

Author information

Authors and Affiliations

  1. Oden Institute for Computational Engineering & Sciences, The University of Texas at Austin, 201 E 24th St, Austin, TX, 78712, USA

    Yijun Dong & Per-Gunnar Martinsson

  2. Department of Mathematics, The University of Texas at Austin, 2515 Speedway, PMA 8.100, Austin, TX, 78712, USA

    Per-Gunnar Martinsson

Authors
  1. Yijun Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Per-Gunnar Martinsson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Per-Gunnar Martinsson.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Communicated by: Raymond H. Chan

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

Dong, Y., Martinsson, PG. Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions. Adv Comput Math 49, 66 (2023). https://doi.org/10.1007/s10444-023-10061-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10444-023-10061-z

Keywords

Mathematics Subject Classification (2010)

Search

Navigation