Improved nonconvex optimization model for low-rank matrix recovery

Abstract

Low-rank matrix recovery is an important problem extensively studied in machine learning, data mining and computer vision communities. A novel method is proposed for low-rank matrix recovery, targeting at higher recovery accuracy and stronger theoretical guarantee. Specifically, the proposed method is based on a nonconvex optimization model, by solving the low-rank matrix which can be recovered from the noisy observation. To solve the model, an effective algorithm is derived by minimizing over the variables alternately. It is proved theoretically that this algorithm has stronger theoretical guarantee than the existing work. In natural image denoising experiments, the proposed method achieves lower recovery error than the two compared methods. The proposed low-rank matrix recovery method is also applied to solve two real-world problems, i.e., removing noise from verification code and removing watermark from images, in which the images recovered by the proposed method are less noisy than those of the two compared methods.

Keywords

machine learning / computer vision / matrix recovery / nonconvex optimization

References

[1] DeerwesterS, DumaisS T, FurnasG W, LandauerT K, HarshmanR. Indexing by latent semantic analysis [J]. Journal of the American Society for Information Science, 1990, 41(6): 391-407

[2] MazumderR, HastieT, TibshiraniR. Spectral regularization algorithms for learning large incomplete matrices [J]. Journal of Machine Learning Research, 2010, 11(2): 2287-2322

[3] McfarlaneN, SchofieldC. Segmentation and tracking of piglets in images [J]. British Machine Vision and Applications, 1995187-193

[4] ElgammalA, HarwoodD, DavisL. Non-parametric model for background subtraction [C]. European Conference on Computer Vision. London, UK, 2000751-767

[5] LiuG, LinZ, YuY. Robust subspace segmentation by low-rank representation [C]. International Conference on Machine Learning. Haifa, Israel, 2010663-670

[6] WangS, ZhangZ. Colorization by matrix completion [C]. AAAI Conference on Artificial Intelligence. Toronto, Canada, 20121169-1175

[7] CandèsE, LiX, MaY, WrightJ. Robust principal component analysis [J]. Journal of the ACM, 2011, 58(3): 1-31

[8] WangN, YaoT, WangJ, YeungD-Y. A probabilistic approach to robust matrix factorization [C]. European Conference on Computer Vision, 2012

[9] WangS, LiuD, ZhangZ. Nonconvex relaxation approaches to robust matrix recovery [C]. International Joint Conference on Artificial Intelligence. Beijing, China, 20131764-1770

[10] SalakhutdinovR, MnihA. Bayesian probabilistic matrix factorization using Markov chain Monte Carlo [C]. International Conference on Machine Learning. Helsinki, Finland, 2008880-887

[11] SalakhutdinovR, MnihA. Probabilistic matrix factorization [C]. Advances in Neural Information Processing Systems. Vancouver, B.C., Canada, 20081257-1264

[12] ChengB, LiuG, WangJ, HuangZ, YanS. Multi-task low-rank affinity pursuit for image segmentation [C]. IEEE Conference on Computer Vision and Pattern Recognition. Barcelona, Spain, 20112439-2446

[13] KyrillidisA, CevherVMatrix Alps: Accelerated low rank and sparse matrix reconstruction [R], 2012

[14] LinZ, ChenM, WuL, MaY. The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices [R]. UIUC Technical Report, 2009

[15] FanJ, LiR. Variable selection via nonconcave penalized likelihood and its Oracle properties [J]. Journal of the American Statistical Association, 2001, 96: 1348-1361

[16] ZouH, LiR. One-step sparse estimates in nonconcave penalized likelihood models [J]. The Annals of Statistics, 2008, 36(4): 1509-1533

[17] ZhangC H. Nearly unbiased variable selection under minimax concave penalty [J]. The Annals of Statistics, 2010, 38: 894-942

[18] GaoC, WangN, YuQ, ZhangZ. A feasible nonconvex relaxation approach to feature selection [C]. AAAI Conference on Artificial Intelligence. San Francisco, USA, 2011356-361

[19] GongP, YeJ, ZhangC. Multi-stage multi-task feature learning [C]. Advances in Neural Information Processing Systems. Beijing, China, 2012895-903

[20] ShiJ, RenX, DaiG, WangJ, ZhangZ. A non-convex relaxation approach to sparse dictionary learning [C]. IEEE Conference on Computer Vision and Pattern Recognition. Colorado, USA, 20111809-1816

[21] ZhangZ, TuB. Nonconvex penalization using Laplace exponents and concave conjugates [C]. Advances in Neural Information Processing Systems. Lake Tahoe, USA, 2012611-619

[22] ZhangZ, WangS, LiuD, JordanM I. EP-GIG priors and applications in Bayesian sparse learning [J]. Journal of Machine Learning Research, 2012, 13: 2031-2061

[23] HunterR, LiR. Variable selection using MM algorithm [J]. Annals of Statistics, 2005, 33(4): 1617-1642

[24] ZhangZ, MatsushitaY, MaY. Camera calibration with lens distortion from low-rank textures [C]. IEEE Conference on Computer Vision and Pattern Recognition, Colorado, USA, 20112321-2328

[25] PengY, GaneshA, WrightJ, XuW, MaY. Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images [J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012, 34(11): 2233-2246

[26] TibshiraniR. Regression shrinkage and selection via the lasso [J]. Journal of the Royal Statistical Society: Series B. Methodological, 1996, 58(1): 267-288

[27] MartinD, FowlkesC, TalD, MalikJ. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics [C]. IEEE International Conference on Computer Vision. Vancouver, Canada, 2001416-423