Fast structured total least squares algorithms via exploitation of the displacement structure

We present fast algorithms and their stability properties for Toeplitz structured total least squares (STLS) problems. The STLS problem can be formulated as the following constrained optimization problem min(DeltaA,Deltab,x) parallel to[DeltaA Deltab]parallel to(F) such that (A + DeltaA)x = b + Deltab and [DeltaA Deltab] has the same structure as [A b]. This natural extension of the TLS problem is clearly 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 case where [A b] is a Toeplitz matrix. The problem is solved in an iterative fashion, in which at each iteration the Kaxush-Kuhn-Tucker (KKT) equations of the locally linearized problem have to be solved. For this kernel routine we use a generalized Schur decomposition algorithm based on the low displacement rank of the KKT system matrix. By exploiting the sparsity of the associated generators, we obtain a fast algorithm that requires O(mn + n(2)) flops per iteration, where m and n axe the number of rows and the number of columns of A, respectively. We also prove the stability of the latter kernel routine. The efficiency of the proposed fast implementation is compared to the efficiency of the straightforward implementation, which does not exploit the structure of the involved matrices. The comparison is done on a recently introduced speech compression scheme in which the considered STLS problem constitutes one of the kernel problems. The numerical results confirm the high efficiency of the newly proposed fast implementation.