%0 Journal Article
%T A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
%A Meng Wang
%A Weiyu Xu
%A Ao Tang
%J Mathematics
%D 2010
%I arXiv
%R 10.1109/TSP.2010.2089624
%X 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.
%U http://arxiv.org/abs/1003.4778v1