Projected Landweber iteration for matrix completion. (English) Zbl 1225.65049

Let \(M\in\mathbb{R}^{n\times m}\) be an unknown low-rank matrix and \(\{M_{ij}:\;(i,j)\in\Omega\}\) be a sampling set of its entries, and let \(\|\cdot \|_F\), \(\|\cdot\|_*\) be the Frobenius norm and the nuclear norm on \(\mathbb{R}^{n\times m}\), respectively. The authors derive a nonlinear constrained quadratic programming problem: \(\min\{\|\mathcal{P}_\Omega(X)-\mathcal{P}_\Omega(M)\|_F^2:\;X\in \bar{B}_R\}\), where \(\mathcal{P}_\Omega\) is the orthogonal projector such that \(\mathcal{P}_\Omega(X)_{ij}=M_{ij}\) when \((i,j)\in\Omega\) and otherwise equals to zero, and the level set \(\bar{B}_R=\{X\in\mathbb{R}^{n\times m}: \|X\|_*\leq R\}\). They design a new algorithm for addressing such a matrix completion problem, namely projected Landweber iteration, based on the projected method and Landweber iteration. The convergence of the proposed algorithm is proved strictly, and numerical results show that the proposed algorithm can be fast and efficient under suitable prior conditions of \(M\).


65F30 Other matrix algorithms (MSC2010)
15A83 Matrix completion problems
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
Full Text: DOI


[3] Trosset, M. W., Distance matrix completion by numerical optimization, Comput. Optim. Appl., 17, 11-22 (2000) · Zbl 0964.65047
[5] Candès, E.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2008) · Zbl 1219.90124
[7] Liu, Z.; Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 3, 1235-1256 (2009) · Zbl 1201.90151
[8] Goldberg, K.; Roeder, T.; Gupta, D.; Perkins, C., Eigentaste: a constant time collaborative filtering algorithm, Inf. Retr., 4, 2, 133-151 (2001) · Zbl 0989.68052
[9] Spellman, P. T.; Sherlock, G.; Zhang, M. Q.; Iyer, V. R.; Anders, K.; Eisen, M. B.; Brown, P. O.; Botstein, D.; Futcher, B., Comprehensive identification of cell cycle-regulated genes of the yeast saccharomyces cerevisiae by micro array hybridization, Mol. Biol. Cell, 9, 3273-3297 (1998)
[11] Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(l 1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076
[13] Cai, J. F.; Osher, S.; Shen, Z., Convergence of the linearized Bregman iteration for \(l_1\)-norm minimization, Math. Comp., 78, 268, 2127-2136 (2009) · Zbl 1198.65103
[14] Cai, J. F.; Osher, S.; Shen, Z., Linearized Bregman iterations for compressed sensing, Math. Comp., 78, 267, 1515-1536 (2009) · Zbl 1198.65102
[15] Yin, W.; Osher, S.; Goldfarb, D.; Darbon, J., Bregman iterative algorithms for 1-minimization with applications to compressed sensing, SIAM J. Imag. Sci., 1, 1, 143-168 (2008) · Zbl 1203.90153
[16] Cai, J. F.; Candès, E.; Shen, Z. W., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 4, 1956-1982 (2010) · Zbl 1201.90155
[18] Chen, S. S.; Donoho, D.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 33-61 (1998) · Zbl 0919.94002
[19] Tibshirani, R., Regression shrinkage and selection via the Lasso, J. R. Stat. Soc. Ser. B, 58, 1, 267-288 (1996) · Zbl 0850.62538
[20] Van Den Berg, E.; Friedlander, M. P., Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 890-912 (2008) · Zbl 1193.49033
[21] Daubechies, I.; Fornasier, M.; Loris, I., Accelerated projected gradient method for linear inverse problems with sparsity constraints, J. Fourier Anal. Appl., 14, 5-6, 764-792 (2008) · Zbl 1175.65062
[23] Bertsekas, D. P.; Nedić, A.; Ozdaglar, A. E., Convex Analysis and Optimization (2006), Athena Scientific and Tsinghua University Press
[24] Drineas, P.; Kannan, R.; Mahoney, M. W., Fast Monte Carlo algorithms for matrices II: computing low-rank approximations to a matrix, SIAM J. Comput., 36, 132-157 (2006) · Zbl 1111.68147
[26] Candès, E.; Plan, Y., Matrix completion with noise, Proc. IEEE, 98, 925-936 (2010)
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.