The authors develop a method to solve the structured total least squares problem \(Ax = b\) for \(A\) with a block circulant structure of \(N\) blocks. The key is the use of the discrete Fourier transform to decompose the structured problem into \(N\) unstructured total least squares problems. These \(N\) problems can then be solved via the singular value decomposition, see G. H. Golub and C. F. van Loan [SIAM J. Numer. Anal. 17, 883–893 (1980; Zbl 0468.65011)], and the inverse discrete Fourier transform finally gives the structured total least squares solution.
In both the structured and unstructured cases, the total least squares problem is a global optimization problem. The total least squares problem is convex for structured matrices and their allowed perturbations and it is nonconvex for unstructured matrices, making global optimization for the structured total least squares problem almost impossible by standard means. Previous algorithms for the structured total least squares problem have had difficulties with finding the global minimum that the proposed algorithm finds easily.