zbMATH — the first resource for mathematics

Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank. (English) Zbl 1346.90662
Summary: The nonnegative rank of a matrix \(A\) is the smallest integer \(r\) such that \(A\) can be written as the sum of \(r\) rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of “positive” ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks. Additionally the bounds we propose can be computed by semidefinite programming using sum-of-squares relaxations. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that enjoys other interesting structural properties. For the case of the nonnegative rank we show that our bound has an appealing connection with existing combinatorial bounds and other norm-based bounds. For example we show that our lower bound is a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lovász \(\bar{\vartheta }\) number of the rectangle graph of the matrix. We also prove that the lower bound is always greater than or equal to the hyperplane separation bound (and other similar “norm-based” bounds). We also discuss the case of the tensor nonnegative rank as well as the cp-rank, and compare our bound with existing results.

90C25 Convex programming
15A23 Factorization of matrices
15B48 Positive matrices and their generalizations; cones of matrices
frlib; YALMIP
Full Text: DOI arXiv
[1] Allman, ES; Rhodes, JA; Sturmfels, B; Zwiernik, P, Tensors of nonnegative rank two, Linear Algebra Appl., 473, 37-53, (2013) · Zbl 1312.15033
[2] Bachoc, C., Gijswijt, D.C., Schrijver, A., Vallentin, F.: Invariant semidefinite programs. In: Handbook on Semidefinite, Conic and Polynomial Optimization. Springer, pp. 219-269 (2012) · Zbl 1334.90097
[3] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003) · Zbl 1030.15022
[4] Blekherman, G., Parrilo, P.A., Thomas, R.R. (eds.): Semidefinite optimization and convex algebraic geometry. MOS-SIAM Series on Optimization, vol. 13. SIAM (2013) · Zbl 1260.90006
[5] Blekherman, G; Teitler, Z, On maximum, typical and generic ranks, Math. Ann., 362, 1021-1031, (2015) · Zbl 1326.15034
[6] Bocci, C; Carlini, E; Rapallo, F, Perturbation of matrices and nonnegative rank with a view toward statistical models, SIAM J. Matrix Anal. Appl., 32, 1500-1512, (2011) · Zbl 1242.15031
[7] Borwein, J; Wolkowicz, H, Regularizing the abstract convex program, J. Math. Anal. Appl., 83, 495-530, (1981) · Zbl 0467.90076
[8] Braun, G., Fiorini, S., Pokutta, S., Steurer, D.: Approximation limits of linear programs (beyond hierarchies). In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 480-489 (2012) · Zbl 1343.68308
[9] Braun, G., Pokutta, S.: Common information and unique disjointness. In: IEEE 54th Annual Symposium on Foundations of Computer Science (2013) · Zbl 1353.68072
[10] Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing. ACM, pp. 161-170 (2013) · Zbl 1293.68137
[11] Chandrasekaran, V; Recht, B; Parrilo, PA; Willsky, AS, The convex geometry of linear inverse problems, Found. Comput. Math., 12, 805-849, (2012) · Zbl 1280.52008
[12] Comon, P; Golub, G; Lim, LH; Mourrain, B, Symmetric tensors and symmetric tensor rank, SIAM J. Matrix Anal. Appl., 30, 1254-1279, (2008) · Zbl 1181.15014
[13] Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (2012) · Zbl 0762.94001
[14] Dickinson, P.J.C.: The Copositive Cone, the Completely Positive Cone and Their Generalisations. Ph.D. thesis, University of Groningen (2013) · Zbl 0185.40101
[15] Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57, 403-415 (2014). doi:10.1007/s10589-013-9594-z · Zbl 1330.90103
[16] Doan, XV; Vavasis, S, Finding approximately rank-one submatrices with the nuclear norm and \(ℓ _1\)-norm, SIAM J. Optim., 23, 2502-2540, (2013) · Zbl 1297.90114
[17] Drton, M., Sturmfels, B., Sullivant, S.: Lectures on Algebraic Statistics. Springer, New York (2009) · Zbl 1166.13001
[18] Dukanovic, I; Rendl, F, Semidefinite programming relaxations for graph coloring and maximal clique problems, Math. Program., 109, 345-365, (2007) · Zbl 1278.90299
[19] Fawzi, H; Gouveia, J; Parrilo, PA; Robinson, RZ; Thomas, RR, Positive semidefinite rank, Math. Program. Ser. B, (2015) · Zbl 1327.90174
[20] Fawzi, H; Parrilo, PA, Lower bounds on nonnegative rank via nonnegative nuclear norms, Math. Program. Ser. B, (2014) · Zbl 1327.90202
[21] Fiorini, S; Kaibel, V; Pashkovich, K; Theis, DO, Combinatorial bounds on nonnegative rank and extended formulations, Discrete Math., 313, 67-83, (2013) · Zbl 1259.90111
[22] Gatermann, K; Parrilo, PA, Symmetry groups, semidefinite programs, and sums of squares, J. Pure Appl. Algebra, 192, 95-128, (2004) · Zbl 1108.13021
[23] Gillis, N; Glineur, F, On the geometric interpretation of the nonnegative rank, Linear Algebra Appl., 437, 2685-2712, (2012) · Zbl 1258.65039
[24] Gouveia, J; Parrilo, PA; Thomas, RR, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[25] Grone, R, Decomposable tensors as a quadratic variety, Proc. Am. Math. Soc., 64, 227-230, (1977) · Zbl 0404.15008
[26] Grone, R; Johnson, CR; Sá, EM; Wolkowicz, H, Positive definite completions of partial Hermitian matrices, Linear Algebra Appl., 58, 109-124, (1984) · Zbl 0547.15011
[27] Karchmer, M., Kushilevitz, E., Nisan, N.: Fractional covers and communication complexity. In: Proceedings of the Seventh Annual Structure in Complexity Theory Conference. IEEE, pp. 262-274 (1992) · Zbl 0817.68094
[28] König, H, Cubature formulas on spheres, Math. Res., 107, 201-212, (1999) · Zbl 0977.41014
[29] Kubjas, K; Robeva, E; Sturmfels, B; etal., Fixed points EM algorithm and nonnegative rank boundaries, Ann. Stat., 43, 422-461, (2015) · Zbl 1308.62035
[30] Landsberg, J.M.: Tensors: Geometry and Applications, vol. 128. AMS Bookstore (2012) · Zbl 1238.15013
[31] Lee, T; Shraibman, A, Lower bounds in communication complexity, Found. Trendsin Theor. Comput. Sci., 3, 263-399, (2009) · Zbl 1193.94002
[32] Lim, LH; Comon, P, Nonnegative approximations of nonnegative tensors, J. Chemom., 23, 432-441, (2009)
[33] Löfberg, J.: YALMIP: a toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei, Taiwan (2004). http://users.isy.liu.se/johanl/yalmip
[34] Lovász, L, On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390, (1975) · Zbl 0323.05127
[35] Lovász, L; Korte, B (ed.); Promel, H (ed.); Graham, RL (ed.), Communication complexity: a survey, 235-265, (1990), Secaucus
[36] Lund, C; Yannakakis, M, On the hardness of approximating minimization problems, J. ACM, 41, 960-981, (1994) · Zbl 0814.68064
[37] Meurdesoif, P, Strengthening the lovász bound for graph coloring, Math. Program., 102, 577-588, (2005) · Zbl 1059.05052
[38] Mond, D; Smith, J; Straten, D, Stochastic factorizations, sandwiched simplices and the topology of the space of explanations. proc. R. soc. lond. ser. A math. phys, Eng. Sci., 459, 2821-2845, (2003) · Zbl 1051.60076
[39] Nesterov, Y; Todd, MJ, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res., 22, 1-42, (1997) · Zbl 0871.90064
[40] Permenter, F., Parrilo, P.: Partial facial reduction: simplified, equivalent sdps via approximations of the psd cone. arXiv preprintarXiv:1408.4685 (2014) · Zbl 0871.90064
[41] Reznick, B.: Sums of even powers of real linear forms. Mem. Am. Math. Soc. 96(463), viii+155 (1992) · Zbl 0762.11019
[42] Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton (1997) · Zbl 0932.90001
[43] Rothvoss, T.: The matching polytope has exponential extension complexity. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ACM, pp. 263-272 (2014) · Zbl 1315.90038
[44] Scheinerman, ER; Trenk, AN, On the fractional intersection number of a graph, Graphs Comb., 15, 341-351, (1999) · Zbl 0935.90043
[45] Shaked-Monderer, N; Bomze, IM; Jarre, F; Schachinger, W, On the cp-rank and minimal cp factorizations of a completely positive matrix, SIAM J. Matrix Anal. Appl., 34, 355-368, (2013) · Zbl 1314.15025
[46] Strassen, V, Gaussian elimination is not optimal, Numer. Math., 13, 354-356, (1969) · Zbl 0185.40101
[47] Szegedy, M.: A note on the \(ϑ \) number of Lovász and the generalized Delsarte bound. In: IEEE 35th Annual Symposium on Foundations of Computer Science, pp. 36-39 (1994) · Zbl 1312.15033
[48] Vandenberghe, L; Boyd, S, Semidefinite programming, SIAM Rev., 38, 49-95, (1996) · Zbl 0845.65023
[49] Vavasis, SA, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20, 1364-1377, (2009) · Zbl 1206.65130
[50] Winograd, S, On multiplication of 2\(× \) 2 matrices, Linear Algebra Appl., 4, 381-388, (1971) · Zbl 0225.68018
[51] Wyner, A, The common information of two dependent random variables, IEEE Trans. Inf. Theory, 21, 163-179, (1975) · Zbl 0299.94014
[52] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
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.