zbMATH — the first resource for mathematics

Some empirical advances in matrix completion. (English) Zbl 1219.94068
Summary: Solving the matrix completion problem via rank minimization is NP-hard. Recent studies have shown that this problem can be addressed as a convex nuclear-norm minimization problem, albeit at an increase in the required number of samples. This paper proposes a non-convex optimization problem (a variant of convex nuclear-norm minimization) for the solution of matrix completion. It also develops a fast numerical algorithm to solve the optimization. This empirical study shows that significant improvement can be achieved by the proposed method compared to the previous ones.
The number of required samples is also dependent on the type of the sampling scheme used. This work shows that blue-noise sampling schemes yield more accurate matrix completion results compared to the popular uniform random sampling.
94A20 Sampling theory in information and communication theory
65F30 Other matrix algorithms (MSC2010)
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
Full Text: DOI
[1] Savas, B.; Lindgren, D.: Rank reduction and volume minimization approach to state-space subspace system identification, Signal processing 86, No. 11, 3275-3285 (2006) · Zbl 1172.93400 · doi:10.1016/j.sigpro.2006.01.008
[2] Al-Jazzara, S. O.; Mclernonb, D. C.; Smadi, M. A.: SVD-based joint azimuth/elevation estimation with automatic pairing, Signal processing 90, No. 5, 1669-1675 (2010) · Zbl 1194.94050 · doi:10.1016/j.sigpro.2009.11.017
[3] Candès, E. J.; Recht, B.: Exact matrix completion via convex optimization, Found. comput. Math. 9, No. 6, 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[4] Candès, E. J.; Tao, T.: The power of convex relaxation: near-optimal matrix completion, IEEE trans. Inf. theory 56, No. 5, 2053-2080 (2010) · Zbl 1366.15021
[5] B. Recht, A Simpler Approach to Matrix Completion arXiv:0910.0651v2. · Zbl 1280.68141
[6] Donoho, D. L.: For most large underdetermined systems of linear equations, the minimal ell-1 norm solution is also the sparsest solution, Comm. pure and applied maths. 59, No. 6, 797-829 (2006) · Zbl 1113.15004 · doi:10.1002/cpa.20132
[7] Chartrand, R.; Yin, W.: Iteratively reweighted algorithms for compressive sensing, IEEE conf. Acoust., speech signal process. (2008)
[8] Tang, G.; Shahidi, R.; Herrmann, F. J.; Ma, J.: Higher dimensional blue-noise sampling schemes for curvelet-based seismic data recovery, Soc. explor. Geophys. (2009)
[9] Oliveira, J.; Bioucas-Dias, J.; Figueiredo, M.: Adaptive total variation image deblurring: a majorization–minimization approach, Signal processing 89, No. 9, 1683-1693 (2009) · Zbl 1178.94029 · doi:10.1016/j.sigpro.2009.03.018
[10] \langlehttp://cnx.org/content/m32168/latest/ angle
[11] Lin, T.; Herrmann, F. J.: Compressed extrapolation, Geophysics 72, No. 5, 77-93 (2007)
[12] Cai, J. -F.; Candès, E. J.; Shen, Z.: A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20, No. 4, 1956-1982 (2008) · Zbl 1201.90155 · doi:10.1137/080738970
[13] S. Ma, D. Goldfarb, L. Chen, Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization, arXiv:0905.1643v2. · Zbl 1221.65146
[14] \langlehttp://www.mathworks.com/matlabcentral/fileexchange/26395-matrix-completion-via-thresholding angle.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.