In many practical applications, the structure of covariance matrix is often
blurred due to random errors, making the estimation of covariance matrix very
difficult particularly for high-dimensional data. In this article, we propose a regularization method for finding a possible banded Toeplitz structure for a given covariance matrix A (e.g., sample covariance matrix), which is usually an estimator of the unknown population covariance matrix S. We aim to find a matrix, say B, which is of banded Toeplitz structure, such that the Frobenius-norm discrepancy between B and A achieves the smallest in the whole class of banded Toeplitz structure matrices. As a result, the obtained Toeplitz structured matrix B recoveries the underlying structure behind S. Our simulation studies show that B is also more accurate than the sample covariance matrix A when estimating the covariance matrix S that has a banded Toeplitz structure. The studies also show that the proposed method works very well in regularization of covariance structure.