An Algorithm of Schatten ρ-Norm Regularized Least Squares Problems for Video Restoration

Abstract:

Minimizing the nuclear norm is recently considered as the convex relaxation of the rank minimization problem and arises in many applications as Netflix challenge. A closest nonconvex relaxation - Schatten norm minimization has been proposed to replace the NP hard rank minimization. In this paper, an algorithm based on Majorization Minimization has be proposed to solve Schatten norm minimization. The numerical experiments show that Schatten norm with recovers low rank matrix from fewer measurements than nuclear norm minimization. The numerical results also indicate that our algorithm give a more accurate reconstruction

• Periodical: Advanced Materials Research (Volumes 718-720)
• Pages: 2308-2313
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.718-720.2308
• Online since: July 2013
• Authors: Lu Liu, Wei Huang, Di Rong Chen
• Keywords: Isometry Constant, Majorization Minimization, Random Matrix, Rank Minimization, Schatten p-Norm, Singular Value Decomposition

References

[1] E. J. Candes, B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics 9 (2009) 717-772.

DOI: 10.1007/s10208-009-9045-5

[2] B. Recht, M. Fazel, P. Parrilo, Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, SIAM Review 52(2010) 471-501.

DOI: 10.1137/070697835

[3] Fazel, M., Matrix rank minimization with applications, Ph.D. thesis, Stanford University , 2002.

[4] K. C. Toh, M. J. Todd, R. H. Tutuncu, SDPT3 a Matlab software package for semidefinite quadratic inear programming, Information on http://www.math.nus.edu.sg/mattohkc/sdpt3.html

DOI: 10.1109/cacsd.2004.1393891

[5] Liu, Z., Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications 3(2009) 1235-1256.

DOI: 10.1137/090755436

[6] R. Mazumder, T. Hastie, R. Tibshirani, Spectral Regularization Algorithms for Learning Large Incomplete Matrices, The Journal of Machine Learning Research 11(2010) 2287-2322.

[7] Information on http://cnx.org/content/m32168/latest/

[8] J.-F. Cai, E. J. Candes, Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. on Optimization 20(2010)1956-1982.

DOI: 10.1137/080738970

[9] Information on http://soi.stanford.edu/~rmunk/PROPACK/