Structured total least norm method for Toeplitz problems

The total least squares (TLS) method for solving an overdetermined system Ax≈b is a generalization of the least squares (LS) method, and it minimizes ||[E|r]||_F so that (b+r)∈Range(A+E), given A∈R^mxn, with m⩾n and b∈R^m×1 . The commonly used TLS algorithm is based on the singular value decomposition (SVD) of [A|b]. However, in applications where the matrix A has a special structure, the SVD based methods may not always be appropriate, since they do not preserve the structure. A new formulation, called the structured total least norm (STLN), and an algorithm for computing solutions have been developed. The STLN preserves any affine structure of A or [A|b], and can minimize error in the discrete L_p norm, where p=1, 2 or ∞. We study the STLN method for problems in which the perturbation matrix E or [E|r] keeps the Toeplitz structure like the data matrix A or [A|b]. These structures occur in many problems such as deconvolution, transfer function modeling and linear prediction problems. In particular, the STLN methods with L₁ and L₂ norms are compared with the LS and TLS methods and shown to improve the accuracy of the solutions significantly. When there is an outlier in the data, the STLN method with L₁ norm is shown to produce solutions that are essentially not affected by the outlier