article

Free access

Using side information to reliably learn low-rank matrices from missing and corrupted observations

Authors:

Kai-Yang Chiang,

Inderjit S. Dhillon,

Cho-Jui HsiehAuthors Info & Claims

The Journal of Machine Learning Research, Volume 19, Issue 1

Pages 3005 - 3039

Published: 01 January 2018 Publication History

PDF eReader Publisher Site

Abstract

Learning a low-rank matrix from missing and corrupted observations is a fundamental problem in many machine learning applications. However, the role of side information in low-rank matrix learning has received little attention, and most current approaches are either ad-hoc or only applicable in certain restrictive cases. In this paper, we propose a general model that exploits side information to better learn low-rank matrices from missing and corrupted observations, and show that the proposed model can be further applied to several popular scenarios such as matrix completion and robust PCA. Furthermore, we study the effect of side information on sample complexity and show that by using our model, the efficiency for learning can be improved given sufficiently informative side information. This result thus provides theoretical insight into the usefulness of side information in our model. Finally, we conduct comprehensive experiments in three real-world applications-- relationship prediction, semi-supervised clustering and noisy image classification, showing that our proposed model is able to properly exploit side information for more effective learning both in theory and practice.

References

[1]

P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-482, 2003.

Digital Library

[2]

J.-F. Cai, E. J. Candès, and Z. Shen. A singular value thresholding algorithm for matrix completion. Society for Industrial and Applied Mathematics, 20(4):1956-1982, 2010.

[3]

E. J. Candès and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6): 925-936, 2010.

[4]

E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111-119, 2012.

Digital Library

[5]

E. J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transaction of Information Theory, 56(5):2053-2080, 2009.

Digital Library

[6]

E. J. Candès, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of ACM, 58(3):11:1-11:37, 2011.

Digital Library

[7]

V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2), 2011.

[8]

T. Chen, W. Zhang, Q. Lu, K. Chen, Z. Zheng, and Y. Yu. SVDFeature: A toolkit for feature-based collaborative filtering. Journal of Machine Learning Research, 13:3619-3622, 2012.

Digital Library

[9]

Y. Chen, A. Jalali, S. Sanghavi, and C. Caramanis. Low-rank matrix recovery from errors and erasures. IEEE Transaction of Information Theory, 59(7):4324-4337, 2013.

Digital Library

[10]

Y. Chen, A. Jalali, S. Sanghavi, and H. Xu. Clustering partially observed graphs via convex optimization. Journal of Machine Learning Research, 15(1):2213-2238, 2014.

Digital Library

[11]

K.-Y. Chiang, C.-J. Hsieh, N. Natarajan, I. S. Dhillon, and A. Tewari. Prediction and clustering in signed networks: A local to global perspective. Journal of Machine Learning Research, 15:1177-1213, 2014.

Digital Library

[12]

K.-Y. Chiang, C.-J. Hsieh, and I. S. Dhillon. Matrix completion with noisy side information. In Advances in Neural Information Processing Systems, 2015.

[13]

K.-Y. Chiang, C.-J. Hsieh, and I. S. Dhillon. Robust principal component analysis with side information. In International Conference on Machine Learning, 2016.

[14]

J. V. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon. Information-theoretic metric learning. In International Conference on Machine Learning, pages 209-216, 2007.

Digital Library

[15]

M. Fazel, H. Hindi, and S. P. Boyd. A rank minimization heuristic with application to minimum order system approximation. In American Control Conference, volume 6, pages 4734-4739, 2001.

[16]

W. Ha and R. F. Barber. Robust PCA with compressed data. In Advances in Neural Information Processing Systems, 2015.

[17]

H. Hotelling. Analysis of a complex of statistical variables into principal components. Journal of Educational Psychology, 24(6):417-441, 1933.

[18]

C.-J. Hsieh and P. A. Olsan. Nuclear norm minimization via active subspace selection. In International Conference on Machine Learning, 2014.

[19]

C.-J. Hsieh, K.-Y. Chiang, and I. S. Dhillon. Low rank modeling of signed networks. In International Conference on Knowledge Discovery and Data Mining, pages 507-515, 2012.

Digital Library

[20]

C.-J. Hsieh, N. Natarajan, and I. S. Dhillon. PU learning for matrix completion. In International Conference on Machine Learning, 2015.

[21]

P. Jain and I. S. Dhillon. Provable inductive matrix completion. CoRR, abs/1306.0626, 2013.

[22]

P. Jain, P. Netrapalli, and S. Sanghavi. Low-rank matrix completion using alternating minimization. In Symposium on Theory of Computing, pages 665-674, 2013.

Digital Library

[23]

S. M. Kakade, K. Sridharan, and A. Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in Neural Information Processing Systems, pages 793-800, 2008.

[24]

R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. Journal of Machine Learning Research, 11:2057-2078, 2010.

Digital Library

[25]

Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 42:30-37, 2009.

Digital Library

[26]

J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predicting positive and negative links in online social networks. In International Conference on World Wide Web, pages 641-650, 2010.

Digital Library

[27]

Z. Li and J. Liu. Constrained clustering by spectral kernel learning. In International Conference on Computer Vision, 2009.

[28]

D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol., 58(7):1019-1031, 2007.

[29]

G. Liu, Z. Lin, and Y. Yu. Robust subspace segmentation by low-rank representation. In International Conference on Machine Learning, 2010.

Digital Library

[30]

G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Aanalysis and Machine Intelligence, 35(1):171-184, 2013.

Digital Library

[31]

P. Massa and P. Avesani. Trust-aware bootstrapping of recommender systems. In ECAI Workshop on Recommender Systems, pages 29-33, 2006.

[32]

R. Meir and T. Zhang. Generalization error bounds for bayesian mixture algorithms. Journal of Machine Learning Research, 4:839-860, 2003.

Digital Library

[33]

A. K. Menon and C. Elkan. Link prediction via matrix factorization. European Conference on Machine Learning and Knowledge Discovery in Databases, pages 437-452, 2011.

Digital Library

[34]

N. Natarajan and I. S. Dhillon. Inductive matrix completion for predicting gene-disease associations. Bioinformatics, 30(12):60-68, 2014.

[35]

S. Negahban and M. J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Journal of Machine Learning Research, 13(1): 1665-1697, 2012.

Digital Library

[36]

B. Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12:3413-3430, 2011.

Digital Library

[37]

O. Shamir and S. Shalev-Shwartz. Matrix completion with the trace norm: Learning, bounding, and transducing. Journal of Machine Learning Research, 15(1):3401-3423, 2014.

Digital Library

[38]

D. Shin, S. Cetintas, K.-C. Lee, and I. S. Dhillon. Tumblr blog recommendation with boosted inductive matrix completion. In International Conference on Information and Knowledge Management, pages 203-212, 2015.

Digital Library

[39]

N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. In Annual Conference on Learning Theory, pages 545-560, 2005.

Digital Library

[40]

Paul Tseng. Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of optimization theory and applications, 109(3):475-494, 2001.

[41]

M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive Neuroscience, 3 (1):71-86, 1991.

Digital Library

[42]

J. Wright, A. Ganesh, S. Rao, Y. Peng, and Y. Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. In Advances in Neural Information Processing Systems, 2009.

[43]

H. Xu, C. Caramanis, and S. Sanghavi. Robust PCA via outlier pursuit. In Advances in Neural Information Processing Systems, pages 2496-2504, 2010.

Digital Library

[44]

M. Xu, R. Jin, and Z.-H. Zhou. Speedup matrix completion with side information: Application to multi-label learning. In Advances in Neural Information Processing Systems, 2013.

[45]

J. Yi, L. Zhang, R. Jin, Q. Qian, and A. Jain. Semi-supervised clustering by input pattern assisted pairwise similarity matrix completion. In International Conference on Machine Learning, 2013.

[46]

