Abstract
This paper introduces a theoretical framework for lower-bounding "positive" ranks, such as the nonnegative rank of a matrix and the cp-rank of a completely positive matrix. By leveraging the geometry of convex cones and sum-of-squares (SOS) relaxations, the authors provide a "self-scaled" atomic norm framework. This method is computationally tractable via semidefinite programming (SDP) and theoretically superior to previous norm-based approaches, bridging the gap between continuous optimization and combinatorial graph-theoretic bounds.
Introduction
Many problems in optimization, communication complexity, and probability involve decomposing a matrix into a sum of "simple" rank-one pieces that must lie within a specific convex cone, such as the nonnegative orthant. The minimum number of such pieces is known as the nonnegative rank ($\text{rank}_+$). For symmetric matrices, a similar concept is the cp-rank.
Historically, lower bounds for these ranks have been either combinatorial (focusing on zero/nonzero patterns) or norm-based (using continuous optimization). Combinatorial bounds often ignore entry values, while norm-based bounds are frequently sensitive to diagonal scaling—a property the true ranks do not share. This paper addresses this gap by proposing a self-scaled lower-bounding technique that is both continuous and invariant to scaling.
The Self-Scaled Atomic Rank Framework
The authors define the atomic cone rank relative to a convex cone $K$ and an algebraic variety $V$ of "atoms." The rank of an element $A$ is the minimum number of atoms from $V \cap K$ that sum to $A$. The core innovation is the self-scaled lower bound, $\tau_{K,V}(A)$. Unlike standard atomic norms that use a fixed set of atoms, the self-scaled approach defines the set of feasible atoms $\mathcal{A}_+(A)$ based on the target element $A$ itself:
$$\mathcal{A}_+(A) = \{ R \in V \cap K : 0 \preceq_K R \preceq_K A \}$$
The bound $\tau$ is then defined as the gauge function of the convex hull of this set. This construction ensures that the bound is invariant under diagonal scaling, mirroring the behavior of the actual rank.
As shown in the figure, for a point $A$, the set $\text{conv } \mathcal{A}_+(A)$ defines a region such that $A$ lies on the boundary of $\tau \text{conv } \mathcal{A}_+(A)$. In this simplified 2D example, $A$ is on the boundary of $2 \text{conv } \mathcal{A}_+(A)$, yielding a lower bound of 2.
Semidefinite Programming Relaxations
Since computing $\tau$ directly is generally NP-hard, the authors propose a Semidefinite Programming (SDP) relaxation using Sum-of-Squares (SOS) techniques. For the nonnegative rank, the rank-one constraint on atoms is relaxed into linear constraints on a larger matrix. The resulting SDP, $\tau_+^{sos}(A)$, can be solved in polynomial time relative to the number of non-zero entries in $A$. This makes the approach practically applicable to problems where exact rank computation is infeasible.
Key Results and Theoretical Insights
The paper demonstrates that $\tau_+$ is theoretically dominant, proving $\tau_+(A) \ge \frac{N^*(A)}{N(A)}$ for any monotone positively homogeneous function $N$. Furthermore, it establishes a bridge to graph theory: $\tau_+$ acts as a continuous version of the fractional rectangle cover number, and its SOS relaxation is a continuous analogue of the Lovász $\vartheta$ number applied to the matrix's rectangle graph.
Key results include:
- Nonnegative Rank: For diagonal matrices, $\tau_+$ exactly recovers the number of non-zero entries (sparsity), which many other continuous bounds fail to do.
- CP-Rank: The bound $\tau_{cp}^{sos}(A) \ge \text{rank}(A)$ is a significant result, as the standard rank is a common but often weak lower bound for cp-rank.
- Numerical Success: In the "nested rectangles" problem, the $\tau_+^{sos}$ bound successfully identifies regions where a triangle cannot be sandwiched between two rectangles, matching known geometric truths.
Conclusion and Future Work
The self-scaled atomic norm framework provides a robust and computationally feasible method for lower-bounding positive ranks. While the SDP size can be a limiting factor for very large dense matrices ($|supp(A)| \times |supp(A)|$), the theoretical properties—particularly scaling invariance and the connection to graph-theoretic bounds—mark a significant advancement. Future work remains in extending this logic to other complexity measures, such as psd rank, which does not fit perfectly into the current atomic framework.
Summary updated