article

Joint Schatten $$p$$p-norm and $$\ell _p$$ℓp-norm robust matrix completion for missing value recovery

Authors:

Chris DingAuthors Info & Claims

Knowledge and Information Systems, Volume 42, Issue 3

Pages 525 - 544

https://doi.org/10.1007/s10115-013-0713-z

Published: 01 March 2015 Publication History

Abstract

The low-rank matrix completion problem is a fundamental machine learning and data mining problem with many important applications. The standard low-rank matrix completion methods relax the rank minimization problem by the trace norm minimization. However, this relaxation may make the solution seriously deviate from the original solution. Meanwhile, most completion methods minimize the squared prediction errors on the observed entries, which is sensitive to outliers. In this paper, we propose a new robust matrix completion method to address these two problems. The joint Schatten $$p$$ p -norm and $$\ell _p$$ ℓ p -norm are used to better approximate the rank minimization problem and enhance the robustness to outliers. The extensive experiments are performed on both synthetic data and real-world applications in collaborative filtering prediction and social network link recovery. All empirical results show that our new method outperforms the standard matrix completion methods.

References

[1]

Srebro N, Rennie J, Jaakkola T (2004) Maximum margin matrix factorization. Conf Neural Inf Process Syst (NIPS) 17:1329---1336

[2]

Rennie J, Srebro N (2005) Fast maximum margin matrix factorization for collaborative prediction. In: International conference on machine learning (ICML)

[3]

Abernethy J, Bach F, Evgeniou T, Vert JP (2009) A new approach to collaborative filtering: operator estimation with spectral regularization. J Mach Learn Res (JMLR) 10:803---826

Digital Library

[4]

Candès E, Recht B (2009) Exact matrix completion via convex optimization. Found Comput Math 9(6):717---772

[5]

Candes EJ, Tao T (2009) The power of convex relaxation: near-optimal matrix completion. IEEE Trans Inform Theory 56(5):2053---2080

Digital Library

[6]

Recht B, Fazel M, Parrilo PA (2010) Guaranteed minimum rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev 52(3):471---501

Digital Library

[7]

Mazumder R, Hastie T, Tibshirani R (2010) Spectral regularization algorithms for learning large incomplete matrices. J Mach Learn Res (JMLR) 11:2287---2322

Digital Library

[8]

Cai J-F, Candes EJ, Shen Z (2008) A singular value thresholding algorithm for matrix completion. SIAM J Opt 20(4):1956---1982

[9]

Toh K, Yun S (2010) An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac J Opt 6:615---640

[10]

Ji S, Ye Y (2009) An accelerated gradient method for trace norm minimization. In: International conference on machine learning (ICML)

[11]

Liu Y-J, Sun D, Toh K-C (2012) An implementable proximal point algorithmic framework for nuclear norm minimization. Math Program 133(1---2):399---436

[12]

Ma S, Goldfarb D, Chen L (2011) Fixed point and Bregman iterative methods for matrix rank minimization. Math Program 128(1---2):321---353

[13]

Recht B (2011) A simpler approach to matrix completion. J Mach Learn Res 12:3413---3430

Digital Library

[14]

Vishwanath S (2010) Information theoretic bounds for low-rank matrix completion. In: IEEE international symposium on information theory proceedings (ISIT), pp 1508---1512

[15]

Koltchinskii V, Lounici K, Tsybakov A (2011) Nuclear norm penalization and optimal rates for noisy low rank matrix completion. Ann Stat 39:2302---2329

[16]

Salakhutdinov R, Srebro N (2010) Collaborative filtering in a non-uniform world: learning with the weighted trace norm. Adv Neural Inf Process Syst (NIPS) 23:1---8

[17]

Pong TK, Tseng P, Ji S, Ye J (2010) Trace norm regularization: reformulations, algorithms, and multi-task learning. SIAM J Opt 20(6):3465---3489

Digital Library

[18]

Nie F, Wang H, Cai X, Huang H, Ding C (2012) Robust matrix completion via joint schatten $$p$$p-norm and $$l_p$$lp-norm minimization. In: IEEE international conference on data mining (ICDM), pp 566---574

