Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Self-scaled bounds for atomic cone ranks: applications to nonnegative
  rank and cp-rank   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.

31
The categories of this paper are: ao-sci
30
The categories of this paper are: q-alg
29
The categories of this paper are: funct-an
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
37
The categories of this paper are: supr-con
24
The categories of this paper are: dg-ga
36
The categories of this paper are: cmp-lg
18
The categories of this paper are: econ
14
The categories of this paper are: math-ph
4
The categories of this paper are: cond-mat
19
The categories of this paper are: eess
28
The categories of this paper are: alg-geom
34
The categories of this paper are: chem-ph
6
The categories of this paper are: astro-ph
21
The categories of this paper are: adap-org