Computer Science – Information Theory
Scientific paper
2010-03-24
Computer Science
Information Theory
Scientific paper
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.
Tang Ao
Wang Meng
Xu Weiyu
No associations
LandOfFree
A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-555731