Search

The nonnegative rank of a matrix A is the smallest integer r such that A can be written as the sum of r rank-one nonnegative matrices. The nonnegative rank has received a lot of attention recently due to its application in optimization, probability and communication complexity. In this paper we study a class of atomic rank functions defined on a convex cone which generalize several notions of "positive" ranks such as nonnegative rank or cp-rank (for completely positive matrices). The main contribution of the paper is a new method to obtain lower bounds for such ranks which improve on previously known bounds. Additionally the bounds we propose can be computed by semidefinite programming. The idea of the lower bound relies on an atomic norm approach where the atoms are self-scaled according to the vector (or matrix, in the case of nonnegative rank) of interest. This results in a lower bound that is invariant under scaling and that is at least as good as other existing norm-based bounds. We mainly focus our attention on the two important cases of nonnegative rank and cp-rank where our bounds satisfying interesting properties: For the nonnegative rank we show that our lower bound can be interpreted as a non-combinatorial version of the fractional rectangle cover number, while the sum-of-squares relaxation is closely related to the Lov\'asz theta number of the rectangle graph of the matrix. We also prove that the lower bound inherits many of the structural properties satisfied by the nonnegative rank such as invariance under diagonal scaling, subadditivity, etc. We also apply our method to obtain lower bounds on the cp-rank for completely positive matrices. In this case we prove that our lower bound is always greater than or equal the plain rank lower bound, and we show that it has interesting connections with combinatorial lower bounds based on edge-clique cover number.

Let M∈R[superscript p×q] be a nonnegative matrix. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A[subscript i],B[subscript j] of size k×k such that M[subscript ij]=trace(A[subscript i]B[subscript j]). The psd rank has many appealing geometric interpretations, including semidefinite representations of polyhedra and information-theoretic applications. In this paper we develop and survey the main mathematical properties of psd rank, including its geometry, relationships with other rank notions, and computational and algorithmic aspects., United States. Air Force Office of Scientific Research (AFOSR FA9550-11-1-0305)

We consider the solution of strongly monotone variational inequalities of the form \(F(x^*)'(x-x^*)\ge 0\), for all \(x\in X\). We focus on special structures that lend themselves to sampling, such as when \(X\) is the intersection of a large number of sets, and/or \(F\) is an expected value or is the sum of a large number of component functions. We propose new methods that combine elements of incremental constraint projection and stochastic gradient. These methods are suitable for problems involving large-scale data, as well as problems with certain online or distributed structures. We analyze the convergence and the rate of convergence of these methods with various types of sampling schemes, and we establish a substantial rate of convergence advantage for random sampling over cyclic sampling., United States. Air Force (Grant FA9550-10-1-0412)