Skip to content (access key 's')
Logo of Technion
Logo of CS Department

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Rank minimization via the gamma_2 norm
event speaker icon
Troy Lee (Columbia University)
event date icon
Sunday, 07.06.2009, 14:30
event location icon
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.