An Inner-Outer Iteration Algorithm for Completing a Toeplitz Matrix

Rui-Ping Wen; Liang Zhang; Jin-Rui Guan; Zubair Ahmed Kalhoro; Hamadullah Bhutto

Author(s)

Rui-Ping Wen Shanxi Key Lab for Intelligent Optimization Computing & Block-chain Technology, School of Mathematics & Statistics, Taiyuan Normal University,Jinzhong 030619,China

Liang Zhang Shanxi Key Lab for Intelligent Optimization Computing & Block-chain Technology, School of Mathematics & Statistics, Taiyuan Normal University,Jinzhong 030619,China

Jin-Rui Guan Shanxi Key Lab for Intelligent Optimization Computing & Block-chain Technology, School of Mathematics & Statistics, Taiyuan Normal University,Jinzhong 030619,China

Zubair Ahmed Kalhoro Institute of Mathematics & Computer Science, University of Sindh, Allama I.I. Kazi Campus, Jamshoro 76080, Pakistan

Hamadullah Bhutto Institute of Mathematics & Computer Science, University of Sindh, Jamshoro 76060, Pakistan

Abstract

This study proposes a faster inner-outer iteration algorithm based on the Modified Augmented Lagrange Multiplier (MALM) algorithm for Toeplitz matrix completion introduced in (Wang et al., 2016a), to alleviate the intensive computation burden due to memory traffic and data exchange. In short, with this new inner-outer framework, the optimization process is partitioned. It takes several iterations of inner Singular Value Decomposition (SVD) truncation for fine-tuning the low-rank approximation and then performs a single outer Toeplitzstructure smoothing projection. Consequently, separating these steps reduces unnecessary data transfer through the computer's memory system. In addition, we prove rigorously that the sequence generated by this algorithm globally converges to the optimal solution of the convex programming model, provided that the penalty parameters are set as standard ones which are non-decreasing. In order to ensure the statistical significance of our results, numerical simulations were conducted for a total of 50 different runs, with matrix sizes from n = 500 to n = 8000 and sampling rates between p = 0.3 and p = 0.6. We have found that this new algorithm yields significant computational savings in comparison with the traditional MALM algorithm. It reduces the overall CPU time of execution by up to 55% (runtime ratios range from 45% to 91% of the original MALM), especially in the most challenging and low sampling density cases.

Publication Details

Page(s) 148-161

DOI DOI not available

Published Journal: The Sciencetech, Volume: 7, Issue: 2, Year: 2026

Request the full text from PASTIC

Keywords

Augmented Lagrange Multiplier Method, Toeplitz Matrix, Matrix Completion, Inner-Outer Iteration

References

Amit Y.,Fink M.,Srebro N.,Ullman S. .2007 .Uncovering shared structures in multiclass classification. In Proceedings of the 24th international conference on Machine learning, : 17-24.

Argyriou A.,Evgeniou T.,Pontil M. .2006 .Multi-task feature learning. Advances in neural information processing systems, 19 : .

Bennett J.,Lanning S. .2007 .The netflix prize. In Proceedings of KDD cup and workshop, : 35.

Bertalmio M.,Sapiro G.,Caselles V.,Ballester C. .2000 .Image inpainting. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, : 417-424.

Cai H.,Kundu C.,Liu J.,Yin W. .2026 .Deeply learned robust matrix completion for large-scale low-rank data recovery. IEEE Transactions on Pattern Analysis and Machine Intelligence., : .

Cai J. F.,Candès E. J.,Shen Z. .2010 .A singular value thresholding algorithm for matrix completion. SIAM Journal on optimization, 20(4) : 1956-1982.

Candes E.,Recht B. .2012 .Exact matrix completion via convex optimization. Communications of the ACM, 55(6) : 111-119.

Chawin D.,Haviv I. .2025 .New hardness results for low-rank matrix completion. arXiv preprint arXiv:2506, : 18440.

Fu Y.,Jiang X.,Zheng Y.,Jiang Z. .2025 .Two fast algorithms for finding the solution of the lower Hessenberg quasi-Toeplitz linear system from Markov chain. Scientific reports, 15(1) : 21763.

Li H.,Peng Z.,Pan C.,Zhao D. .2023 .Fast gradient method for lowrank matrix estimation. Journal of Scientific Computing, 96(2) : 41.

Li N.,He L.,Meng C.,Tu Q. .2025 .Low-Rank Matrix Completion via Nonconvex Rank Approximation for IoT Network Localization. , 14(19) : 3920.

Lin Z.,Chen M.,Ma Y. .2010 .The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv preprint arXiv:1009, : 5055.

Mesbahi M.,Papavassilopoulos G. P. .1997 .On the rank minimization problem over a positive semidefinite linear matrix inequality. IEEE Transactions on Automatic Control, 42(2) : 239-243.

Shi Q.,Yin J.,Cai J.,Cichocki A.,Yokota T.,Chen L.,Zeng J. .2020 .Block Hankel tensor ARIMA for multiple short time series forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence, 04 : 5758-5766.

Tomasi C.,Kanade T. .1992 .Shape and motion from image streams under orthography: a factorization method. International journal of computer vision, 9(2) : 137-154.

Wen Y. W.,Li K.,Chen H. .2023 .Accelerated matrix completion algorithm using continuation strategy and randomized SVD. Journal of Computational and Applied Mathematics, 429 : 115215.

Wang C.,Guo J. .2026 .Fast Algorithm for Toeplitz Matrix Recovery via a Hybrid Thresholding Operator. Acta Mathematicae Applicatae Sinica, English Series, 42(2) : 436-449.

Xue J.,Zhao Y. Q.,Wu T.,Chan J. C. W. .2024 .Tensor convolutionlike low-rank dictionary for high-dimensional image representation. IEEE Transactions on Circuits and Systems for Video Technology, 34(12) : 13257-13270.