Compressed sensing theory explains why Lasso programs recover structured high-dimensional signals with minimax order-optimal error. Yet, the optimal choice of the program's governing parameter is often unknown in practice. It is still unclear how variation of the governing parameter impacts recovery error in compressed sensing, which is otherwise provably stable and robust. We establish a novel notion of instability in Lasso programs when the measurement matrix is identity. This is the proximal denoising setup. We prove asymptotic cusp-like behaviour of the risk as a function of the parameter choice, and illustrate the theory with numerical simulations. For example, a 0.1 underestimate of a Lasso parameter can increase the error significantly; and a 50 underestimate can cause the error to increase by a factor of 1e9. We hope that revealing parameter instability regimes of Lasso programs helps to inform a practitioner's choice.
@cite_30: Much of the progress made in image processing in the past decades can be attributed to better modeling of image content and a wise deployment of these models in relevant applications. This path of models spans from the simple l2-norm smoothness through robust, thus edge preserving, measures of smoothness (e.g. total variation), and until the very recent models that employ sparse and redundant representations. In this paper, we review the role of this recent model in image processing, its rationale, and models related to it. As it turns out, the field of image processing is one of the main beneficiaries from the recent progress made in the theory and practice of sparse and redundant representations. We discuss ways to employ these tools for various image-processing tasks and present several applications in which state-of-the-art results are obtained.
@cite_16: Signal processing relies heavily on data models; these are mathematical constructions imposed on the data source that force a dimensionality reduction of some sort. The vast activity in signal processing during the past decades is essentially driven by an evolution of these models and their use in practice. In that respect, the past decade has been certainly the era of sparse and redundant representations, a popular and highly effective data model. This very appealing model led to a long series of intriguing theoretical and numerical questions, and to many innovative ideas that harness this model to real engineering problems. The new entries recently added to the IEEE-SPL EDICS reflect the popularity of this model and its impact on signal processing research and practice. Despite the huge success of this model so far, this field is still at its infancy, with many unanswered questions still remaining. This paper1 offers a brief presentation of the story of sparse and redundant representation modeling and its impact, and outlines ten key future research directions in this field.
@cite_32: Recent research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the l_1 minimization method for identifying a sparse vector from random linear measurements. Indeed, the l_1 approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This paper provides the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.
@cite_8: We develop fast algorithms for estimation of generalized linear models with convex penalties. The models include linear regression, two-class logistic regression, and multi- nomial regression problems while the penalties include l1 (the lasso), l2 (ridge regression) and mixtures of the two (the elastic net). The algorithms use cyclical coordinate descent, computed along a regularization path. The methods can handle large problems and can also deal efficiently with sparse features. In comparative timings we find that the new algorithms are considerably faster than competing methods.
PD is a simple model that elucidates crucial properties of models in general @cite_16 . As a central model for denoising, it lays the groundwork for CS, deconvolution and inpainting problems @cite_30 . A fundamental signal recovery phase transition in CS is predicted by geometric properties of PD @cite_32 , because the minimax risk for PD is equal to the statistical dimension of the signal class @cite_8 . This quantity is a generalized version of @math introduced above.