Abstract

Singular value decomposition (SVD)-based approaches, e.g., truncated SVD and Tikhonov regularization methods, are effective ways to solve problems of small or moderate size. However, SVD, in the sense of computation, is expensive when it is applied in large-sized cases. A multilevel method (MLM) combining SVD-based methods with the thresholding technique for signal restoration is proposed in this paper. Our MLM will transfer large-sized problems to small- or moderate-sized problems in order to make the SVD-based methods available. The linear systems on the coarsest level in the multilevel process will be solved by the Tikhonov regularization method. No presmoothers are implemented in the multilevel process to avoid damaging the parameter choice on the coarsest level. Furthermore, the soft-thresholding denoising technique is employed for the postsmoothers aiming to eliminate the leaving high-frequency information due to the lack of presmoothers. Finally, computational experiments show that our method outperforms other SVD-based methods in signal restoration ability at a shorter CPU-time consumption.

© 2013 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problem: Numerical Aspects of Linear Inversion (SIAM, 1998).
  2. P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering (SIAM, 2006).
  3. M. Fuhry and L. Reichel, “A new Tikhonov regularization method,” Numer. Algorithms 59, 433–445 (2012).
    [CrossRef]
  4. W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed. (SIAM, 2000).
  5. M. Donatelli and S. Serra Capizzano, “On the regularizing power of multigrid-type algorithms,” SIAM J. Sci. Comput. 27, 2053–2076 (2006).
    [CrossRef]
  6. M. Donatelli, “A multigrid for image deblurring with Tikhonov regularization,” Numer. Linear Algebra Appl. 12, 715–729 (2005).
    [CrossRef]
  7. W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
    [CrossRef]
  8. M. Hanke and C. R. Vogel, “Two-level preconditioners for regularized inverse problems I: theory,” Numer. Math. 83, 385–402 (1999).
    [CrossRef]
  9. B. Kaltenbacher, “On the regularizing properties of a full multigrid method for ill-posed problems,” Inverse Probl. 17, 767–788 (2001).
    [CrossRef]
  10. S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
    [CrossRef]
  11. L. Reichel and A. Shyshkov, “Cascadic multilevel methods for ill-posed problems,” J. Comput. Appl. Math. 233, 1314–1325 (2010).
    [CrossRef]
  12. M. I. Español, “Multilevel methods for discrete ill-posed problems: application to deblurring,” Ph.D. thesis (Tufts University, 2009).
  13. M. I. Español and M. E. Kilmer, “Multilevel approach for signal restoration problems with Toeplitz matrices,” SIAM J. Sci. Comput. 32, 299–319 (2010).
    [CrossRef]
  14. M. Donatelli, “An iterative multigrid regularization method for Toeplitz discrete ill-posed problems,” Numer. Math. Theory Methods Appl. 5, 43–61 (2012).
  15. D. L. Donoho, “De-noising by soft-thresholding,” IEEE Trans. Inf. Theory 41, 613–627 (1995).
    [CrossRef]
  16. S. Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, 3rd. ed. (Academic, 1998).
  17. P. C. Hansen, “Regularization tools version 4.0 for Matlab 7.3,” Numer. Algorithms 46, 189–194 (2007).
    [CrossRef]

2012 (2)

M. Fuhry and L. Reichel, “A new Tikhonov regularization method,” Numer. Algorithms 59, 433–445 (2012).
[CrossRef]

M. Donatelli, “An iterative multigrid regularization method for Toeplitz discrete ill-posed problems,” Numer. Math. Theory Methods Appl. 5, 43–61 (2012).

2010 (2)

L. Reichel and A. Shyshkov, “Cascadic multilevel methods for ill-posed problems,” J. Comput. Appl. Math. 233, 1314–1325 (2010).
[CrossRef]

M. I. Español and M. E. Kilmer, “Multilevel approach for signal restoration problems with Toeplitz matrices,” SIAM J. Sci. Comput. 32, 299–319 (2010).
[CrossRef]

2008 (1)

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

2007 (1)

