M.Sc Student | Hershkovitz Oz |
---|---|

Subject | The Modified Structured Total Least Squares Problem |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Amir Beck |

Full Thesis text |

Consider an overdetermined system *Ax **≈ b*, where both the model matrix *A* in *R*^{m×n} and the righthand side
vector *b* in *R*^{m} 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 ║*E*║^{2} + ║*w*║^{2}
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.