Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations | Numerical Algorithms Skip to main content
Springer Nature Link
Log in

Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

A randomized quaternion singular value decomposition algorithm based on block Krylov iteration (RQSVD-BKI) is presented to solve the low-rank quaternion matrix approximation problem. The upper bounds of deterministic approximation error and expected approximation error for the RQSVD-BKI algorithm are also given. It is shown by numerical experiments that the running time of the RQSVD-BKI algorithm is smaller than that of the quaternion singular value decomposition, and the relative errors of the RQSVD-BKI algorithm are smaller than those of the randomized quaternion singular value decomposition algorithm in Liu et al. (SIAM J. Sci. Comput., 44(2): A870-A900 (2022)) in some cases. In order to further illustrate the feasibility and effectiveness of the RQSVD-BKI algorithm, we use it to deal with the problem of color image inpainting.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 3
Fig. 5
Algorithm 4
Fig. 6

Similar content being viewed by others

Data availability

Data sharing is not applicable to this article as no new data were created or analyzed in this study.

References

  1. Arrigo, F., Benzi, M., Fenu, C.: Computation of generalized matrix functions. SIAM J. Matrix Anal. Appl. 37, 836–860 (2016)

    Article  MathSciNet  Google Scholar 

  2. Bihan, N.L., Sangwine, S.J.: Jacobi method for quaternion matrix singular value decomposition. Appl. Math. Comput. 187, 1265–1271 (2007)

    MathSciNet  Google Scholar 

  3. Cai, J.F., Candès, E.J., Shen, Z.W.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)

    Article  MathSciNet  Google Scholar 

  4. Candes, E.J., Plan, Y.: Matrix completion with noise. In: Setti, G. (ed.): Proc. of the IEEE. 98, 925-936 (2010)

  5. Chen, J., Ng, M.K.: Color image inpainting via robust pure quaternion matrix completion: error bound and weighted loss. SIAM Journal on Imaging Sciences 15, 1469–1498 (2022)

    Article  MathSciNet  Google Scholar 

  6. Chen, Y., Jia, Z.G., Peng, Y., Peng, Y.X., Zhang, D.: A new structure-preserving quaternion QR decomposition method for color image blind watermarking. Signal Process. 185, 108088 (2021)

    Article  Google Scholar 

  7. Chen, Y.N., Qi, L.Q., Zhang, X.Z., Xu, Y.W.: A low rank quaternion decomposition algorithm and its application in color image inpainting. arXiv preprint arXiv: 2009. 12203 (2020)

  8. Chen, Y.Y., Xiao, X.L., Zhou, Y.C.: Low-rank quaternion approximation for color image processing. IEEE Trans. Image Process. 29, 1426–1439 (2019)

    Article  MathSciNet  Google Scholar 

  9. Cheng, D., Kou, K.I.: Generalized sampling expansions associated with quaternion Fourier transform. Math. Methods Appl. Sci. 41, 4021–4032 (2018)

    Article  MathSciNet  Google Scholar 

  10. Clarkson, K.L., Woodruff, D.P.: Numerical linear algebra in the streaming model, in Proceedings of the forty-first Annual ACM Symposium on Theory of Computing(STOC), 205-214 (2009)

  11. Drineas, P., Ipsen, I.C.F., Kontopoulou, E.M., Magdon-Ismail, M.: Structural convergence results for approximation of dominant subspaces from block Krylov spaces. SIAM J. Matrix Anal. Appl. 39, 567–586 (2018)

    Article  MathSciNet  Google Scholar 

  12. Ell, T.A., Bihan, N.L., Sangwine, S.J.: Quaternion Fourier transforms for signal and image processing, John Wiley & Sons (2014)

  13. Gai, S., Yang, G.W., Wan, M.H., Wang, L.: Denoising color images by reduced quaternion matrix singular value decomposition. Multidim. Syst. Sign. Process. 26, 307–320 (2015)

    Article  MathSciNet  Google Scholar 

  14. Golub, G.H., Van Loan, C.F.: Matrix computations. Johns Hopkins University Press, Baltimore (2013)

    Book  Google Scholar 

  15. Grigoryan, A.M., Agaian, S.S.: Tensor transform-based quaternion Fourier transform algorithm. Information Sciences. 320, 62–74 (2015)

    Article  MathSciNet  Google Scholar 

  16. 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 

  17. Hamilton, W.R.: Elements of quaternions. Longmans, Green, & Company, London (1866)

    Google Scholar 

  18. Horé, A., Ziou, D.: Image quality metrics: PSNR vs. SSIM. In: Guerrero, J.E. (ed.): 2010 20th International Conference on Pattern Recognition. IEEE. 2366-2369 (2010)

  19. Horn, R.A., Johnson, C.R.: Topics in matrix analysis. Cambridge University Press, UK (1994)

    Google Scholar 

  20. Jia, Z.G., Ng, M.K., Song, G.J.: Robust quaternion matrix completion with applications to image inpainting. Numer. Linear Algebra Appl. 26, 2245 (2019)

    Article  MathSciNet  Google Scholar 

  21. Jia, Z.G., Jin, Q.Y., Ng, M.K., Zhao, X.L.: Non-local robust quaternion matrix completion for large-scale color image and video inpainting. IEEE Trans. Image Process. 31, 3868–3883 (2022)

    Article  Google Scholar 

  22. Jia, Z.G., Ng, M.K., Song, G.J.: Lanczos method for large-scale quaternion singular value decomposition. Numer. Algorithms. 82, 699–717 (2019)

    Article  MathSciNet  Google Scholar 

  23. Jiang, T.S., Chen, L.: Algebraic algorithms for least squares problem in quaternionic quantum theory. Comput. Phys. Commun. 176, 481–485 (2007)

    Article  Google Scholar 

  24. Li, Y., Wei, M.S., Zhang, F.X., Zhao, J.L.: A fast structure-preserving method for computing the singular value decomposition of quaternion matrices. Appl. Math. Comput. 235, 157–167 (2014)

    MathSciNet  Google Scholar 

  25. Liu, Q.H., Ling, S.T., Jia, Z.G.: Randomized quaternion singular value decomposition for low-rank matrix approximation. SIAM J. Sci. Comput. 44, A870–A900 (2022)

    Article  MathSciNet  Google Scholar 

  26. Lv, H., Zhang, H.S.: Quaternion extreme learning machine. In: Cao, J.W., Cambria, E., Lendasse A., Miche, Y., Vong, C.M. (eds.): Proceedings of ELM-2016, Springer International Publishing, 27-36 (2018)

  27. Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Werner, B. (ed.): Proc. ICCV. 2, 416-423 (2001)

  28. Miao, J.F., Kou, K.I., Liu, W.K.: Low-rank quaternion tensor completion for recovering color videos and images. Pattern Recognition. 107, 107505 (2020)

    Article  Google Scholar 

  29. Miao, J.F., Kou, K.I.: Color image recovery using low-rank quaternion matrix completion algorithm. IEEE Trans. Image Process. 31, 190–201 (2021)

    Article  Google Scholar 

  30. Minemoto, T., Isokawa, T., Nishimura, H., Matsui, N.: Feed forward neural network with random quaternionic neurons. Signal Process. 136, 59–68 (2017)

    Article  Google Scholar 

  31. Musco, C., Musco, C.: Randomized block Krylov methods for stronger and faster approximate singular value decomposition. Advances in Neural Information Processing Systems. 28, 1–9 (2015)

    Google Scholar 

  32. Pei, S.C., Cheng, C.M.: A novel block truncation coding of color images using a quaternion-moment-preserving principle. IEEE Trans. Commun. 45, 583–595 (1997)

    Article  Google Scholar 

  33. Ren, H., Ma, R.R., Liu, Q.H., Bai, Z.J.: Randomized quaternion QLP decomposition for low-rank approximation. J Sci Comput. 92, 80 (2022)

    Article  MathSciNet  Google Scholar 

  34. Sangwine, S.J., Bihan, N.L.: Quaternion singular value decomposition based on bidiagonalization to a real or complex matrix using quaternion householder transformations. Appl. Math. Comput. 182, 727–738 (2006)

    MathSciNet  Google Scholar 

  35. Song, G.J., Ding, W.Y., Ng, M.K.: Low rank pure quaternion approximation for pure quaternion matrices. SIAM J. Matrix Anal. Appl. 42, 58–82 (2021)

    Article  MathSciNet  Google Scholar 

  36. Soo, C.P., Chang, J.H., Ding, J.J.: Quaternion matrix singular value decomposition and its applications for color image processing. In: Ltd, S.O. (ed.): Proceedings 2003 International Conference on Image Processing(Cat. No. 03CH37429). IEEE. 1, 805-808 (2003)

  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, A2430–A2463 (2019)

    Article  MathSciNet  Google Scholar 

  38. Wang, G., Zhang, D., Vasiliev, V.I., Jiang, T.S.: A complex structure-preserving algorithm for the full rank decomposition of quaternion matrices and its applications. Numer Algorithms. 91, 1461–1481 (2022)

    Article  MathSciNet  Google Scholar 

  39. Wei, M.S., Li, Y., Zhang, F.X., Zhao, J.L.: Quaternion matrix computations, Nova Science Publishers (2018)

  40. Xu, Y., Yu, L.C., Xu, H.T., Zhang, H., Nguyen, T.: Vector sparse representation of color image using quaternion matrix analysis. IEEE Trans. Image Process. 24, 1315–1329 (2015)

    Article  MathSciNet  Google Scholar 

  41. Yang, L.Q., Kou, K.I., Miao, J.F.: Weighted truncated nuclear norm regularization for low-rank quaternion matrix completion. J. Vis. Commun. Image Represent. 81, 103335 (2021)

    Article  Google Scholar 

  42. Yang, L.Q., Miao, J.F., Kou, K.I.: Quaternion-based color image completion via logarithmic approximation. Information Sciences. 588, 82–105 (2022)

    Article  Google Scholar 

  43. Yu, Y.B., Zhang, Y.L., Yuan, S.F.: Quaternion-based weighted nuclear norm minimization for color image denoising. Neurocomputing. 332, 283–297 (2019)

    Article  Google Scholar 

  44. Zhang, F.Z.: Quaternions and matrices of quaternions. Linear Algebra Appl. 251, 21–57 (1997)

    Article  MathSciNet  Google Scholar 

  45. Zhao, M.X., Jia, Z.G., Cai, Y.F., Chen, X., Gong, D.W.: Advanced variations of two-dimensional principal component analysis for face recognition. Neurocomputing. 452, 653–664 (2021)

    Article  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the reviewers for their valuable and constructive suggestions, in particular, for pointing out the difference between real random matrices and quaternion random matrices in numerical experiments.

