# 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:
 [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