Analysis versus synthesis in signal priors

By Michael Elad, Peyman Milanfar, Ron Rubinstein. European Signal Processing Conference, 2006

757 citations recorded by the source corpus.

The concept of prior probability for signals plays a key role in the successful solution of many inverse problems. Much of the literature on this topic can be divided between analysis-based and synthesis-based priors. Analysis-based priors assign probability to a signal through various forward measurements of it, while synthesis-based priors seek a reconstruction of the signal as a combination of atom signals. The algebraic similarity between the two suggests that they could be strongly related; however, in the absence of a detailed study, contradicting approaches have emerged. While the computationally intensive synthesis approach is receiving ever-increasing attention and is notably preferred, other works hypothesize that the two might actually be much closer, going as far as to suggest that one can approximate the other. In this paper we describe the two prior classes in detail, focusing on the distinction between them. We show that although in the simpler complete and undercomplete formulations the two approaches are equivalent, in their overcomplete formulation they depart. Focusing on the ℓ1 case, we present a novel approach for comparing the two types of priors based on high-dimensional polytopal geometry. We arrive at a series of theoretical and numerical results establishing the existence of an unbridgeable gap between the two.

Subfields: Computational Mechanics, Mechanics of Materials, Signal Processing

View Paper: https://www.semanticscholar.org/paper/c52128dc34d76cc7e2362cba4d57a5cd74ee8603

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Mechanics of Materials

In Signal Processing

Citations in the corpus

Compressed Sensing with Coherent and Redundant Dictionaries (2010, neutral): “This theoretical gap is also demonstrated by numerical simulations in [21], which show that the two methods perform very differently on large families of signals.”
Enhancing Sparsity by Reweighted ℓ1 Minimization (2007, background): “Moreover, in some cases the analysis-based reconstruction may in fact be superior, a phenomenon which is not very well understood; see [54] for some insights.”
Non-local Color Image Denoising with Convolutional Neural Networks (2016, background): “For general inverse problems, the latter regularization strategy has been reported to lead to better reconstruction results [9, 35] and therefore is mostly preferred.”
Multi-Wiener SURE-LET Deconvolution (2013, neutral): “2) Transform-domain sparsity constraints [12]–[16]: Here, the coefficients of a frame-based representation of the original image are estimated under a sparsity-inducing regularizer such as the 1 -norm [17].”
Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model (2013, background): “This case of analysis dictionary training is a challenging problem, which has recently started to attract attention [13]–[16].”
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery (2009, methodology): “This is particularly interesting because recent work [31] suggests the potential advantage of this analysis-based approach over the classical basis pursuit in solving important inverse problems [31].”
Modern regularization methods for inverse problems (2018, methodology): “ormal system, this is equivalent to the synthesis formulation, which is based on writing J(u) = X i jc ij where u= X i c i˚ i: (17) Note that in general the two formulations may dier for frames (cf. [160]). In the analysis formulation we can eectively dene the variational problem on the coe- cient v”
The solution path of the generalized lasso (2010, background): “Though attention has traditionally been centered around synthesis, a recent paper by [12] suggests that synthesis may be too sensitive, and shows that it can be outperformed by its analysis counterpart.”
Templates for convex cone problems with applications to sparse signal recovery (2010, background): “When W is not orthogonal, the two approaches are generally different in non-trivial ways, and furthermore, the solutions to synthesis may be overly sensitive to the data [27].”
Learning Sparse FRAME Models for Natural Image Patterns (2014, methodology): “The proposed model (and the original FRAME model) is related to “analysis priors” developed in the last few years by the sparse modeling community (Nama et al. 2013; Elad et al. 2007).”
BM3D Frames and Variational Image Deblurring (2011, background): “A detailed discussion of the nontrivial connections between these formulations can be found in [7].”
Bregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction (2010, background): “Suppose that an image is formulated as a column vector (signal) of size n, D ∈ Rm×n is a given frame or a dictionary matrix, there are two different formulations for solving the problem: analysis based or synthesis based[21].”
The Cosparse Analysis Model and Algorithms (2011, neutral): “It is well known by now [19] that for a square and invertible dictionary, the synthesis and the analysis models are the same with D = Ω − 1 .”
Fast Image Recovery Using Variable Splitting and Constrained Optimization (2009, neutral): “Arguably, the best known and most often used regularizer used in analysis approaches to image restoration is the total variation (TV) norm [40], [11].”
Strategic Protection Against Data Injection Attacks on Power Grids (2011, background): “This attacking strategy can be seen as the combination of analysis-based and synthesis-based recovery problems [5], [6].”
Fields of Experts (2009, methodology): “Somewhat similar to ICA are sparse-coding approaches (e. g., Olshausen and Field, 1996), which also represent image patches in terms of a linear combination of learned filters, but in a synthesis-based manner (see also Elad et al., 2006).”
A Direct Algorithm for 1-D Total Variation Denoising (2013, neutral): “, [3, 4, 5, 6, 7, 8] for various insights.”
Projective dictionary pair learning for pattern classification (2014, background): “One related work to this paper is the analysis-based sparse representation prior learning [15, 16], which represents a signal from a dual viewpoint of the commonly used synthesis model.”