Journal article
A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
IEEE transactions on signal processing, Vol.59(3), pp.1007-1016
03/24/2010
DOI: 10.1109/TSP.2010.2089624
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.
Details
- Title: Subtitle
- A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
- Creators
- Meng WangWeiyu XuAo Tang
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on signal processing, Vol.59(3), pp.1007-1016
- DOI
- 10.1109/TSP.2010.2089624
- ISSN
- 1053-587X
- eISSN
- 1941-0476
- Language
- English
- Date published
- 03/24/2010
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083822602771
Metrics
23 Record Views