M.Sc Thesis
M.Sc Student Hershkovitz Oz The Modified Structured Total Least Squares Problem Department of Industrial Engineering and Management Professor Amir Beck

Abstract

Consider an overdetermined system Ax b, where both the model matrix A in Rm×n and the righthand side vector b in Rm are subjected to noise. The total least squares (TLS) approach to this problem is to seek a perturbation matrix E and a perturbation vector w that minimize E2 + w2 subject to the consistency equation (A + E)x = b + w. When the model matrix has a linear structure, the problem is called the structured total least squares (STLS) problem. In contrast to the TLS problem for which a solution can be found efficiently, the STLS problem is nonconvex and as a result finding its solution is in general a difficult task.

In the first part of the work we provide a self-contained review of the known results on the TLS and STLS from an optimization point of view. These derivations from basic optimization principles are different from those available in the literature which relies on advanced linear algebra topics. We then review and empirically compare different approaches for solving the nonconvex STLS problem such as STLN and other methods based on general purpose optimization algorithms.

The main contribution of the work is in introducing and analyzing a new estimate called the modified structured total least squares (MSTLS) which is related to the STLS solution in two aspects (thus its name). First, both the STLS and MSTLS are maximum-likelihood estimates under suitable normality conditions, but from different interpretations. Second, the resulting optimization problems are very similar. We also study a specific structure where the perturbation matrix is of the form DEC (E is unknown and D,C are known). This kind of structure arises in many cases, one of them is when only few of the rows or columns of A are contaminated by noise. For this structure we provide a more efficient solution algorithm based on converting the problem into an univariate optimization problem and prove that in some cases the univariate function is unimodal, thus showing that the problem can be solved efficiently and globally. Numerical results illustrate the attractiveness of the MSTLS over the STLS method.