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_24: This note provides a condition under which lscr1 minimization (also known as basis pursuit) can recover short linear combinations of complex vectors chosen from fixed, overcomplete collection. This condition has already been established in the real setting by Fuchs, who used convex analysis. The proof given here is more direct
@cite_14: Motivated by the theoretical and practical results in compressed sensing, efforts have been undertaken by the inverse problems community to derive analogous results, for instance linear convergence rates, for Tikhonov regularization with l1-penalty term for the solution of ill-posed equations. Conceptually, the main difference between these two fields is that regularization in general is an uncon strained optimization problem, while in compressed sensing a constrained one is used. Since the two methods have been developed in two different communities, the theoretical approaches to them appear to be rather different: In compressed sensing, the restricted isometry property seems to be central for proving linear convergence rates, whereas in regularization theory range or source conditions are imposed. The paper gives a common meaning to the seemingly different conditions and puts them into perspective with the conditions from the respective other community. A particularly important observation is that the range condition together with an injectivity condition is weaker than the restricted isometry property. Under the weaker conditions, linear convergence rates can be proven for compressed sensing and for Tikhonov regularization. Thus existing results from the literature can be improved based on a unified analysis. In particular, the range condition is shown to be the weakest possible condition that permits the derivation of linear convergence rates for Tikhonov regularization with a priori parameter choice. © 2010 Wiley Periodicals, Inc.
@cite_13: The minimum @math -norm solution to an underdetermined system of linear equations @math , is often, remarkably, also the sparsest solution to that system. In this paper, we provide a and condition for @math to be identifiable for a large set of matrices @math ; that is to be the unique sparsest solution to the @math -norm minimization problem. Furthermore, we prove that this sparsest solution is stable under a reasonable perturbation of the observations @math . We also propose an efficient semi-greedy algorithm to check our condition for any vector @math . We present numerical experiments showing that our condition is able to predict almost perfectly all identifiable solutions @math , whereas other previously proposed criteria are too pessimistic and fail to identify properly some identifiable vectors @math . Beside the theoretical proof, this provides empirical evidence to support the sharpness of our condition.
@cite_17: This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f spl isin C sup N and a randomly chosen set of frequencies spl Omega . Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set spl Omega ? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)= spl sigma sub spl tau spl isin T f( spl tau ) spl delta (t- spl tau ) obeying |T| spl les C sub M spl middot (log N) sup -1 spl middot | spl Omega | for some constant C sub M >0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N sup -M ), f can be reconstructed exactly as the solution to the spl lscr sub 1 minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C sub M which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T| spl middot logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N sup -M ) would in general require a number of frequency samples at least proportional to |T| spl middot logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.
Work @cite_17 considers problem with complex-valued quantities and @math equal to a down-sampled discrete Fourier operator, for which it establishes both the necessity and sufficiency of Condition 1 to the solution uniqueness of . Their proof uses the Hahn-Banach separation theorem and the Parseval formula. Work @cite_24 lets the entries of matrix @math and vector @math in problem have complex values and gives a sufficient condition for its solution uniqueness. In regularization theory, Condition 1 is used to derive linear error bounds under the name of range or source conditions in @cite_14 , which shows the necessity and sufficiency of Condition 1 for solution uniqueness of in a Hilbert-space setting. More recently, @cite_13 constructs the set and then states that the set of vectors that can be recovered by problem is exactly characterized by the closure of @math if the measurement matrix @math satisfies the so-called (GP) condition, namely, for any sign vector @math , the set of columns @math of @math satisfying that any @math -dimensional affine subspace of @math , @math , contains at most @math points from the set @math . This paper claims that the result holds without the GP condition.