Toeplitz matrix completion via a low-rank approximation algorithm
Tóm tắt
In this paper, we propose a low-rank matrix approximation algorithm for solving the Toeplitz matrix completion (TMC) problem. The approximation matrix was obtained by the mean projection operator on the set of feasible Toeplitz matrices for every iteration step. Thus, the sequence of the feasible Toeplitz matrices generated by iteration is of Toeplitz structure throughout the process, which reduces the computational time of the singular value decomposition (SVD) and approximates well the solution. On the theoretical side, we provide a convergence analysis to show that the matrix sequences of iterates converge. On the practical side, we report the numerical results to show that the new algorithm is more effective than the other algorithms for the TMC problem.
Tài liệu tham khảo
Amit, Y., Fink, M., Srebro, N., Ullman, S.: Uncovering shared structures in multiclass classification. In: Processings of the 24th International Conference on Machine Learning, pp. 17–24. ACM, New York (2007)
Argyriou, A., Evgeniou, T., Pontil, M.: Multi-task feature learning. Adv. Neural Inf. Process. Syst. 19, 41–48 (2007)
Bajwa, W.U., Haupt, J.D., Raz, G.M., Wright, S.J., Nowak, R.D.: Toeplitz-structures compressed sensing matrices. In: IEEE/SP 14th Workshop on Statistical Signal Processing, SSP’07, pp. 294–298 (2007)
Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.: Image inpainting. Comput. Graph. 34, 417–424 (2000)
Boumal, N., Absil, P.A.: RTRMC: a Riemannian trust-region method for low-rank matrix completion. Adv. Neural Inf. Process. Syst. 24, 406–414 (2011)
Cai, J.F., Liu, S., Xu, W.: A fast algorithm for reconstruction of spectrally sparse signals in super-resolution. In: Wavelets and Sparsity XVI. Proceedings of SPIE, vol. 9597. SPIE, Bellingham (2015)
Cai, J.F., Qu, X., Xu, W., Ye, G.B.: Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction. Appl. Comput. Harmon. Anal. 41(2), 470–490 (2016)
Cai, J.F., Wang, T., Wei, K.: Spectral compressed sensing via projected gradient descent. SIAM J. Optim. 28(3), 2625–2653 (2018)
Cai, J.F., Wang, T., Wei, K.: Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion. Appl. Comput. Harmon. Anal. 46(1), 94–121 (2019)
Chen, Y., Chi, Y.: Robust spectral compressed sensing via structured matrix completion. IEEE Trans. Inf. Theory 60(10), 6576–6601 (2014)
Fazel, M., Pong, T.K., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34, 946–977 (2013)
Fu, Y.R., Wang, C.L.: A modified orthogonal rank-one matrix pursuit for Toeplitz matrix completion. Far East J. Appl. Math. 95, 411–428 (2016)
Golub, G.H., VanLoan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)
Gutiérrez-Gutiérrez, J., Crespo, P.M., Böttcher, A.: Functions of banded Hermitian block Toeplitz matrices in signal processing. Linear Algebra Appl. 422, 788–807 (2007)
Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 665–674 (2013)
Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. Technical report, Stanford University (2009)
Liu, Z., Vandenberghe, L.: Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31, 1235–1256 (2009)
Lu, Z., Zhang, Y., Li, X.: Penalty decomposition methods for rank minimization. Optim. Methods Softw. 30(3), 531–558 (2015)
Luk, F.T., Qiao, S.Z.: A fast singular value algorithm for Hankel matrices. In: Olshevsky, V. (ed.) Fast Algorithms for Structured Matrices: Theory and Applications. Contemporary Mathematics, vol. 323. Am. Math. Soc., Providence (2003)
Mesbahi, M., Papavassilopoulos, G.P.: On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Trans. Autom. Control 42, 239–243 (1997)
Mishra, B., Apuroop, K.A., Sepulchre, R.: A Riemannian geometry for low-rank matrix completion (2012). arXiv:1211.1550
Pati, Y.C., Rezaiifar, R., Rezaiifar, Y.C.P.R., Krishnaprasad, P.S.: Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition. In: Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, pp. 40–44 (1993)
Sebert, F., Zou, Y.M., Ying, L.: Toeplitz block matrices in compressed sensing and their applications in imaging. In: International Conference on Information Technology and Applications in Biomedicine, pp. 47–50 (2008). https://doi.org/10.1109/ITAB.2008.4570587
Shaw, A.K., Pokala, S., Kumaresan, R.: Toeplitz and Hankel approximation using structured approach. In: Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 12–15 (1998)
Suffridge, T.J., Hayden, T.L.: Approximation by a Hermitian positive semidefinite Toeplitz matrix. SIAM J. Matrix Anal. Appl. 14(3), 721–734 (1993)
Tanner, J., Wei, K.: Low rank matrix completion by alternating steepest descent methods. Appl. Comput. Harmon. Anal. 40, 417–429 (2016)
Vandereycken, B.: Low rank matrix completion by Riemannian optimization. SIAM J. Optim. 23, 1214–1236 (2013)
VanLoan, C.F.: Computational Frameworks for the Fast Fourier Transform. SIAM, Philadelphia (1992)
Wang, C.L., Li, C.: A mean value algorithm for Toeplitz matrix completion. Appl. Math. Lett. 41, 35–40 (2015)
Wang, C.L., Li, C.: A structure-preserving algorithm for Toeplitz matrix completion. Sci. Sin., Math. 46, 1191–1206 (2016) (in Chinese)
Wang, C.L., Li, C., Wang, J.: A modified augmented Lagrange multiplier algorithm for Toeplitz matrix completion. Adv. Comput. Math. 42, 1209–1224 (2016)
Wang, C.L., Li, C., Wang, J.: Optimal low-rank matrix approximation algorithms for matrix completion. Appl. Math. Comput. (under revision)
Wang, Z., Lai, M.J., Lu, Z.S., Fan, W., Davulcu, H., Ye, J.-P.: Orthogonal rank-one matrix pursuit for low rank matrix completion. SIAM J. Sci. Comput. 37, A488–A514 (2015)
Wen, R.P., Li, S.Z.: An ℓ-step modified augmented Lagrange multiplier algorithm for completing a Toeplitz matrix. Math. Appl. 32(4), 887–899 (2019)
Wen, R.P., Li, S.Z., Duan, Y.H.: Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm. Appl. Math. Comput. 355, 299–310 (2019)
Wen, R.P., Li, S.Z., Zhou, F.: A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion. J. Inequal. Appl. 2019, Article ID 83 (2019)
Wen, R.P., Liu, L.X.: The two-stage iteration algorithms based on the shortest distance for low-rank completion. Appl. Math. Comput. 314, 133–141 (2017)
Wen, Z.W., Yin, W.T., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm. Math. Program. Comput. 4, 333–361 (2012)
Xu, W., Qiao, S.Z.: A fast SVD algorithm for square Hankel matrices. Linear Algebra Appl. 428, 550–563 (2008)
Ying, J., Lu, H., Wei, Q., Cai, J.F., Guo, D., Wu, J., Chen, Z., Qu, X.: Hankel matrix nuclear norm regularized tensor completion for n-dimensional exponential signal. IEEE Trans. Signal Process. 65, 3702–3717 (2017)