When solving an underdetermined linear system $Ax = b$, we confront a fundamental geometric reality: there are more unknowns than equations. The measurement matrix $A$ possesses a null space containing infinitely many non-zero vectors. If we have a true signal $x^\star$, any vector $v$ in the null space can be added to it to yield an alternative solution $x^\star + v$ that produces the exact same measurements ($A(x^\star + v) = b$).
This ambiguity is only possible because the positive and negative components of $v$ can perfectly balance each other out when multiplied by $A$. This is destructive interference. To isolate the true signal, traditional compressed sensing forces $x$ to be sparse, using $\ell_1$-minimization to penalize non-zero entries and find the solution with the smallest footprint.
But what happens if we know a priori that the signal is strictly non-negative ($x \ge 0$)? This simple constraint radically alters the geometry of the problem. If the components of the signal can only add up and never cancel out, the entire landscape of inverse problems simplifies.
The Singleton Property: Collapsing the Feasible Set
The most striking consequence of eliminating destructive interference is that the feasible set of non-negative solutions—the polytope defined by $\{x \ge 0 : Ax = b\}$—can collapse into a single point, a singleton.
Meng Wang 0003 et al. demonstrated that for certain underdetermined systems, this nonnegativity constraint acts as a standalone mechanism for uniqueness. Under specific matrix conditions, the feasible set shrinks to a singleton containing only the true signal. This means you do not even need a sparsity-inducing objective function like $\ell_1$-minimization; any algorithm capable of finding a valid non-negative vector is guaranteed to recover the exact true signal.
Standard Feasible Set (Line/Affine Space) Non-negative Feasible Set
\ \
\ x* (True Signal) \ x* (Feasible region
\ \ collapses to a
\ • single point!)
\ \
This equivalence between optimization success and geometric uniqueness was further unfurled by M. Amin Khajehnejad et al.. They showed that for sparse measurement matrices with non-negative entries and constant column sums, the success of $\ell_1$ optimization is identical to the existence of a unique vector in the non-negative constraint set. Because the geometry itself enforces uniqueness, alternative and computationally simpler objectives—such as $\ell_2$ minimization over the non-negative constraint set—will also successfully recover the exact signal.
Bypassing traditional Compressed Sensing Limits
In classical compressed sensing, proving that a matrix can recover sparse signals requires strict conditions like the Restricted Isometry Property (RIP). RIP guarantees that no sparse vector accidentally falls into the null space of $A$. However, designing and verifying RIP matrices is notoriously difficult.
Nonnegativity allows us to bypass these rigid structural requirements entirely. Because basis vectors cannot cancel each other out, sparse recovery becomes possible for a much broader class of matrices. Aditya Bhaskara et al. showed that when both the system matrix and the solution vector are non-negative, greedy and combinatorial optimization strategies can find approximate sparse solutions without requiring RIP.
To formalize how this geometry bridges the gap between intractable combinatorial searches and practical algorithms, Linxia Qin et al. introduced the "nonnegative restricted property." When a measurement matrix satisfies this condition, the linear programming relaxation of the sparse recovery problem is theoretically guaranteed to yield the exact and unique non-negative solution, providing a reliable foundation for applications like DNA microarrays.
Breaking the Separation Limit in Super-Resolution
The power of nonnegativity becomes even more visible when moving from discrete vectors to continuous measures, such as resolving point sources (spikes) from blurred, low-resolution observations.
In standard super-resolution, if two spikes are located too close together, their blurred representations merge into a single blob. If the spikes can have both positive and negative amplitudes, they can cancel each other out, making it impossible to distinguish a pair of close, large spikes from noise. To prevent this, mathematical frameworks like Total Variation minimization or atomic norm minimization require a strict minimum separation distance between sources to guarantee exact recovery.
Signed Spikes (Can cancel out) Positive Spikes (Cannot cancel)
/\ /\ /\
_____/ \_____/\_____ _____/ \/ \_____
\ / Merged Blob
\/ (Peak shape changes predictably)
When sources are known to be strictly positive, this physical barrier vanishes. Because positive spikes cannot cancel each other out, any change in their proximity creates a predictable, monotonic change in the observed blurred signal.
Shai Dekel et al. demonstrated that incorporating a non-negativity constraint allows for the complete relaxation of these strict spatial separation requirements; exact recovery can be achieved based on signal sparsity alone.
Providing a rigorous asymptotic analysis of this phenomenon, Quentin Denoyelle et al. proved that under the Beurling-LASSO (BLASSO) framework, the minimum separation distance can safely shrink to zero. In a follow-up work, the authors confirmed that enforcing positivity alters the optimization geometry so fundamentally that perfect support recovery—identifying the exact number and locations of spikes—is guaranteed at arbitrarily small distances, provided the signal-to-noise ratio scales sufficiently to counter the blur.
This geometric guarantee translates directly into computational efficiency. Maxime Ferreira Da Costa et al. leveraged this lack of spatial separation requirements to design a compressed atomic norm minimization (C-ANM) algorithm. By exploiting the positivity constraint, they reformulate the problem using a lower-dimensional linear matrix inequality, achieving massive computational speedups in applications like direction finding without sacrificing exact recovery.
Straightening Non-Convex Landscapes
Beyond linear systems and continuous measures, nonnegativity can even untangle non-convex optimization landscapes. Consider a bilinear inversion problem, where the goal is to recover two sparse vectors from their entrywise product. This problem is inherently non-convex, bounded by complex hyperbolic constraints that typically require expensive high-dimensional "lifting" or highly sensitive initializations to solve.
Alireza Aghasi et al. demonstrated that simply knowing the signs of the signals—such as nonnegativity in imaging—allows these non-convex hyperbolic constraints to relax into a single convex branch. This geometric simplification allows practitioners to deploy standard, efficient convex optimization tools directly in the problem's original dimensions.
Across all these domains, the intuition remains unified: when you forbid components from canceling each other out, you strip the null space of its power to deceive. The feasible set collapses, separation limits dissolve, and non-convexities straighten out—leaving a direct, unique path to the true signal.
Key Foundational Work
Linear Program Relaxation of Sparse Nonnegative Recovery in Compressive Sensing Microarrays (2012) — contributed 3 concept elements to this direction.
Sparse Recovery of Nonnegative Signals With Minimal Expansion. (2011) — contributed 2 concept elements to this direction.
A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices (2011) — contributed 2 concept elements to this direction.