A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices

Abstract

This paper investigates the uniqueness of a nonnegative vector solution and the uniqueness of a positive semidefinite matrix solution to underdetermined linear systems. A vector solution is the unique solution to an underdetermined linear system only if the measurement matrix has a row-span intersecting the positive orthant. Focusing on two types of binary measurement matrices, Bernoulli 0-1 matrices and adjacency matrices of general expander graphs, we show that, in both cases, the support size of a unique nonnegative solution can grow linearly, namely O(n), with the problem dimension n. We also provide closed-form characterizations of the ratio of this support size to the signal dimension. For the matrix case, we show that under a necessary and sufficient condition for the linear compressed observations operator, there will be a unique positive semidefinite matrix solution to the compressed linear observations. We further show that a randomly generated Gaussian linear compressed observations operator will satisfy this condition with overwhelmingly high probability.

References in corpus (1)

• Sparse Recovery of Positive Signals with Minimal Expansion

Cited by in corpus (25)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Graph topology inference based on sparsifying transform learning
• Active Sensing of Social Networks
• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
• Perfect Recovery Conditions For Non-Negative Sparse Modeling
• Systems of random linear equations and the phase transition in MacArthur's resource-competition model
• The Lawson-Hanson Algorithm with Deviation Maximization: Finite Convergence and Sparse Recovery
• Error Correction Codes for COVID-19 Virus and Antibody Testing: Using Pooled Testing to Increase Test Reliability
• Development of hp-inverse model by using generalized polynomial chaos
• Sparse Non-Negative Recovery from Biased Subgaussian Measurements using NNLS
• On non-negative solutions to large systems of random linear equations
• A Scalable and Statistically Robust Beam Alignment Technique for mm-Wave Systems
• Regularization-free estimation in trace regression with symmetric positive semidefinite matrices
• RIDS: Robust Identification of Sparse Gene Regulatory Networks from Perturbation Experiments
• Machine Learning for Geometrically-Consistent Angular Spread Function Estimation in Massive MIMO
• Oracle inequalities for sign constrained generalized linear models
• Controllability of Linear Positive Systems: An Alternative Formulation
• Recovering Sparse Nonnegative Signals via Non-convex Fraction Function Penalty
• Equivalence and Strong Equivalence between Sparsest and Least ${\ell }_1$-Norm Nonnegative Solutions of Linear Systems and Their Application
• Recovering Non-negative and Combined Sparse Representations
• Critical Parameter Values and Reconstruction Properties of Discrete Tomography: Application to Experimental Fluid Dynamics
• Efficient Tuning-Free ${\ell }_1$-Regression of Nonnegative Compressible Signals
• Average Case Recovery Analysis of Tomographic Compressive Sensing
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets
• Irreducible infeasible subsystems of semidefinite systems