An Inner-Outer Iteration Algorithm for Completing a Toeplitz Matrix

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 Toeplitz-structure 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.