[19]

Huang J, Nie F, Huang H, Lei Y, Ding C (2013) Social trust prediction using rank-k matrix recovery. In: 23rd international joint conference on artificial intelligence

[20]

Huang J, Nie F, Huang H (2013) Robust discrete matrix completion. In: Twenty-seventh AAAI conference on artificial intelligence (AAAI-13), pp 424---430

[21]

Tan VY, Balzano L, Draper SC (2011) Rank minimization over finite fields. In: IEEE international symposium on information theory proceedings (ISIT), pp 1195---1199

[22]

Meka R, Jain P, Dhillon IS (2010) Guaranteed rank minimization via singular value projection. In: Conference on neural information processing systems (NIPS)

[23]

Gabidulin EM (1985) Theory of codes with maximum rank distance. Problemy Peredachi Informatsii 21(1):3---16

[24]

Loidreau P (2008) Properties of codes in rank metric. In: Eleventh international workshop on algebraic and combinatorial coding theory, pp 192---198

[25]

Fazel M, Hindi H, Boyd SP (2001) A rank minimization heuristic with application to minimum order system approximation. IEEE Am Control Conf 6:4734---4739

[26]

Fazel M, Hindi H, Boyd SP (2003) Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices. IEEE Am Control Conf 3:2156---2162

[27]

Blomer J, Karp R, Welzl E (1997) The rank of sparse random matrices over finite fields. Random Struct Algorithms 10(4):407---420

Digital Library

[28]

Ma S, Goldfarb D, Chen L (2011) Fixed point and Bregman iterative methods for matrix rank minimization. Math Program 128(1---2):321---353

[29]

Nie F, Huang H, Ding CHQ (2012) Low-rank matrix recovery via efficient schatten p-norm minimization. In: AAAI conference on artificial intelligence

[30]

Nie F, Huang H, Cai X, Ding C (2010) Efficient and robust feature selection via joint $$\ell _{2,1}$$ℓ2,1-norms minimization. In: Conference on neural information processing systems (NIPS)

[31]

Powell MJD (1969) A method for nonlinear constraints in minimization problems. In: Fletcher R (ed) Optimization. Academic Press, London

[32]

Hestenes MR (1969) Multiplier and gradient methods. J Opt Theory Appl 4:303---320

[33]

Bertsekas DP (1996) Constrained optimization and lagrange multiplier methods. Athena Scientific, Belmont

[34]

Gabay D, Mercier B (1969) A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl 2(1):17---40

[35]

Wright J, Ganesh A, Rao S, Ma Y (2009) Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: The proceedings of the conference on neural information processing systems. pp 1---9

[36]

Candes E, Plan Y (2010) Matrix completion with noise. Proc IEEE 98(6):925---936

[37]

Salakhutdinov R, Mnih A (2008) Probabilistic matrix factorization. Adv Neural Inf Process Syst (NIPS) 20:1257---1264

[38]

Gu Q, Zhou J, Ding C (2010) Collaborative filtering: weighted nonnegative matrix factorization incorporating user and item graphs. In: Siam data mining conference

[39]

Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: International world wide web conference (WWW). ACM, pp 641---650

[40]

Leskovec J, Lang K, Dasgupta A, Mahoney M (2009) Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Int Math 6(1):29---123

[41]

Newman M (2001) Clustering and preferential attachment in growing networks. Phys Rev E 64(2):025102

[42]

Billsus D, Pazzani M (1998) Learning collaborative information filters. In: International conference on machine learning (ICML), pp 46---54

Cited By

Zhang HWen BZha ZZhang BTang YYu GDu W(2023)Accelerated PALM for Nonconvex Low-Rank Matrix Recovery With Theoretical AnalysisIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.330681134:4(2304-2317)Online publication date: 21-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3306811
Zhang HLi SQiu JTang YWen JZha ZWen B(2023)Efficient and Effective Nonconvex Low-Rank Subspace Clustering via SVT-Free OperatorsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.327529933:12(7515-7529)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3275299
Nie FLiu CWang RWang ZLi X(2022)Fast Fuzzy Clustering Based on Anchor GraphIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2021.308199030:7(2375-2387)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/TFUZZ.2021.3081990
Show More Cited By

