Troy Lee (Columbia University)
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.