A fast SVD for multilevel block Hankel matrices with minimal memory storage | Numerical Algorithms Skip to main content
Springer Nature Link
Log in

A fast SVD for multilevel block Hankel matrices with minimal memory storage

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

Abstract

Motivated by the Cadzow filtering in seismic data processing, this paper presents a fast SVD method for multilevel block Hankel matrices. A seismic data presented as a multidimensional array is first transformed into a two dimensional multilevel block Hankel (MBH) matrix. Then the Lanczos process is applied to reduce the MBH matrix into a bidiagonal or tridiagonal matrix. Finally, the SVD of the reduced matrix is computed using the twisted factorization method. To achieve high efficiency, we propose a novel fast MBH matrix-vector multiplication method for the Lanczos process. In comparison with existing fast Hankel matrix-vector multiplication methods, our method applies 1-D, instead of multidimensional, FFT and requires minimum storage. Moreover, a partial SVD is performed on the reduced matrix, since complete SVD is not required by the Caszow filtering. Our numerical experiments show that our fast MBH matrix-vector multiplication method significantly improves both the computational cost and storage requirement. Our fast MBH SVD algorithm is particularly efficient for large size multilevel block Hankel matrices.

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

Similar content being viewed by others

References

  1. Barrowes, B.E., Teixeira, F.L., Kong, J.A.: Fast algorithm for matrix-vector multiply of asymmetric multilevel block-toeplitz matrices. IEEE Antennas Propag. Soc. Int. Symp. 4, 630–633 (2001)

    Google Scholar 

  2. Browne, K., Qiao, S., Wei, Y.: A lanczos bidiagonalization algorithm for hankel matrices. Linear Algebra Appl. 430, 1531–1543 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Barker, V.A., Blackford, L.S., Dongarra, J., Du Croz, J., Hammarling, S., Marinova, M., Wásniewski, J., Yalamov, P.: LAPACK95 Users’ Guide”, SIAM. Philadelphia, Pennsylvania (2001)

    Book  Google Scholar 

  4. Broomhead, D., King, G.: Extracting qualitative dynamics from experimental data. Phys. D Nonlinear Phenom. 20(2), 217–236 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cadzow, J.: Signal enhancement a composite property mapping algorithm. IEEE Trans. Acoust., Speech, Sig. Process. 36, 49–62 (1988)

    Article  MATH  Google Scholar 

  6. Chan, R.H., Jin, X.: An Introduction to Iterative Toeplitz Solvers, 3rd edition, SIAM. Philadelphia, Pennsylvania (2007)

    Book  Google Scholar 

  7. Chu, M.T., Funderlic, R.E., Plemmons, R.J.: Structured low rank approximation. Linear Algebra Appl. 366, 157–172 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dhillon, I.S.: A new O(n 2) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem,PhD thesis, University of California, Berkeley, CA (1997)

  9. Falkovskiy, A., Floreani, E., Schlosser, G.: FX Cadzow / SSA random noise filter: frequency extension,2011 CSPG CSEG CWLS Convention, pp. 1–8 (2011)

  10. Fernando, F.V.: On computing an eigenvector of a tridiagonal matrix. SIAM Matrix Anal. Appl. 18, 1013–1034 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  11. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edition. Johns Hopkins University Press, Baltimore, MD (2009)

    Google Scholar 

  12. Ghil, M., Allen, M., Dettinger, M., Ide, K., Kondrashov, D., Mann, M., Robertson, A., Saunders, A., Tian, Y., Varadi, F., Yiou, P.: Advance spectral methods for climatic time series. Rev. Geophys. 40, 1–41 (2002)

    Article  Google Scholar 

  13. Gao, J., Sacchi, M.D., Chen, X.: A fast reduced-rank interpolation method for prestack seismic volumes that depend on four spatial dimensions. Geophysics 78(1), V21–V30 (2013)

    Article  Google Scholar 

  14. Liberty, E., Woolfe, F., Martinsson, P.G., Rokhlin, V., Tygerts, M.: Randomized algorithms for the low-rank approximation of matrices. Proc. Natl. Acad. Sci. USA 104(51), 20167–20172 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  15. Markovsky, I.: Low rank approximation: algorithms, implementation, applications. Springer (2012)

  16. Oropeza, V.E., Sacchi, M.D.: A randomized SVD for Multichannel Singular Spectrum Analysis (MSSA) noise attenuation, JSEG Denver 2010 Annual Meeting, pp. 3539–3544 (2010)

  17. Oropeza, V.E., Sacchi, M.D.: Simultaneous seismic data denoising and reconstruction via multichannel singular spectrum analysis. Geophysics 76(3), 25–32 (2011)

    Article  Google Scholar 

  18. Qiao, S., Liu, G., Xu, W.: Block lanczos tridiagonalization of complex symmetric matrices,Optics & Photonics 2005, International Society for Optics and Photonics, 591010-591010 (2005)

  19. Sanliturk, K.Y., Cakar, O.: Noise elimination from measured frequency response functions. Mech. Syst. Signal Process. 19(3), 615–631 (2005)

    Article  Google Scholar 

  20. Tsang, L., Ding, K.H., Shih, S.E., Kong, J.A.: Scattering of electromagnetic waves from dense distributions of spheroidal particles based on Monte Carlo simulations. J. Opt. Soc. Amer. A 15, 2660–2669 (1998)

    Article  Google Scholar 

  21. Trickeett, S.: F-xy Cadzow noise suppression,CSPG CSEG CWLS Convention, pp. 303–306 (2008)

  22. Trickeett, S., Burroughs, L.: Prestack rank-reduction-based noise suppression. CSEG Recorder 34, 3193–3196 (2009)

    Google Scholar 

  23. Trickeett, S., Burroughs, L., Milton, A., Walton, L., Dack, R: Rank-reduction-based trace interpolation, 81st Annual International Meeting, SEG,Expanded Abstracts, pp. 1989–1992 (2010)

  24. Ulrych, T., Freire, S., Siston, P.: Eigenimage Processing of Seismic Sections. SEG Extended Abstr. 7, 1261 (1988)

    Google Scholar 

  25. van Loan, C.: Computational frameworks for the fast Fourier transform, SIAM. Pennsylvania, Philadelphia (1992)

    Book  Google Scholar 

  26. Xu, W., Qiao, S.: A twisted factorization method for symmetric SVD of a complex symmetric tridiagonal matrix. Numer. Linear Algebra Appl. 16, 801–815 (2009)

    Article  MathSciNet  Google Scholar 

  27. Xu, W., Qiao, S.: A fast SVD algorithm for square hankel matrices. Linear Algebra Appl. 428, 550–563 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  28. Zhang, H., Thurber, C.H.: Estimating the model resolution matrix for large seismic tomography problems based on Lanczos bidiagonalization with partial reorthogonalization. Geophys. J. Int. 170, 337–345 (2007)

    Article  Google Scholar 

  29. Zhang, L., Peng, W., Yuan, C.: An improved method for noise reduction based on singular value decomposition. Chin. J. Ship Res. 7(5), 83–88 (2012)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Tongji University, Shanghai, 200092, People’s Republic of China

    Ling Lu & Wei Xu

  2. Department of Computing and Software, McMaster University, Hamilton, Ontario, L8S 4K1, Canada

    Sanzheng Qiao

Authors
  1. Ling Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sanzheng Qiao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Wei Xu.

Additional information

This work was supported by the Natural Science Foundation of China (Project No: 11101310) and Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lu, L., Xu, W. & Qiao, S. A fast SVD for multilevel block Hankel matrices with minimal memory storage. Numer Algor 69, 875–891 (2015). https://doi.org/10.1007/s11075-014-9930-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-014-9930-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation