Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) problem when constraints on the matrix structure need to be imposed. Similar to the ordinary TLS approach, the STLS approach can be used to determine the parameter vector of a linear model, given some noisy measurements. In many signal processing applications, the imposition of this matrix structure constraint is necessary for obtaining Maximum Likelihood (ML) estimates of the parameter vector. In this paper we consider the Toeplitz (Hankel) STLS problem (i.e., an STLS problem in which the Toeplitz (Hankel) structure needs to be preserved). A fast implementation of an algorithm for solving this frequently occurring STLS problem is proposed. The increased efficiency is obtained by exploiting the low displacement rank of the involved matrices and the sparsity of the associated generators. The fast implementation is compared to two other implementations of algorithms for solving the Toeplitz (Hankel) STLS problem. The comparison is carried out on a recently proposed speech compression scheme. The numerical results confirm the high efficiency of the newly proposed fast implementation: the straightforward implementations have a complexity of O((m+n)³) and O(m³) whereas the proposed implementation has a complexity of O(mn+n²). This revised version was published online in June 2006 with corrections to the Cover Date.     

A SUCCESSIVE LEAST SQUARES METHOD FOR STRUCTURED TOTAL LEAST SQUARES

A new method for Total Least Squares (TLS) problems is presented. It differs from previous approaches and is based on the solution of successive Least Squares problems.The method is quite suitable for Structured TLS (STLS) problems. We study mostly the case of Toeplitz matrices in this paper. The numerical tests illustrate that the method converges to the solution fast for Toeplitz STLS problems. Since the method is designed for general TLS problems, other structured problems can be treated similarly.     

On inversion of square matrices partitioned into non-square blocks

Inversion theorems for structured block matrices with non-square blocks are presented. The considered classes contain Toeplitz, Toeplitz plus Hankel and Van der Monde type matrices.     

The structured total least‐squares approach for non‐linearly structured matrices

In this paper, an extension of the structured total least‐squares (STLS) approach for non‐linearly structured matrices is presented in the so‐called ‘Riemannian singular value decomposition’ (RiSVD) framework. It is shown that this type of STLS problem can be solved by solving a set of Riemannian SVD equations. For small perturbations the problem can be reformulated into finding the smallest singular value and the corresponding right singular vector of this Riemannian SVD. A heuristic algorithm is proposed. Some examples of Vandermonde‐type matrices are used to demonstrate the improved accuracy of the obtained parameter estimator when compared to other methods such as least squares (LS) or total least squares (TLS). Copyright © 2002 John Wiley & Sons, Ltd.     

Regularized Total Least Squares Based on Quadratic Eigenvalue Problem Solvers

This paper presents a new computational approach for solving the Regularized Total Least Squares problem. The problem is formulated by adding a quadratic constraint to the Total Least Square minimization problem. Starting from the fact that a quadratically constrained Least Squares problem can be solved via a quadratic eigenvalue problem, an iterative procedure for solving the regularized Total Least Squares problem based on quadratic eigenvalue problems is presented. Discrete ill-posed problems are used as simulation examples in order to numerically validate the method. AMS subject classification (2000) 65F20, 65F30.Received March 2003. Revised November 2003. Accepted January 2004. Communicated by Per Christian Hansen.     

无限广义块Toeplitz和Hankel矩阵求逆的统一方法

利用 Sylvester位移方程的统一办法给出所谓的无限广义块Toeplitz和 Hankel矩阵的求逆公式 .     

TLS问题和LS问题解加权残量的比较

总体最小二乘(TLS)问题和最小二乘(LS)问题解残量的比较已有多篇文献予以探讨.本文对TLS问题和LS问题解的加权残量进行了比较. 导出了TLS解、改进的LS解及普通LS解加权残量之间的误差界. 从而进一步完善了已有的相关结果.     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method

We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.     

Block‐row Hankel weighted low rank approximation

This paper extends the weighted low rank approximation (WLRA) approach to linearly structured matrices. In the case of Hankel matrices with a special block structure, an equivalent unconstrained optimization problem is derived and an algorithm for solving it is proposed. Copyright © 2005 John Wiley & Sons, Ltd.     

Algebras in matrix spaces with displacement structure

We introduce the problem of the location of the algebras contained in a matrix space with displacement structure. We present some partial solutions of the problem that unify and generalize various results obtained so far for the spaces of Toeplitz, Loewner and Toeplitz plus Hankel matrices.     

带多重右边的不定最小二乘问题的条件数

本文研究了带多重右边的不定最小二乘问题的条件数,给出了范数型、混合型及分量型条件数的表达式,同时,也给出了相应的结构条件数的表达式.所考虑的结构矩阵包含Toeplitz 矩阵、Hankel矩阵、对称矩阵、三对角矩阵等线性结构矩阵与Vandermonde矩阵、Cauchy矩阵等非线性结构矩阵.数值例子显示结构条件数总是紧于非结构条件数.     

Averaging operators for exponential splittings

Averaging operations are considered in connection with exponential splitting methods. Toeplitz plus Hankel related matrices are resplit by applying appropriate averaging operators leading to a hierarchy of structured matrices. With the resulting parts, the option of using exponential splitting methods becomes available. A related, seemingly important group of unitary unipotents is looked at. Based on a formula due to Lenard, a very fast iterative method to find the nearest Toeplitz plus Hankel matrix in the Frobenius norm is devised.     

Fast deconvolution with approximated PSF by RSTLS with antireflective boundary conditions

The problem of reconstructing signals and images from degraded ones is considered in this paper. The latter problem is formulated as a linear system whose coefficient matrix models the unknown point spread function and the right hand side represents the observed image. Moreover, the coefficient matrix is very ill-conditioned, requiring an additional regularization term. Different boundary conditions can be proposed. In this paper antireflective boundary conditions are considered. Since both sides of the linear system have uncertainties and the coefficient matrix is highly structured, the Regularized Structured Total Least Squares approach seems to be the more appropriate one to compute an approximation of the true signal/image. With the latter approach the original problem is formulated as an highly nonconvex one, and seldom can the global minimum be computed. It is shown that Regularized Structured Total Least Squares problems for antireflective boundary conditions can be decomposed into single variable subproblems by a discrete sine transform. Such subproblems are then transformed into one-dimensional unimodal real-valued minimization problems which can be solved globally. Some numerical examples show the effectiveness of the proposed approach.     

Kernel structure of Toeplitz-plus-Hankel matrices

The structure of the kernel of block Toeplitz-plus-Hankel matrices R=[a_j−k+b_j+k], where a_j and b_j are the given p×q blocks with entries from a given field, is investigated. It is shown that R corresponds to two systems of at most p+q vector polynomials from which a basis of the kernel of R and all other Toeplitz-plus-Hankel matrices with the same parameters a_j and b_j can be built. The main result is an analogue of a known kernel structure theorem for block Toeplitz and block Hankel matrices.     

On two particular cases of solving the normal Hankel problem

The normal Hankel problem is one of characterizing all the complex matrices that are normal and Hankel at the same time. The matrix classes that can contain normal Hankel matrices admit a parameterization by real 2 × 2 matrices with determinant one. Here, the normal Hankel problem is solved in the case where the characteristic matrix of a given class is an order two Jordan block for the eigenvalue 1 or ?1.     

Some results on condition numbers of the scaled total least squares problem

Under the Golub-Van Loan condition for the existence and uniqueness of the scaled total least squares (STLS) solution, a first order perturbation estimate for the STLS solution and upper bounds for condition numbers of a STLS problem have been derived by Zhou et al. recently. In this paper, a different perturbation analysis approach for the STLS solution is presented. The analyticity of the solution to the perturbed STLS problem is explored and a new expression for the first order perturbation estimate is derived. Based on this perturbation estimate, for some STLS problems with linear structure we further study the structured condition numbers and derive estimates for them. Numerical experiments show that the structured condition numbers can be markedly less than their unstructured counterparts.     

On the skew-symmetric part of the Toeplitz component in the real normal (<Emphasis Type="Italic">T</Emphasis> + <Emphasis Type="Italic">H</Emphasis>)-problem

The real normal Toeplitz-plus-Hankel problem is to characterize the matrices that can be represented as sums of two real matrices of which one is Toeplitz and the other Hankel. For a matrix of this type, relations are found between the skew-symmetric part of the Toeplitz component and the matrix obtained by reversing the order of columns in the Hankel component.     

Perturbation analysis and condition numbers of scaled total least squares problems

The standard approaches to solving an overdetermined linear system Ax ≈ b find minimal corrections to the vector b and/or the matrix A such that the corrected system is consistent, such as the least squares (LS), the data least squares (DLS) and the total least squares (TLS). The scaled total least squares (STLS) method unifies the LS, DLS and TLS methods. The classical normwise condition numbers for the LS problem have been widely studied. However, there are no such similar results for the TLS and the STLS problems. In this paper, we first present a perturbation analysis of the STLS problem, which is a generalization of the TLS problem, and give a normwise condition number for the STLS problem. Different from normwise condition numbers, which measure the sizes of both input perturbations and output errors using some norms, componentwise condition numbers take into account the relation of each data component, and possible data sparsity. Then in this paper we give explicit expressions for the estimates of the mixed and componentwise condition numbers for the STLS problem. Since the TLS problem is a special case of the STLS problem, the condition numbers for the TLS problem follow immediately from our STLS results. All the discussions in this paper are under the Golub-Van Loan condition for the existence and uniqueness of the STLS solution. Yimin Wei is supported by the National Natural Science Foundation of China under grant 10871051, Shanghai Science & Technology Committee under grant 08DZ2271900 and Shanghai Education Committee under grant 08SG01. Sanzheng Qiao is partially supported by Shanghai Key Laboratory of Contemporary Applied Mathematics of Fudan University during his visiting.     

Condition Numbers for Structured Least Squares Problems

This paper studies the normwise perturbation theory for structured least squares problems. The structures under investigation are symmetric, persymmetric, skewsymmetric, Toeplitz and Hankel. We present the condition numbers for structured least squares. AMS subject classification (2000) 15A18, 65F20, 65F25, 65F50