Some upper and lower bounds on PSD-rank
Tóm tắt
Positive semidefinite rank (PSD-rank) is a relatively new complexity measure on matrices, with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix M as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
Tài liệu tham khảo
Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248–264 (2013). arXiv:1111.3164
Fiorini, S., Massar, S., Pokutta, S., Tiwary, H. R. and de Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM, 16(2), 2015. Earlier version in STOC’12. arXiv:1111.0837
Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441–466 (1991)
Rothvoß, T.: The matching polytope has exponential extension complexity. In: Proceedings of 46th ACM STOC, pp. 263–272 (2014)
Lee, J., Steurer, D. and Raghavendra, P.: Lower bounds on the size of semidefinite programming relaxations. In: Proceedings of 47th ACM STOC, pp. 567–576 (2015). arXiv:1411.6317
Lee, T. and Wei, Z.: The square root rank of the correlation polytope is exponential (2014). arXiv:1411.6712
Conforti, M., Faenza, Y., Fiorini, S. and Tiwary, H.R.: Extended formulations, non-negative factorizations and randomized communication protocols. In: 2nd International Symposium on Combinatorial Optimization, pp. 129–140 (2012). arXiv:1105.4127
Zhang, S.: Quantum strategic game theory. In: Proceedings of the 3rd Innovations in Theoretical Computer Science, pp 39–59 (2012). arXiv:1012.5141
Jain, R., Shi, Y., Wei, Z., Zhang, S.: Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Trans. Inf. Theory 59, 5171–5178 (2013)
Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)
Lee, T. and Theis, D.O.: Support based bounds for positive semidefinite rank (2012). arXiv:1203.3961
Sikora, J., Varvitsiotis, A. and Wei, Z.: On the minimum dimension of a Hilbert space needed to generate a quantum correlation (2015). arXiv:1507.00213
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193–205 (2001)
Fawzi, H., Parrilo, P.: Lower bounds on nonnegative rank via nonnegative nuclear norms. Math. Program., Ser. B 153(1), 41–66 (2015). arXiv:1210.6970
Fawzi, H., Gouveia, J., Parrilo, P., Robinson, R., Thomas, R.: Positive semidefinite rank. Math. Program., Ser. B 153(1), 133–177 (2015). arXiv:1407.4095
Alon, N.: Perturbed identity matrices have high rank: proof and applications. Combin., Prob., Comput. 18, 3–15 (2009)