Fast Structured Total Least Squares Algorithms via Exploitation of the Displacement Structure

Nicola Mastronardi (), Philippe Lemmerling () and Sabine Van Huffel ()
Additional contact information
Nicola Mastronardi: K. U.Leuven, Department of Computer Science
Philippe Lemmerling: ESAT-SISTA, K. U.Leuven
Sabine Van Huffel: ESAT-SISTA, K. U.Leuven

A chapter in Total Least Squares and Errors-in-Variables Modeling, 2002, pp 93-106 from Springer

Abstract: Abstract 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 $$ \begin{gathered} \mathop {\min ||\left[ {\Delta A\Delta b} \right]|{|_F}}\limits_{\Delta A,\Delta b,x} \hfill \\ SUCHTHAT\left( {A + \Delta A} \right)x = b + \Delta b \hfill \\ and\left( {\Delta A\Delta B} \right)hasthesamestructureas\left[ {AB} \right]. \hfill \\ \end{gathered} $$ 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 Karush-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 are 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.

Keywords: Hankel/Toeplitz matrix; structured total least squares; displacement rank (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-94-017-3552-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9789401735520

DOI: 10.1007/978-94-017-3552-0_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().