Theory Seminar: Rank minimization via the gamma_2 norm

Troy Lee (Columbia University)

Sunday, 07.06.2009, 14:30

Room 337-8 Taub Bld.

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.

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.