The Taub Faculty of Computer Science Events and Talks

In the affine rank minimization problem, the goal is to minimize the rank of a matrix subject to a set of affine constraints. This is in general an NP-hard problem. We study a convex relaxation of this problem where the rank objective function is replaced by the gamma_2 norm. The gamma_2 norm can be viewed as a weighted version of the trace norm and can be expressed as a semidefinite program.

We show that, given certain conditions on the constraint matrices, if the mimimal rank solution of the original problem over n-by-n matrices is r, via the gamma_2 norm relaxation one can find a rank O(rlog(n)) matrix which approximately satisfies the constraints.

Our main motivation and application comes from communication complexity. The approximation rank of a sign matrix A is the minimum rank of a real matrix which is entrywise close to A. Approximation rank is one of the strongest lower bound techniques available for randomized and quantum communication complexity, yet can be quite difficult to evaluate in practice. We show that approximation rank and the analogous approximation version of the gamma_2 norm are polynomially related, and thus are essentially equivalent for the purposes of communication complexity.

This is joint work with Adi Shraibman.