Total Least Norm Formulation and Solution for Structured Problems

A new formulation and algorithm is described for computing the solution to an overdetermined linear system, $Ax \approx b$, with possible errors in both A and b. This approach preserves any affine structure of A or $[ A\mid b ]$, such as Toeplitz or sparse structure, and minimizes a measure of error in the discrete $L_p $ norm, where $p = 1,2,\,{\text{or}}\,\infty $. It can be considered as a generalization of total least squares and we call it structured total least norm (STLN). The STLN problem is formulated, the algorithm for its solution is presented and analyzed, and computational results that illustrate the algorithm convergence and performance on a variety of structured problems are summarized. For each test problem, the solutions obtained by least squares, total least squares, and STLN with $p = 1,2,\,{\text{and}}\,\infty $ were compared. These results confirm that the STLN algorithm is an effective method for solving problems where A or b has a special structure or where errors can occur in only some of the elements of A and b.