zbMATH — the first resource for mathematics

On the geometric interpretation of the nonnegative rank. (English) Zbl 1258.65039
A new quantity called the restricted nonnegative rank, whose computation amounts to solving a problem in computational geometry consisting of finding a polytope nested between two given polytopes is introduced. This allows characterizing its computational complexity. The geometric interpretation and the relationship between the nonnegative rank and the restricted nonnegative rank let to derive new improved lower bounds for the nonnegative rank, in particular for slack matrices and linear Euclidean distance matrices. This allows obtaining counter-examples to two conjectures of Beasley and Laffey, namely, it is shown that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.

65F30 Other matrix algorithms (MSC2010)
15A23 Factorization of matrices
15B48 Positive matrices and their generalizations; cones of matrices
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
52B11 \(n\)-dimensional polytopes
65D99 Numerical approximation and computational geometry (primarily algorithms)
90C27 Combinatorial optimization
Full Text: DOI arXiv
[1] Aggarwal, A.; Booth, H.; O’Rourke, J.; Suri, S., Finding minimal convex nested polygons, Inform. comput., 83, 1, 98-110, (1989) · Zbl 0679.68068
[2] S. Arora, R. Ge, R. Kannan, A. Moitra, Computing a nonnegative matrix factorization – provably, 2011. arXiv:1111.0952v1. · Zbl 1286.15014
[3] Beasley, L.; Laffey, T., Real rank versus nonnegative rank, Linear algebra appl., 431, 12, 2330-2335, (2009) · Zbl 1185.15002
[4] Ben-Tal, A.; Nemirovski, A., On polyhedral approximations of the second-order cone, Math. oper. res., 26, 2, 193-205, (2001) · Zbl 1082.90133
[5] Berman, A.; Plemmons, R., Rank factorization of nonnegative matrices, SIAM rev., 15, 3, 655, (1973)
[6] Berman, A.; Shaked-Monderer, N., Completely positive matrices, (2003), World Scientific Publishing · Zbl 1030.15022
[7] Berry, M.; Browne, M.; Langville, A.; Pauca, V.; Plemmons, R., Algorithms and applications for approximate nonnegative matrix factorization, Comput. stat. data anal., 52, 155-173, (2007) · Zbl 1452.90298
[8] J. Bhadury, R. Chandrasekaran, Finding the set of all minimal nested convex polygons, in: Proceedings of the 8th Canadian Conference on Computational Geometry, 1996, pp. 26-31.
[9] J. Boardman, Geometric mixture analysis of imaging spectrometry data, in: Proc. IGARSS 4, Pasadena, Calif, 1994, pp. 2369-2371.
[10] Carlini, E.; Rapallo, F., Probability matrices, non-negative rank, and parameterization of mixture models, Linear algebra appl., 433, 424-432, (2010) · Zbl 1196.15034
[11] M. Chu, On the nonnegative rank of Euclidean distance matrices, II. http://www4.ncsu.edu/∼mtchu/Research/Papers/letter04.pdf, 2010. · Zbl 1194.15003
[12] Chu, M.; Lin, M., Low-dimensional polytope approximation and its applications to nonnegative matrix factorization, SIAM J. sci. comput., 30, 3, 1131-1155, (2008) · Zbl 1168.65019
[13] Cichocki, A.; Zdunek, R.; Amari, S., Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization, (), 169-176 · Zbl 1172.94390
[14] K. Clarkson, Algorithms for polytope covering and approximation, in: Proceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 246-252.
[15] Cohen, J.; Rothblum, U., Nonnegative ranks, decompositions and factorization of nonnegative matrices, Linear algebra appl., 190, 149-168, (1993) · Zbl 0784.15001
[16] Conforti, M.; Cornuéjols, G.; Zambelli, G., Extended formulations in combinatorial optimization, 4OR: quart. J. oper. res., 10, 1, 1-48, (2010) · Zbl 1219.90193
[17] Craig, M., Minimum-volume transforms for remotely sensed data, IEEE trans. geosci. remote sens., 32, 3, 542-552, (1994)
[18] G. Das, Approximation Schemes in Computational Geometry, Ph.D. thesis, University of Wisconsin-Madison, 1990.
[19] Das, G.; Goodrich, M., On the complexity of optimization problems for three-dimensional convex polyhedra and decision trees, Comput. geom. theory appl., 8, 123-137, (1997) · Zbl 0881.68121
[20] G. Das, D. Joseph, The complexity of minimum convex nested polyhedra, in: Proc. of the 2nd Canadian Conference on Computational Geometry, 1990, pp. 296-301.
[21] D. de Caen, D. Gregory, N. Pullman, The boolean rank of zero-one matrices, in: Proc. 3rd Caribbean Conference on Combinatorics and Computing, 1981, pp. 169-173. · Zbl 0496.20052
[22] Donoho, D.; Stodden, V., When does non-negative matrix factorization give a correct decomposition into parts?, ()
[23] N. Gillis, Nonnegative Matrix Factorization: Complexity, Algorithms and Applications, Ph.D. thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2011.
[24] N. Gillis, F. Glineur, Nonnegative Factorization and The Maximum Edge Biclique Problem, CORE Discussion paper 2008/64, 2008.
[25] Gillis, N.; Glineur, F., Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization, Neural comput., 24, 1085-1105, (2012)
[26] Gillis, N.; Plemmons, R., Dimensionality reduction, classification, and spectral mixture analysis using nonnegative underapproximation, Opt. eng., 50, 027001, (2011)
[27] F. Glineur, Computational experiments with a linear approximation of second order cone optimization, Image Technical Report 0001, Service de Mathématique et de Recherche Opérationnelle, Faculté Polytechnique de Mons, 2000.
[28] M. Goemans, Smallest compact formulation for the permutahedron,Talk at ISMP, Chicago, 2009. · Zbl 1322.90048
[29] H. Hazewinkel, On Positive Vectors, Positive Matrices and the Specialization Ordering, Tech. Rep., CWI Report PM-R8407, 1984.
[30] Ifarraguerri, A.; Chang, C.-I., Multispectral and hyperspectral image analysis with convex cones, IEEE trans. geosci.remote sens., 37, 2, 756-770, (1999)
[31] Kaibel, V., Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[32] V. Kaibel, K. Pashkovich, Constructing extended formulations from reflection relations, in: IPCO’11 Proc. of the 15th Int. Conf. on Integer Programming and Combinatorial Optimization, 2010. · Zbl 1317.90190
[33] Klingenberg, B.; Curry, J.; Dougherty, A., Non-negative matrix factorization: ill-posedness and a geometric algorithm, Pattern recognition, 42, 5, 918-928, (2009) · Zbl 1178.68501
[34] N. Krislock, H. Wolkowicz, Euclidean distance matrices and applications, in: Miguel Anjos, Jean Lasserre (Eds.), Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, 2011. · Zbl 1334.90109
[35] Lee, D.; Seung, H., Learning the parts of objects by nonnegative matrix factorization, Nature, 401, 788-791, (1999) · Zbl 1369.68285
[36] T. Lee, A. Shraibman, Lower bounds in communication complexity, Foundations and Trends in Theoretical Computer Science, 2009.
[37] Lin, M.; Chu, M., On the nonnegative rank of Euclidean distance matrices, Linear algebra appl., 433, 3, 681-689, (2010) · Zbl 1194.15003
[38] Mitchell, J.; Suri, S., Separation and approximation of polyhedral surfaces, Oper. res. lett., 11, 255-259, (1992)
[39] Orlin, J., Contentment in graph theory: covering graphs with cliques, Indag. math. (Proceedings), 80, 5, 406-424, (1977) · Zbl 0374.05041
[40] Peeters, R., The maximum edge biclique problem is NP-complete, Discrete appl. math., 131, 3, 651-654, (2003) · Zbl 1026.68068
[41] Thomas, L., Rank factorization of nonnegative matrices, SIAM rev., 16, 3, 393-394, (1974)
[42] Vavasis, S., On the complexity of nonnegative matrix factorization, SIAM J. optim., 20, 1364-1377, (2009) · Zbl 1206.65130
[43] Wang, C., Finding minimal nested polygons, Bit, 31, 230-236, (1991) · Zbl 0726.68084
[44] Watts, V., Fractional biclique covers and partitions of graphs, Electron. J. combin., 13, #R74, (2006) · Zbl 1096.05043
[45] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, Comput. system sci., 43, 441-466, (1991) · Zbl 0748.90074
[46] Ziegler, G., Lectures on polytopes, (1995), Springer-Verlag · Zbl 0823.52002
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.