P. C. Hansen, “Regularization tools version 4.0 for Matlab 7.3,” Numer. Algorithms 46, 189–194 (2007).
[CrossRef]

2006 (1)

M. Donatelli and S. Serra Capizzano, “On the regularizing power of multigrid-type algorithms,” SIAM J. Sci. Comput. 27, 2053–2076 (2006).
[CrossRef]

2005 (1)

M. Donatelli, “A multigrid for image deblurring with Tikhonov regularization,” Numer. Linear Algebra Appl. 12, 715–729 (2005).
[CrossRef]

2001 (1)

B. Kaltenbacher, “On the regularizing properties of a full multigrid method for ill-posed problems,” Inverse Probl. 17, 767–788 (2001).
[CrossRef]

1999 (1)

M. Hanke and C. R. Vogel, “Two-level preconditioners for regularized inverse problems I: theory,” Numer. Math. 83, 385–402 (1999).
[CrossRef]

1997 (1)

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

1995 (1)

D. L. Donoho, “De-noising by soft-thresholding,” IEEE Trans. Inf. Theory 41, 613–627 (1995).
[CrossRef]

Barbour, R. L.

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

Briggs, W. L.

W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed. (SIAM, 2000).

Deng, Y.

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

Donatelli, M.

M. Donatelli, “An iterative multigrid regularization method for Toeplitz discrete ill-posed problems,” Numer. Math. Theory Methods Appl. 5, 43–61 (2012).

M. Donatelli and S. Serra Capizzano, “On the regularizing power of multigrid-type algorithms,” SIAM J. Sci. Comput. 27, 2053–2076 (2006).
[CrossRef]

M. Donatelli, “A multigrid for image deblurring with Tikhonov regularization,” Numer. Linear Algebra Appl. 12, 715–729 (2005).
[CrossRef]

Donoho, D. L.

D. L. Donoho, “De-noising by soft-thresholding,” IEEE Trans. Inf. Theory 41, 613–627 (1995).
[CrossRef]

Español, M. I.

M. I. Español and M. E. Kilmer, “Multilevel approach for signal restoration problems with Toeplitz matrices,” SIAM J. Sci. Comput. 32, 299–319 (2010).
[CrossRef]

M. I. Español, “Multilevel methods for discrete ill-posed problems: application to deblurring,” Ph.D. thesis (Tufts University, 2009).

Fuhry, M.

M. Fuhry and L. Reichel, “A new Tikhonov regularization method,” Numer. Algorithms 59, 433–445 (2012).
[CrossRef]

Hanke, M.

M. Hanke and C. R. Vogel, “Two-level preconditioners for regularized inverse problems I: theory,” Numer. Math. 83, 385–402 (1999).
[CrossRef]

Hansen, P. C.

P. C. Hansen, “Regularization tools version 4.0 for Matlab 7.3,” Numer. Algorithms 46, 189–194 (2007).
[CrossRef]

P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problem: Numerical Aspects of Linear Inversion (SIAM, 1998).

P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering (SIAM, 2006).

Henson, V. E.

W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed. (SIAM, 2000).

Kaltenbacher, B.

B. Kaltenbacher, “On the regularizing properties of a full multigrid method for ill-posed problems,” Inverse Probl. 17, 767–788 (2001).
[CrossRef]

Kilmer, M. E.

M. I. Español and M. E. Kilmer, “Multilevel approach for signal restoration problems with Toeplitz matrices,” SIAM J. Sci. Comput. 32, 299–319 (2010).
[CrossRef]

Mallat, S.

S. Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, 3rd. ed. (Academic, 1998).

McCormick, S. F.

W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed. (SIAM, 2000).

Morigi, S.

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

Nagy, J. G.

P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering (SIAM, 2006).

O’Leary, D. P.

P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering (SIAM, 2006).

Reichel, L.

M. Fuhry and L. Reichel, “A new Tikhonov regularization method,” Numer. Algorithms 59, 433–445 (2012).
[CrossRef]

L. Reichel and A. Shyshkov, “Cascadic multilevel methods for ill-posed problems,” J. Comput. Appl. Math. 233, 1314–1325 (2010).
[CrossRef]

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

Serra Capizzano, S.

M. Donatelli and S. Serra Capizzano, “On the regularizing power of multigrid-type algorithms,” SIAM J. Sci. Comput. 27, 2053–2076 (2006).
[CrossRef]

Sgallari, F.

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

Shyshkov, A.

L. Reichel and A. Shyshkov, “Cascadic multilevel methods for ill-posed problems,” J. Comput. Appl. Math. 233, 1314–1325 (2010).
[CrossRef]

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

Vogel, C. R.

M. Hanke and C. R. Vogel, “Two-level preconditioners for regularized inverse problems I: theory,” Numer. Math. 83, 385–402 (1999).
[CrossRef]

Wang, Y.

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

Yao, Y.

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

Zhu, W.

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

IEEE Trans. Inf. Theory (1)

D. L. Donoho, “De-noising by soft-thresholding,” IEEE Trans. Inf. Theory 41, 613–627 (1995).
[CrossRef]

IEEE Trans. Med. Imag. (1)

W. Zhu, Y. Wang, Y. Deng, Y. Yao, and R. L. Barbour, “A wavelet-based multiresolution regularized least squares reconstruction approach for optical tomography,” IEEE Trans. Med. Imag. 16, 210–217 (1997).
[CrossRef]

Inverse Probl. (1)

B. Kaltenbacher, “On the regularizing properties of a full multigrid method for ill-posed problems,” Inverse Probl. 17, 767–788 (2001).
[CrossRef]

J. Comput. Appl. Math. (1)

L. Reichel and A. Shyshkov, “Cascadic multilevel methods for ill-posed problems,” J. Comput. Appl. Math. 233, 1314–1325 (2010).
[CrossRef]

Numer. Algorithms (2)

M. Fuhry and L. Reichel, “A new Tikhonov regularization method,” Numer. Algorithms 59, 433–445 (2012).
[CrossRef]

P. C. Hansen, “Regularization tools version 4.0 for Matlab 7.3,” Numer. Algorithms 46, 189–194 (2007).
[CrossRef]

Numer. Linear Algebra Appl. (1)

M. Donatelli, “A multigrid for image deblurring with Tikhonov regularization,” Numer. Linear Algebra Appl. 12, 715–729 (2005).
[CrossRef]

Numer. Math. (1)

M. Hanke and C. R. Vogel, “Two-level preconditioners for regularized inverse problems I: theory,” Numer. Math. 83, 385–402 (1999).
[CrossRef]

Numer. Math. Theory Methods Appl. (1)

M. Donatelli, “An iterative multigrid regularization method for Toeplitz discrete ill-posed problems,” Numer. Math. Theory Methods Appl. 5, 43–61 (2012).

SIAM J. Imaging Sci. (1)

S. Morigi, L. Reichel, F. Sgallari, and A. Shyshkov, “Cascadic multiresolution methods for image deblurring,” SIAM J. Imaging Sci. 1, 51–74 (2008).
[CrossRef]

SIAM J. Sci. Comput. (2)

M. I. Español and M. E. Kilmer, “Multilevel approach for signal restoration problems with Toeplitz matrices,” SIAM J. Sci. Comput. 32, 299–319 (2010).
[CrossRef]

M. Donatelli and S. Serra Capizzano, “On the regularizing power of multigrid-type algorithms,” SIAM J. Sci. Comput. 27, 2053–2076 (2006).
[CrossRef]

Other (5)

W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, 2nd ed. (SIAM, 2000).

P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problem: Numerical Aspects of Linear Inversion (SIAM, 1998).

P. C. Hansen, J. G. Nagy, and D. P. O’Leary, Deblurring Images: Matrices, Spectra, and Filtering (SIAM, 2006).

S. Mallat, A Wavelet Tour of Signal Processing: The Sparse Way, 3rd. ed. (Academic, 1998).

M. I. Español, “Multilevel methods for discrete ill-posed problems: application to deblurring,” Ph.D. thesis (Tufts University, 2009).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Metrics