Joint Schatten $$p$$p-norm and $$\ell _p$$ℓp-norm robust matrix completion for missing value recovery
1. Computing methodologies

Recommendations

Robust Matrix Completion via Joint Schatten p-Norm and lp-Norm Minimization
ICDM '12: Proceedings of the 2012 IEEE 12th International Conference on Data Mining

The low-rank matrix completion problem is a fundamental machine learning problem with many important applications. The standard low-rank matrix completion methods relax the rank minimization problem by the trace norm minimization. However, this ...
Image compressive sensing via Truncated Schatten-p Norm regularization

Low-rank property as a useful image prior has attracted much attention in image processing communities. Recently, a nonlocal low-rank regularization (NLR) approach toward exploiting low-rank property has shown the state-of-the-art performance in ...
Performance guarantees for Schatten-p quasi-norm minimization in recovery of low-rank matrices

We address some theoretical guarantees for Schatten-p quasi-norm minimization ( p ( 0 , 1 ] ) in recovering low-rank matrices from compressed linear measurements. Firstly, using null space properties of the measurement operator, we provide a sufficient ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Knowledge and Information Systems

Knowledge and Information Systems Volume 42, Issue 3

March 2015

238 pages

ISSN:0219-1377

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer-Verlag London.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 March 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HWen BZha ZZhang BTang YYu GDu W(2023)Accelerated PALM for Nonconvex Low-Rank Matrix Recovery With Theoretical AnalysisIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.330681134:4(2304-2317)Online publication date: 21-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3306811
Zhang HLi SQiu JTang YWen JZha ZWen B(2023)Efficient and Effective Nonconvex Low-Rank Subspace Clustering via SVT-Free OperatorsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.327529933:12(7515-7529)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3275299
Nie FLiu CWang RWang ZLi X(2022)Fast Fuzzy Clustering Based on Anchor GraphIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2021.308199030:7(2375-2387)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1109/TFUZZ.2021.3081990
Guo YSun HHao S(2022)Adaptive dictionary and structure learning for unsupervised feature selectionInformation Processing and Management: an International Journal10.1016/j.ipm.2022.10293159:3Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1016/j.ipm.2022.102931
Liang HKang LHuang J(2022)A robust low-rank matrix completion based on truncated nuclear norm and Lp-normThe Journal of Supercomputing10.1007/s11227-022-04385-878:11(12950-12972)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s11227-022-04385-8
Zhang HLuo WDu WQian JYang JZhang B(2021)Robust Recovery of Low Rank Matrix by Nonconvex Rank RegularizationImage and Graphics10.1007/978-3-030-87358-5_9(106-119)Online publication date: 6-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-87358-5_9
Zhang HQian JZhang BYang JGong CWei Y(2020)Low-Rank Matrix Recovery via Modified Schatten- $p$ Norm Minimization With Convergence GuaranteesIEEE Transactions on Image Processing10.1109/TIP.2019.295792529(3132-3142)Online publication date: 28-Jan-2020
https://dl.acm.org/doi/10.1109/TIP.2019.2957925
Wu GYang MLi YWang J(2020)De novo Prediction of Drug-Target Interaction via Laplacian Regularized Schatten-p Norm MinimizationBioinformatics Research and Applications10.1007/978-3-030-57821-3_14(154-165)Online publication date: 1-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-57821-3_14
Ma JZhang YZhang LDu BTao D(2019)Pseudo supervised matrix factorization in discriminative subspaceProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367471.3367676(4554-4560)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367471.3367676
Ye HLi HCao FZhang L(2019)A Hybrid Truncated Norm Regularization Method for Matrix CompletionIEEE Transactions on Image Processing10.1109/TIP.2019.291873328:10(5171-5186)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1109/TIP.2019.2918733
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents