×

zbMATH — the first resource for mathematics

Max-norm optimization for robust matrix recovery. (English) Zbl 1414.90265
In order to recover an unknown matrix \(M^0 \in \mathbb{R}^{d_1 \times d_2}\) based on some of its entries observed with noise, \(\{Y_{i_t,j_t}\}_{t=1}^n\), the authors propose a hybrid estimator defined as the solution of the optimization problem \[ \begin{cases} \text{Minimize }\frac{1}{n} \sum_{t=1}^n (Y_{i_t,j_t} - M_{i_t,j_t})^2 +\lambda \|M\|_{\max} + \mu \|M\|_*, \\ \text{subject to } M \in \mathbb{R}^{d_1 \times d_2},\; \|M\|_\infty \leq \alpha, \end{cases} \] where \(\|M\|_{\max}\), \(\|M\|_*\) and \(\|M\|_\infty\) denote the max-norm, the nuclear norm and the elementwise \(\infty\)-norm of \(M\), respectively, while \(\lambda >0\) and \(\mu \geq 0\) are tuning parameters. Efficient algorithms are provided along with numerical experiments on different datasets.

MSC:
90C25 Convex programming
90C29 Multi-objective and goal programming
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
Software:
SNLSDP; GADMM; ADMM_QAP
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Abernethy, J; Bach, F; Evgeniou, T; Vert, J-P, A new approach to collaborative filtering: operator estimation with spectral regularization, J. Mach. Learn. Res., 10, 803-826, (2009) · Zbl 1235.68122
[2] Amit, Y., Fink, M., Srebro, N., Ullman, S.: Uncovering shared structures in multiclass classification. In: Proceedings of the 24th International Conference on Machine Learning. ACM (2007) · Zbl 1353.90110
[3] Argyriou, A; Evgeniou, T; Pontil, M, Convex multi-task feature learning, Mach. Learn., 73, 243-272, (2008)
[4] Bennett, J., Lanning, S.: The Netflix prize. In: Proceedings of KDD Cup and Workshop. http://www.cs.uic.edu/ liub/KDD-cup-2007/proceedings.html (2007) · Zbl 1198.90321
[5] Biswas, P; Liang, T; Toh, K; Wang, T; Ye, Y, Semidefinite programming approaches for sensor network localization with noisy distance measurements, IEEE Trans. Autom. Sci. Eng., 3, 360-371, (2006)
[6] Cai, J-F; Candès, EJ; Shen, Z, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982, (2010) · Zbl 1201.90155
[7] Cai, TT; Zhou, W-X, Matrix completion via MAX-norm constrained optimization, Electron. J. Stat., 10, 1493-1525, (2016) · Zbl 1342.62091
[8] Candès, EJ; Li, X; Ma, Y; Wright, J, Robust principal component analysis?, J. ACM, 58, 1-37, (2009) · Zbl 1327.62369
[9] Candès, EJ; Recht, B, Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772, (2009) · Zbl 1219.90124
[10] Candès, EJ; Tao, T, The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory, 56, 2053-2080, (2010) · Zbl 1366.15021
[11] Chen, C; He, B; Yuan, X, Matrix completion via an alternating direction method, IMA J. Numer. Anal., 32, 227-245, (2012) · Zbl 1236.65043
[12] Doan, X; Vavasis, S, Finding approximately rank-one submatrices with the nuclear norm and \(ℓ _1\)-norm, SIAM J. Optim., 23, 2502-2540, (2013) · Zbl 1297.90114
[13] Drusvyatskiy, D; Vavasis, S; Wolkowicz, H, Extreme point inequalities and geometry of the rank sparsity ball, Math. Program., 152, 521-544, (2015) · Zbl 1327.90200
[14] Fang, EX; He, B; Liu, H; Yuan, X, Generalized alternating direction method of multipliers: new theoretical insights and applications, Math. Prog. Comp., 7, 149-187, (2015) · Zbl 1353.90110
[15] Fazel, M., Hindi, H., Boyd, S.P.: A rank minimization heuristic with application to minimum order system approximation. In: Proceedings of the American Control Conference, vol. 6. IEEE (2001) · Zbl 1242.62069
[16] Figueiredo, M; Nowak, R; Wright, S, Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process., 1, 586598, (2007)
[17] Jalali, A., Srebro, N.: Clustering using max-norm constrained optimization. In: Proceedings of the 29th International Conference on Machine Learning (ICML-12) (2012) · Zbl 1297.90114
[18] Jameson, G.J.O.: Summing and Nuclear Norms in Banach Space Theory, vol. 8. Cambridge University Press, Cambridge (1987) · Zbl 0634.46007
[19] Keshavan, RH; Montanari, A; Oh, S, Matrix completion from noisy entries, J. Mach. Learn. Res., 11, 2057-2078, (2010) · Zbl 1242.62069
[20] Klopp, O, Noisy low-rank matrix completion with general sampling distribution, Bernoulli, 20, 282-303, (2014) · Zbl 1400.62115
[21] Koltchinskii, V; Lounici, K; Tsybakov, AB, Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion, Ann. Statist., 39, 2302-2329, (2011) · Zbl 1231.62097
[22] Lee, J., Recht, B., Srebro, N., Tropp, J., Salakhutdinov, R.: Practical large-scale optimization for max-norm regularization. In: Proceedings of the Advances in Neural Information Processing Systems (2010) · Zbl 1236.65043
[23] Linial, N; Mendelson, S; Schechtman, G; Shraibman, A, Complexity measures of sign matrices, Combinatorica, 27, 439-463, (2007) · Zbl 1164.68006
[24] Liu, Z; Vandenberghe, L, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 1235-1256, (2009) · Zbl 1201.90151
[25] Mackey, L; Jordan, MI; Chen, RY; Farrell, B; Tropp, JA, Matrix concentration inequalities via the method of exchangeable pairs, Ann. Probab., 42, 906-945, (2014) · Zbl 1294.60008
[26] Negahban, S; Wainwright, MJ, Restricted strong convexity and weighted matrix completion: optimal bounds with noise, J. Mach. Learn. Res., 13, 1665-1697, (2012) · Zbl 1436.62204
[27] Netflix (2006). Netflix problem. http://www.netflixprize.com · Zbl 1235.68122
[28] Oliveira, D.E., Wolkowicz, H., Xu, Y.: ADMM for the SDP relaxation of the QAP. arXiv preprint arXiv:1512.05448 (2015)
[29] Orabona, F., Argyriou, A., Srebro, N.: PRISMA: Proximal iterative smoothing algorithm. arXiv preprint arXiv:1206.2372 (2012) · Zbl 1205.90218
[30] Recht, B, A simpler approach to matrix completion, J. Mach. Learn. Res., 12, 3413-3430, (2011) · Zbl 1280.68141
[31] Recht, B; Fazel, M; Parrilo, PA, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501, (2010) · Zbl 1198.90321
[32] Rohde, A; Tsybakov, AB, Estimation of high-dimensional low-rank matrices, Ann. Stat., 39, 887-930, (2011) · Zbl 1215.62056
[33] Shen, J; Xu, H; Li, P, Online optimization for MAX-norm regularization, Mach. Learn., 106, 419-457, (2017) · Zbl 1454.68132
[34] Srebro, N., Rennie, J., Jaakkola, T.S.: Maximum-margin matrix factorization. In: Proceedings of the Advances in Neural Information Processing Systems (2005) · Zbl 1201.90155
[35] Srebro, N., Salakhutdinov, R.R.: Collaborative filtering in a non-uniform world: learning with the weighted trace norm. In: Proceedings of the Advances in Neural Information Processing Systems (2010)
[36] Srebro, N., Shraibman, A.: Rank, trace-norm and max-norm. In: Proceedings of the 18th Annual Conference on Learning Theory (2005) · Zbl 1137.68563
[37] Toh, K-C; Yun, S, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6, 615-640, (2010) · Zbl 1205.90218
[38] Trefethen, L.N., Bau III, D.: Numerical Linear Algebra, vol. 50. SIAM, Philadelphia (1997) · Zbl 0874.65013
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.