Given two n×n Toeplitz matrices T 1 and T 2, and a vector b∈R n(2), consider the linear system Ax = b-η, where η∈R n(2) is an unknown vector representing the noise and A = T 1⊗T 2. Recovering approximations of x, given A and b, is encountered in image restoration problems. We propose a method for the approximation of the solution x that has good regularization properties. The algorithm is based on a modified version of Newton's iteration for matrix inversion and relies on the concept of approximate displacement rank. We provide a formal description of the regularization properties of Newton's iteration in terms of filters and determine bounds to the number of iterations that guarantee regularization. The method is extended to deal with more general systems where A = ∑ i = 1 hT 1 (i)⊗T 2 (i). The cost of computing regularized inverses is O(n log n) operations (ops), the cost of solving the system Ax = b is O(n 2 log n) ops. Numerical experiments which show the effectiveness of our algorithm are presented.

On the regularized solution of block banded block Toeplitz systems

BINI, DARIO ANDREA;MEINI, BEATRICE
2000

Abstract

Given two n×n Toeplitz matrices T 1 and T 2, and a vector b∈R n(2), consider the linear system Ax = b-η, where η∈R n(2) is an unknown vector representing the noise and A = T 1⊗T 2. Recovering approximations of x, given A and b, is encountered in image restoration problems. We propose a method for the approximation of the solution x that has good regularization properties. The algorithm is based on a modified version of Newton's iteration for matrix inversion and relies on the concept of approximate displacement rank. We provide a formal description of the regularization properties of Newton's iteration in terms of filters and determine bounds to the number of iterations that guarantee regularization. The method is extended to deal with more general systems where A = ∑ i = 1 hT 1 (i)⊗T 2 (i). The cost of computing regularized inverses is O(n log n) operations (ops), the cost of solving the system Ax = b is O(n 2 log n) ops. Numerical experiments which show the effectiveness of our algorithm are presented.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/204909
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact