×

Matrix completion with \(\varepsilon\)-algorithm. In memory of Peter Wynn (1931–2017). (English) Zbl 1405.65004

Summary: We show in this paper how the convergence of an algorithm for matrix completion can be significantly improved by applying Wynn’s \(\varepsilon\)-algorithm. Straightforward generalization of the scalar \(\varepsilon\)-algorithm to matrices fails. However, accelerating the convergence of only the missing matrix elements turns out to be very successful.

MSC:

65B05 Extrapolation to the limit, deferred corrections
15A83 Matrix completion problems
65F10 Iterative numerical methods for linear systems

Biographic References:

Wynn, Peter

Software:

EPSfun; Maple; Matlab
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brezinski, C.: Accélération de la Convergence en Analyse Numérique. Lecture Notes in Mathematics, p 584. Springer, Berlin (1977) · Zbl 0352.65003
[2] Brezinski, C.: Généralisations de la transformation de Shanks, de la table de Padé et de l’e-algorithme. Calcolo 12, 317-360 (1975) · Zbl 0329.65006
[3] Brezinski, C., Redivo-Zaglia, M.: The simplified topological epsilon-algorithms for accelerating sequences in a vector space. SIAM J. Sci. Comput. 36, A2227-A2247 (2014) · Zbl 1308.65006
[4] Brezinski, C., Redivo-Zaglia, M.: The simplified topological epsilon-algorithms: software and applications. Numer. Algorithms 74, 1237-1260 (2017) · Zbl 1362.65004
[5] Brezinski, C., Redivo-Zaglia, M.: The genesis and early developments of Aitken’s process, Shanks’ transformation, the e-algorithm, and related fixed point methods. Numer. Algorithms, this issue · Zbl 1477.65011
[6] Candès, E. J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717-772 (2009) · Zbl 1219.90124
[7] Gander, W, Gander, M.J., Kwok, F.: Scientific Computing, an Introduction Using Maple and Matlab. Springer, Berlin (2014) · Zbl 1296.65001
[8] McLeod, JB: A note on the e-algorithm. Computing 7(1-2), 17-24 (1971) · Zbl 0219.65094
[9] Sidi A: Vector extrapolation methods with applications. Number 17 in SIAM series on Computational Science and Engineering. SIAM (2017) · Zbl 1383.65002
[10] Shanks, D: Non-linear transformation of divergent and slowly convergent sequences. J. Math. Phys. 34, 1-42 (1955) · Zbl 0067.28602
[11] Shi Q, Lu, H, Cheung Y-M: Rank-one matrix completion with automatic rank estimation via L1-norm regularization. IEEE Trans. Neural Netw. Learn Syst. PP(99), 1-14 (2017). https://doi.org/10.1109/TNNLS.2017.2766160. In press
[12] Wynn, P.: On a device for computing the em(Sn)-transformation. MTAC 10, 91-96 (1956) · Zbl 0074.04601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.