K. Zhong, P. Jain, and I. S. Dhillon. Efficient matrix sensing using rank-1 Gaussian measurements. In International Conference on Algorithmic Learning Theory, 2015.

Digital Library

Cited By

Alves R(2024)Regionalization-Based Collaborative Filtering: Harnessing Geographical Information in RecommendersACM Transactions on Spatial Algorithms and Systems10.1145/365664110:2(1-23)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3656641
Chae JNarayanamurthy PBac SSharada SMitra U(2024)Matrix Approximation With Side Information: When Column Sampling Is EnoughIEEE Transactions on Signal Processing10.1109/TSP.2024.338837272(2276-2291)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3388372
Han ZZhang SLiu ZWang YYao JWang Y(2023)Tensor Robust Principal Component Analysis With Side Information: Models and ApplicationsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.323937633:8(3713-3725)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3239376
Show More Cited By

Using side information to reliably learn low-rank matrices from missing and corrupted observations
1. Computing methodologies

Recommendations

A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Learning
WWW '21: Proceedings of the Web Conference 2021

Matrix learning is at the core of many machine learning problems. A number of real-world applications such as collaborative filtering and text mining can be formulated as a low-rank matrix completion problems, which recovers incomplete matrix using low-...
A fast tri-factorization method for low-rank matrix recovery and completion

In recent years, matrix rank minimization problems have received a significant amount of attention in machine learning, data mining and computer vision communities. And these problems can be solved by a convex relaxation of the rank minimization problem ...
Regularized matrix completion with partial side information
Abstract
Side information has been shown useful for improving the performance of matrix completion applications. However, in most cases, only partial side information of either the column or row space is available. In this work, we propose a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 19, Issue 1

January 2018

3249 pages

ISSN:1532-4435

EISSN:1533-7928

Editors:
Francis Bach
INRIA
,
Blei David
Columbia University
,
Bernhard Schölkopf
MPI for Intelligent Systems

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Revised: 01 May 2018

Published: 01 January 2018

Published in JMLR Volume 19, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
113
Total Downloads

Downloads (Last 12 months)46
Downloads (Last 6 weeks)8

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alves R(2024)Regionalization-Based Collaborative Filtering: Harnessing Geographical Information in RecommendersACM Transactions on Spatial Algorithms and Systems10.1145/365664110:2(1-23)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3656641
Chae JNarayanamurthy PBac SSharada SMitra U(2024)Matrix Approximation With Side Information: When Column Sampling Is EnoughIEEE Transactions on Signal Processing10.1109/TSP.2024.338837272(2276-2291)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3388372
Han ZZhang SLiu ZWang YYao JWang Y(2023)Tensor Robust Principal Component Analysis With Side Information: Models and ApplicationsIEEE Transactions on Circuits and Systems for Video Technology10.1109/TCSVT.2023.323937633:8(3713-3725)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TCSVT.2023.3239376
Xia YTang MWang P(2023)Bi-directional matrix completion for highly incomplete multi-label learning via co-embedding predictive side informationApplied Intelligence10.1007/s10489-023-05004-653:23(28074-28098)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1007/s10489-023-05004-6
Yu CXi X(2022)Tensor Completion with Nearly Linear Samples Given Weak Side InformationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35309056:2(1-35)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3530905
Yu C(2022)Nonparametric Matrix Estimation with One-Sided Covariates2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834608(892-897)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834608
Sun LLyu GFeng SHuang X(2021)Beyond missing: weakly-supervised multi-label learning with incomplete and noisy labelsApplied Intelligence10.1007/s10489-020-01878-y51:3(1552-1564)Online publication date: 1-Mar-2021
https://dl.acm.org/doi/10.1007/s10489-020-01878-y
Lyu GFeng SLi YJin YDai GLang C(2020)HERAACM Transactions on Intelligent Systems and Technology10.1145/337950111:3(1-19)Online publication date: 3-Apr-2020
https://dl.acm.org/doi/10.1145/3379501

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents