Optimization Theory

The Total Least Squares (TLS) problem is a well known technique for solving the following over-determined linear systems of equations $$Ax\approx bA\in {\mathbb{R}}^{m\times n},b\in \mathbb{R},m>n$$

in which both the matrix $A$ and the right hand side $b$ are affected by errors. We consider the following classical definition of TLS problem.The Total Least Squares problem with data $A\in {\mathbb{R}}^{m\times n}$ and $b\in {\mathbb{R}}^m,m>n$ is given by, $$\begin{array}{r}min|E\mid f{|}_F\text{subject to}b+f\in \text{Im}(A+E)\end{array}$$

where $E\in {\mathbb{R}}^{m\times n}$ and $f\in {\mathbb{R}}^m$. Here, $|E\mid f{|}_F$ denotes the Frobenius matrix norm and $(E\mid f)$ denotes the $m\times (n+1)$ matrix whose first $n$ columns are the columns of $E$, and the In various engineering and statistics applications where a mathematical model reduces to the solution of an over-determined, possibly inconsistent linear equation $Ax\approx b$, solving that equation in the TLS sense yields a more convenient approach than the ordinary least squares approach, in which the data matrix is assumed constant and errors are considered right-hand side $b$. In this project, we derived a iterative algorithm (see Algorithm 1 above) for solving Total Least Square problem based on randomized projection.