Funding

This work is supported in part by the National Natural Science Foundation of China (12061087), Yunnan Provincial Xing Dian Talent Support Program, China Postdoctoral Science Foundation (2023T160554), the Graduate Research Innovation Fund Project of Yunnan University, and the Sichuan Science and Technology Program (2022ZYD0006).

Author information

Authors and Affiliations

  1. School of Mathematics and Statistics, Yunnan University, 650091, Kunming, People’s Republic of China

    Chaoqian Li, Yonghe Liu & Fengsheng Wu

  2. School of Mathematics, Southwestern University of Finance and Economics, 611130, Chengdu, People’s Republic of China

    Maolin Che

Authors
  1. Chaoqian Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yonghe Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fengsheng Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Maolin Che
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

CL (first author): conceptualization, methodology, writing—original draft. YL and FW: data curation, visualization, investigation, writing—original draft. MC (corresponding author): conceptualization, writing—review and editing.

Corresponding author

Correspondence to Maolin Che.

Ethics declarations

Ethical approval

Not applicable

Conflict of interest

The authors declare no competing interests.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, C., Liu, Y., Wu, F. et al. Randomized block Krylov subspace algorithms for low-rank quaternion matrix approximations. Numer Algor 96, 687–717 (2024). https://doi.org/10.1007/s11075-023-01662-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-023-01662-2

Keywords

Mathematics Subject Classification (2010)

Search

Navigation