Algorithms And Implementations Of Toeplitz Matrix Reconstruction

The study of matrix reconstruction has aroused great interest in recent years, which mainly involves the problem of matrix completion and matrix recovery. There are rich results in both theoretical analysis, algorithms design and applications for the study of matrix reconstruction. However, the sampling matrix often has a special structure, such as a Toeplitz structure. Meanwhile, as an important special matrix, Toeplitz matrices play an important role in signal and image processing which has drawn a large number of researchers.During the study of matrix completion and matrix recovery, we discover that most of the algorithms are based on singular value decomposition of which the algorithm com-plexity is O(n3). Through numerical experiments we obtain that it is time-consuming to compute the singular value decomposition. Therefore, we take full advantage of the fast singular value decomposition algorithm of Toeplitz matrices, of which the algorithm complexity is O(n2 log n). In the aspect of Toeplitz matrix completion, we put forward a new structure-preserving algorithm, combining singular value thresholding operator and a quadratic programming technique, a new mean value algorithm based on the singular value thresholding algorithm and a modified augmented Lagrange multiplier method for matrix completion, respectively. Meanwhile, we discuss the convergence of the new algorithms respectively. And we show the new algorithms are much more effective through numerical experiments. For the Toeplitz matrix recovery problem, we propose a mean Value algorithm, combining alternating iterative method and singular value thresholding operator, four modified augmented Lagrange multiplier algorithms. And we prove the convergence of the new algorithms respectively. Through experimen-tal results, We show our algorithms for Toeplitz matrix completion and recovery are advantageous over the original algorithms on the time of SVD time as well as the CPU time that will be benefit to solve large-scale Toeplitz matrix reconstruction problem. Furthermore, it can be time saving and cost reducing in practical applications.