The Experts below are selected from a list of 10473 Experts worldwide ranked by ideXlab platform
Yun-bin Zhao - One of the best experts on this subject based on the ideXlab platform.
-
Equivalence and Strong Equivalence Between the Sparsest and Least $$\ell _1$$ ℓ
Journal of the Operations Research Society of China, 2014Co-Authors: Yun-bin ZhaoAbstract:Many practical problems can be formulated as $$\ell _0$$ ℓ 0 -minimization problems with nonnegativity constraints, which seek the sparsest Nonnegative Solutions to underdetermined linear systems. Recent study indicates that $$\ell _1$$ ℓ 1 -minimization is efficient for solving $$\ell _0$$ ℓ 0 -minimization problems. From a mathematical point of view, however, the understanding of the relationship between $$\ell _0$$ ℓ 0 - and $$\ell _1$$ ℓ 1 -minimization remains incomplete. In this paper, we further address several theoretical questions associated with these two problems. We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to admit a unique least $$\ell _1$$ ℓ 1 -norm Nonnegative Solution. This condition leads naturally to the so-called range space property (RSP) and the “full-column-rank” property, which altogether provide a new and broad understanding of the equivalence and the strong equivalence between $$ \ell _0$$ ℓ 0 - and $$\ell _1$$ ℓ 1 -minimization. Motivated by these results, we introduce the concept of “RSP of order $$K$$ K ” that turns out to be a full characterization of uniform recovery of all $$K$$ K -sparse Nonnegative vectors. This concept also enables us to develop a nonuniform recovery theory for sparse Nonnegative vectors via the so-called weak range space property.
-
Equivalence and Strong Equivalence between Sparsest and Least $\ell_1$-Norm Nonnegative Solutions of Linear Systems and Their Application
arXiv: Optimization and Control, 2013Co-Authors: Yun-bin ZhaoAbstract:Many practical problems can be formulated as l0-minimization problems with nonnegativity constraints, which seek the sparsest Nonnegative Solutions to underdetermined linear systems. Recent study indicates that l1-minimization is efficient for solving some classes of l0-minimization problems. From a mathematical point of view, however, the understanding of the relationship between l0- and l1-minimization remains incomplete. In this paper, we further discuss several theoretical questions associated with these two problems. For instance, how to completely characterize the uniqueness of least l1-norm Nonnegative Solutions to a linear system, and is there any alternative matrix property that is different from existing ones, and can fully characterize the uniform recovery of K-sparse Nonnegative vectors? We prove that the fundamental strict complementarity theorem of linear programming can yield a necessary and sufficient condition for a linear system to have a unique least l1-norm Nonnegative Solution. This condition leads naturally to the so-called range space property (RSP) and the `full-column-rank' property, which altogether provide a broad understanding of the relationship between l0- and l1-minimization. Motivated by these results, we introduce the concept of the `RSP of order K' that turns out to be a full characterization of the uniform recovery of K-sparse Nonnegative vectors. This concept also enables us to develop certain conditions for the non-uniform recovery of sparse Nonnegative vectors via the so-called weak range space property.
Ao Tang - One of the best experts on this subject based on the ideXlab platform.
-
A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
IEEE Transactions on Signal Processing, 2011Co-Authors: Meng Wang, Weiyu Xu, Ao TangAbstract: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.
Yuhua Sun - One of the best experts on this subject based on the ideXlab platform.
-
On the uniqueness of Nonnegative Solutions of differential inequalities with gradient terms on Riemannian manifolds
Communications on Pure & Applied Analysis, 2015Co-Authors: Yuhua SunAbstract:We investigate the uniqueness of Nonnegative Solutions to the following differential inequality \begin{eqnarray} div(A(x)|\nabla u|^{m-2}\nabla u)+V(x)u^{\sigma_1}|\nabla u|^{\sigma_2}\leq0, \tag{1} \end{eqnarray} on a noncompact complete Riemannian manifold, where $A, V$ are positive measurable functions, $m>1$, and $\sigma_1$, $\sigma_2\geq0$ are parameters such that $\sigma_1+\sigma_2>m-1$. Our purpose is to establish the uniqueness of Nonnegative Solution to (1) via very natural geometric assumption on volume growth.
-
On Nonnegative Solutions of the Inequality Δ u + uσ ≤ 0 on Riemannian Manifolds
Communications on Pure and Applied Mathematics, 2013Co-Authors: Alexander Grigor'yan, Yuhua SunAbstract:We study the uniqueness of a Nonnegative Solution of the differential inequality (*)Δu+uσ≤0 on a complete Riemannian manifold, where σ > 1 is a parameter. We prove that if, for some x0 ∊ M and all large enough r volB(x0,r)≤Crplnqr, where p=2σσ−1,q=1σ−1, and B(x,r) is a geodesic ball, then the only Nonnegative Solution of (*) is identically 0. We also show the sharpness of the above values of the exponents p,q. © 2014 Wiley Periodicals, Inc.
Meng Wang - One of the best experts on this subject based on the ideXlab platform.
-
A Unique “Nonnegative” Solution to an Underdetermined System: From Vectors to Matrices
IEEE Transactions on Signal Processing, 2011Co-Authors: Meng Wang, Weiyu Xu, Ao TangAbstract: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.
Stephen P. Huestis - One of the best experts on this subject based on the ideXlab platform.
-
Smallest Nonnegative Solutions to linear inverse problems
SIAM Review, 1992Co-Authors: Stephen P. HuestisAbstract:Physical considerations often dictate nonnegativity for Solutions to linear geophysical inverse problems. Applying the Lagrange multiplier theorem, the nature of that Nonnegative Solution is deduced, which is smallest in the 2-norm sense. The two-data inverse problem of inference of a planetary density profile, from measurements of mass and moment-of-inertia, serves to show the existence of nonextremal, Nonnegative Solutions that also satisfy the Lagrange multiplier condition. Numerical exploration indicates which of this family is the true extremal Solution.
