The structured total least squares (TLS) problem has been introduced by [4,5] for solving overdetermined linear systems in which both the coefficient matrix A,   A Î R^{m ×n},m >> n, and the right-hand side b Î R^m, are structured and corrupted by noise.

The problem can be formulated as the following constrained optimization problem

This natural extension of the TLS problem is a lot more difficult to solve than the TLS problem, because of its highly nonlinear nature and the existence of many local minima. We focus here on the frequently occurring cases where either [A  |  b] is a Toeplitz matrix or A a Toeplitz matrix and b unstructured.

The structured TLS problem is solved in an iterative fashion, in which, at each iteration, a Least Squares problem involving a rectangular Toeplitz-block matrix needs to be solved. The latter kernel problem is solved in O(mn) flops, via a fast and stable QR decomposition based on the displacement rank representation of the involved Toeplitz-block matrices. The efficiency, which is higher than that of other existing algorithms, results from the low displacement rank and the exploitation of the sparsity of the generators.

We extend this fast algorithm for ill-posed problems by adding regularization and apply the resulting algorithm on a medical application in renography [2], to illustrate the increased computational efficiency and accuracy.

References.

[1] P. Lemmerling, N. Mastronardi and S. Van Huffel , Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem, Numerical Algorithms, 23 (2000) pp. 371-392.

[2] N. Mastronardi, P. Lemmerling and S. Van Huffel Fast structured Total Least Squares algorithm for solving the basic deconvolution problem, SIAM J. Matrix Anal. Appl., Vol. 22, No. 2 (2000), pp. 553-553.

[3] N. Mastronardi, P. Van Dooren, and S. Van Huffel, On the stability of the generalized Schur algorithm, In: Numerical Analysis and Its Applications, Proceedings of the Second International conference, NAA 2000, Rousse, Bulgaria, June 11-15, 2000, published as Lecture Notes in Computer Science 1988, L. Vulkov, J. Wa\'sniewski, P. Yalamov (Eds.), Springer-Verlag, Berlin Heidelberg, 2001, pp.560-567.

[4] J. B. Rosen, H. Park and J. Glick, Total least norm formulation and solution for structured problems, SIAM J. Matrix Anal. Appl., Vol. 17, No. 1 (1996), pp. 110-126.

[5] S. Van Huffel, H. Park and J. Ben Rosen, Formulation and Solution of Structured Total Least Norm Problems for Parameter Estimation, IEEE Trans. on Signal Processing, SP-44, no. 10 (1996), pp. 2464-2474.

Footnotes:

¹ Joint work with Philippe LEMMERLING and Sabine Van HUFFEL.