This paper shows that the solutions to various 1-norm minimization problems are unique if, and only if, a common set of conditions are satisfied. This result applies broadly to the basis pursuit model, basis pursuit denoising model, Lasso model, as well as certain other 1-norm related models. This condition is previously known to be sufficient for the basis pursuit model to have a unique solution. Indeed, it is also necessary, and applies to a variety of 1-norm related models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically. The proof technique is based on linear programming strong duality and strict complementarity results.
@cite_19: The purpose of this contribution is to extend some recent results on sparse representations of signals in redundant bases developed in the noise-free case to the case of noisy observations. The type of question addressed so far is as follows: given an (n,m)-matrix A with m>n and a vector b=Axo, i.e., admitting a sparse representation xo, find a sufficient condition for b to have a unique sparsest representation. The answer is a bound on the number of nonzero entries in xo. We consider the case b=Axo+e where xo satisfies the sparsity conditions requested in the noise-free case and e is a vector of additive noise or modeling errors, and seek conditions under which xo can be recovered from b in a sense to be defined. The conditions we obtain relate the noise energy to the signal level as well as to a parameter of the quadratic program we use to recover the unknown sparsest representation. When the signal-to-noise ratio is large enough, all the components of the signal are still present when the noise is deleted; otherwise, the smallest components of the signal are themselves erased in a quite rational and predictable way
@cite_10: The purpose of this contribution is to generalize some recent results on sparse representations of signals in redundant bases. The question that is considered is the following: given a matrix A of dimension (n,m) with m>n and a vector b=Ax, find a sufficient condition for b to have a unique sparsest representation x as a linear combination of columns of A. Answers to this question are known when A is the concatenation of two unitary matrices and either an extensive combinatorial search is performed or a linear program is solved. We consider arbitrary A matrices and give a sufficient condition for the unique sparsest solution to be the unique solution to both a linear program or a parametrized quadratic program. The proof is elementary and the possibility of using a quadratic program opens perspectives to the case where b=Ax+e with e a vector of noise or modeling errors.
To our knowledge, there are few conditions addressing the solution uniqueness of problems --. The following conditions in @cite_10 , @cite_19 are sufficient for @math to the unique minimizer of for @math : However, they are not necessary as demonstrated by the following example. Let A=, b=, =1 and consider solving the Lasso problem, which is a special case of problem : 1 2 |Ax-b |_2^2+ |x |_1. One gets the solution @math and @math . However, the inequality in condition ) holds with equality. In general, conditions becomes necessary in case @math happens to be a full rank square matrix. This assumption, however, does not apply to a sparse solution @math . Nevertheless, we summarize the result in the following corollary, whose proof is given at the end of Section .