Spar and Redundant Reprentation Modeling—
What Next?
Michael Elad(Fellow,IEEE)
Abstract—Signal processing relies heavily on data mod-els;the are mathematical constructions impod on the data source that force a dimensionality reduction of some sort.The vast activity in signal processing during the past veral decades is esntially driven by an evolution of the models and their u in practice.In that respect, the past decade has been certainly the era of spar and redundant reprentations,a popular and highly effective data model.This very appealing model led to a long ries 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 rearch and practice.
Despite the huge success of this model so far,thisfield is still at its infancy,with many unanswered questions still remaining.This paper1offers a brief prentation of the story of spar and redundant reprentation modeling and its impact,and outlines ten key future rearch directions in thisfield.
I.I NTRODUCTION—W HO N EEDS M ODELS? One could not imagine the vast progress made in signal and image processing in the pastfifty years without the central contribution of data models.Consider the following example as a way of illustrating the need for a model:A signal of interest x∈R d is measured in the prence of additive noi,v∼N(0,σ2I),producing y=x+v.Given y we would like to recover x, esntially eking a decomposition of y into its two parts,x and v.Despite the fact that we have a full statistical characterization of the noi,such a paration is impossible,as the noi model only implies a Gaussian distribution for x,peaked at none other than y itlf. To depart from this triviality,we must characterize x as well,so that the two parts can be told apart.
A model for the signal x is exactly this—a mathe-matical characterization of the signal.As an example for a possible model and its u,if we know that x resides in a subspace of dimension r d spanned by the columns M.Elad is with the Computer Science Department,Technion –Israel Institute of Technology,Haifa32000,Israel(e-mail: hnion.ac.il).Copyright(c)2012IEEE.Personal u of this material is permitted.However,permission to u this material for any other purpos must be obtained from the IEEE by nding a request to pubs-permissions@ieee.
1This is not a regular IEEE-SPL paper,but rather an invited contribution offering a vision for key advances in emergingfields.of the matrix Q∈R d×r,this constitutes a model, and denoising(cleaning t
he noi)becomes possible. One could project y onto this subspace,applying the operation QQ†y,in order tofind the clost signal to y that complies with the model.Put formally,this projection is obtained as the solution of the problem ˆx=argmin x x−=QQ†x,(1) where QQ†x reprents our subspace constraint for the signal.2This will lead to effective denoising,with noi attenuation by a factor r/d( 1)on average.
The signal and image processing literature has en numerous attempts to handle the above-described denois-ing problem.Explicitly or implicitly,each and every one of the many thousands of published methods relies on a specific model,proposing a way to characterize the signal and a method to exploit this for the recovery of x.While the above model example is very simple, it sheds light on key properties of models in general. An effective model typically suggests a dimensionality reduction of some sort;the original d samples in the signal x are believed to be redundant and a much shorter description(in our example,of length r)can be given, reflecting the true dimensionality of the signal.Another issue is the migration from the core model formulation to its deployment in the processing task.In the example we suggested a projection of y,which is very natural. However,when the model becomes more expressive and complex,leaving room for more than one approximation, various possible“estimators”may be propod;thus,in general there is no one-to-one correspondence
between a model and the way to practice it,and this leaves much room for original and creative ideas.
While the above example discusd the denoising problem,models are necessary for almost every pro-cessing that x may need to undergo.Sampling of a signal relies on a prior assumption about its content,so as to guarantee no loss or limited loss of information. Compression of a signal is conceptually possible only becau it has an inner structure that reduces its entropy, 2If x is known to be spanned by the columns of Q,it can be written as x=Qαfor an arbitrary vectorα∈R r.Multiplying both sides by Q†we obtain Q†x=Q†Qα=α,since Q†Q=I.Substituting this relation back into x=Qαwe get the constraint x=Qα=QQ†x, as appears in Equation(1).
which is captured by a model that describes this signal with few parameters.Detection of anomalies in a signal or detection of target-content can be done only when we rely on models for the different contents.Similarly,paration of superimpod signals is done by using models for the distinct parts.Solving inver problems such as a tomographic reconstruction from projections,recovery of missing samples,super-resolving a signal,inpainting (filling-in missing values),extrapolating a signal,and deblurring,all rely on a model for the signals in question in order to regularize the typically highly ill-pod inversion process when recovering the desired signal.
牙线怎么用
Models can take various forms,and through the years they have been gradually improving.What does this mean?It is important to understand that for most signal sources there is no notion of a “correct model”.This is reminiscent of unified theories in physics that cannot be proven correct,but can be demonstrated to align well with experiments.Models,as a t of mathematical properties that the data is believed to follow,or as a probability density function in the Bayesian point of view,are necessarily erroneous.The quest for better models is a arch for a more flexible and accurate mathematical construction that reduces the overall model error.A careful study of the vast literature in signal and image processing from the past veral decades reveals that there has been an evolution of models,constantly improving along time by reducing their modeling error,and therefore consistently leading to better performance in the applications they were brought to rve.In that respect,the more successful models are tho that rely on signal examples to tune their characteristics,thus fitting better to the signals they describe.Figure 1prents such an evolution of models along time in the image processing
literature.
Figure 1.The evolution of models over the years in the field of
image processing.This evolution shows a clear path from L 2-bad methods to more challenging and sparsity-promoting models.
猫齿鲨To summarize,and to answer the question pod in the title of this ction,we all need models ,as they are
水瓶和水瓶extensively ud for many tasks.Their importance cannot be overstated —their impact on our abilities and ways to process data is central and irreplaceable.It is now time to discuss one of the most recent contributions to signal modeling —the model bad on spar and redundant reprentations,which will be referred to hereafter as Sparland .
II.S PARSELAND M ODELING
In the past decade there has been tremendous progress in the construction and u of new signal models.One of the main achievements within this activity is the concep-tion of spar and redundant reprentation modeling [1],[2],[3],[4]and references therein.3The fundamental idea behind this model is a redundant transform of the signal x ∈R d to a new reprentation α∈R n ,where n >d (thus leading to redundancy),such that the obtained reprentation is the simplest (i.e.,sparst)possible.This transform is mi-linear —the inver transform from αto x is linear,given by x =D α,where D ∈R d ×n is a matrix commonly referred to as the dictionary.The forward transform is a highly non-linear one,
(P 0)
ˆα=argmin α α 0
属蛇的幸运颜色<
x =D α,
(2)
arching for the sparst explanation for the signal x .The 0cost function · 0counts the non-zero entries in this vector,and we expect a spar outcome, α 0=k d .This model can be interpreted as a chemistry of data sources:the columns of the dictionary are referred to as atoms (fundamental elements),and thus the dictionary rves as the “periodic table”in this chemistry.The signal is thought of as a molecule,which is believed to be a (linear)combination of only few atoms.
We mentioned before that models impo a dimen-sionality reduction –how does this happen here?A signal belonging to Sparland is assumed to have k d non-zeros in its reprentation,and thus it must have one of the n k possibilities for a support (t of atoms ud).Each such support defines a subspace of dimension k (at most)in R d ,and so the overall signal model is therefore a union-of-sub
spaces which the signal is believed to belong to.As such,this model is a natural extension of the naive single subspace model mentioned in the previous ction,and the dimensionality reduction obtained here is somewhat more involved.It is evident from the above description that the dictionary D is
3
Due to length constraints,it would be impossible to do justice and cite all the relevant literature.
Figure 2.Paper and citation counts over the years for work related to the Sparland model.The results were obtained via ISI Web-Of-Science arching the SCI-Expanded databa with:Topic=(((p
arsim*or spars*)and (reprent*or approx*or sol*or convex)and (pursuit or dictionary or transform))or (compres*and (ns*or sampl*)and (spars*or parsim*))).This arch was done on September 22nd ,2012.Since this arch was done on September 2012,the paper and citation counts for 2012are only partial,explaining the sudden drop in the graphs.
central to the characterization of the signal family which x belongs to.怎么盗号
In order to illustrate how this model should be ud in practice,let us return to the denoising task as described above:We are given y ,a noisy version of the signal x ,and we assume that x belongs to ,it is known to have a k -spar reprentation with respect to some dictionary D .In order to denoi y ,we should project it onto the model,esntially arching for the
signal ˆx that is the clost to y ,while also belonging to one of the n k subspaces that this model covers.Put formally,we should solve the problem
(P noi 0)
ˆα=argmin α y −D α α 0=k,(3)
which is a direct extension of Equation (2)for the noisy tup.The denoid signal would be D ˆα,the
multiplica-tion of the found reprentation ˆαby the dictionary.This description reveals the high complexity that characterizes the required denoising process (in fact,it has been proven to be NP-hard),as we need to sweep through all the possible subspaces.In order not to leave our readers worried at this stage,we should add that in recent years there has been enormous progress in devising highly efficient methods to approximate the solution of (P noi 0
),with provable guarantees of success.The Sparland model is a very effective and suc-cessful model.It has gained substantial popularity in the past decade,as it offers a unique mixture of theoretical depth,numerical challenges,and successful applications.Beyond the simplicity and elegance of this model,it is very appealing and popular becau of the following key reasons:
1.Universality:As said above,a signal belonging to Sparland must reside in a union-of-subspaces.This high-dimensional structure is very rich,very flexible,and
yet,it emerges from a relatively conci t of parameters —the dictionary D .Due to this universality,this model has found numerous applications in processing various imaging sources [5],[6],[7],[8],audio [9],video [10],[11],ismic data [12],financial data [13],and more.2.Theory:This model leads to a wide t of interesting theoretical questions.Given a candidate solution for D α=x ,could w
e claim its global optimality for the problem defined as (P 0)in Equation (2)?As this problem is NP-Hard,can we approximate it?If so,what guarantees can we po for the algorithms?For a noisy signal,could we recover the correct support of its reprentation?What is the minimal possible error we should expect?and is it achievable by practical algorithms?Finally,if a signal is replaced by a small t of projections of it,can this be sufficient for recovering it?The and many other questions have formed the grounds for fascinating rearch activity that flourished in the past decade,leading to very constructive and elegant answers [14],[15],[16],[17],[18].
3.Practicality:There is a clear path from the above theory to practical algorithms and applications.A large family of pursuit algorithms (e.g.[19],[20])has been propod for approximating the solution of (P 0)and its
noisy variant,(P noi 0
).Various ideas have been explored for harnessing this model to applications,using wavelets (e.g.,[21])or learning the dictionary from examples [22],[23],[24],[25],leading often to state-of-the-art results.Today,this field and its branches have become very popular topics,with many active rearchers from lead-ing universities devoting their efforts to decipher some of the above mentione
d riddles and challenges.Figure 2shows paper and citation counts over the years for work related to the Sparland model.While this is a crude and somewhat inaccurate arch,it is sufficient
4
for demonstrating the massive(exponential)growth in the interest in thisfield.Figure3prents the spread of the publications in various universities and rearch institutes around the
world.
Figure3.A list of the universities and rearch institutes where most of the publications on Sparland originate from.This relies on the same ISI Web-of-Science arch as in Figure2.
The interest in this model is growing dramatically, which only magnifies the community’s appetite for more breakthroughs in thisfield,and the belief that such achievements are within reach.Incidently,the work on compresd4nsing(CS)that emerged in2005-2006[26],[27]has also contributed in a large part to the popularity of this model,as it added another layer of theory and practice to spar reprentations,in the context of signal-sampling.So strong was the impact of CS that many today identify the entirefield of spar and redundant reprentations with it.
In the recently updated EDICS for the IEEE-Signal Processing Letters,five new entries related to spar and redundant reprentations have been added.The include:
•Theory of spar reprentations and compresd-nsing(MLSAS-SPARSE),
•Spar signal reprentations and recovery-algo-rithms and applications(DSP-SPARSE)
•Audio processing via spar reprentations(AEA-SPARSE),
•Spar reprentation in imaging(IMD-SPAR),and •Compresd Sensing(SAM-SPARCS).
This reflects the popularity of this model and its impact on signal processing rearch and practice.中国女星
A few words about the history of thisfield:It is quite hard to single-out the origin of the ideas that stand behind the above model,but it is clear that the vast activity in the years1980-2000on transforms in general,and wavelets and frame theory in particular,substantially contributed to it,tting the stage for its conception. 4Sometimes the term“compressive”is ud instead.Central contributions were made by a handful of influ-ential works in the mid-nineties[28],[29],[30],and the marked the birth of thefield as an individual rearch area.Following the,a truly extensive work on Sparland modeling took place mostly in the past decade.It was the daring paper in2001by Donoho and Huo[31],which ignited the burst of interest in thisfield,by establishing for thefirst time a theoretical connection between sparsity-eking transforms and the 1-norm measure.
路
During the past decade,the interest in sparsity and re-dundancy has grown dramatically.The scientists working on this topic come from various disciplines—mathe-maticians(applied and theorists),statisticians,engineers from variousfields,geophysicists,physicists,neuropsy-chologists,computer science theoreticians,and others. Various conferences,workshops,and special ssions have been organized to gather scientists working on the topics,and various journals have allocated special issues for this and related topics.All of the testify to the great popularity thisfield has gained.
III.S O,W HAT N EXT?
With the impressive achievements that spar and redundant reprentation modeling has gathered in the past years,one might be tempted to believe that not much is left to be done.However,this could not be further from the truth—there are numerous unanswered questions and unexplored avenues for future rearch in thefields of signal modeling in general and sparsity-bad models in particular.The success of sparsity and redundancy as core forces in signal modeling naturally leads to an appetite to further extend sparsity-bad signal modeling techniques,and stretch their limits in various ways.
In trying to map the future work in this arena,we e three key directions that are central for advancing thisfield,and tho are likely to draw the attention of rearchers in coming years:
•Theoretical frontiers
•Model improvements,and
•Applications.
We shall now detail each of the directions,and mention ten key open problems that await future tre
atment.
At this point we would like to draw the reader’s attention to Thomas Strohmer’s paper published in this issue,who focus is Compressive-Sensing(CS)[32]. In his article,Strohmer discuss the recent progress in CS,and points to key challenges and opportunities in this field.As CS and Sparland are cloly related,many of the topics covered in[32]are of great relevance to the discussion here,and the reader would benefit much from reading the two papers together.
5
And just before we start,a few words of caution:First, the open problems described hereafter are often so becau they are simply very hard to handle.Second,the discussion to come is somewhat biad by the author’s own perspective,and the ideas discusd should be taken as such.
A.Theoretical Frontiers
As said above,one of the main achievements of the vast work on Sparland is the theoretical backbone that establishes the goodness of this model and the algorithms rving it.In the past decade,many papers explored the performance limits of pursuit algorithms,reconstruction bounds for
various inver problems rving sparly reprented signals,and fundamental properties of the core model.Nevertheless,the main questions on all the fronts remain esntially open,simply becau the obtained results are often unrealistically restrictive.
1.Better Bounds:A commonflaw that shadows many of the existing results in thisfield is the reliance on worst-ca measures of the dictionary properties,such as the mutual-coherence[14]or the restricted isometry property(RIP)[18].Both the measures(and there are others suffering from the same weakness)are defined with respect to the worst-possible constellation of atoms and their influence on the pursuit success.As such,even if conquent analysis adopts a probabilistic point of view,the eventual results tend to be overly restrictive, leading to wide gaps between theoretical predictions and actual performance(which tends to be much better).Nat-urally,we should explore ways to replace the worst-ca measures by average-ca ones,or others.While such work has already started to appear(e[33],[34]), far more work should be invested on this topic in order to lead to simple yet effective theoretical predictions of the actual pursuit performance.
2.Targeting General Dictionaries:The above leads us naturally to the next issue,of providing theoreti-cal results on the performance of pursuit algorithms for general content dictionaries.In recent years much progress has been made in making statements on the pursuit performance for random diction
aries.A major breakthrough along the lines has been obtained via the approximate message-passing algorithms and their machinery[35],[36].However,none of the can be extended easily to more general content dictionaries, which means that the results em to be applicable only for the compresd-nsing problem.In various image processing tasks,we have no control over the dictionary content,and often the dictionary is obtained through training.In the cas we would like to know that the CS results remain applicable,suggesting that a good(near-oracle)MSE recovery is possible of a signal that is known to be compressible(having a spar reprentation,or nearly so).
3.Theory of Dictionary Learning:Dictionary learning is a prominent part of Sparland,as it enables the extraction of an underlying sparsifying dictionary from a given t of signal examples.This process has been treated mostly empirically[22],[23],[25],[30],offering algorithms to learn the dictionary.Theoretically speak-ing,so far we have little justification for using the algorithms—we do not know whether the learning problem is ,that noisy signals can be ud in principle to learn a good quality dictionary),we do not have solid results that guarantee the success of the learning algorithms,nor do we have a thorough study of the algorithms’flaws.Here too there are very few recent,partial,but very daring attempts[37],[38],[39]. But more than anything,the testify to the complexity of the questions,and the dire need for broader and more constructive theoretical results that will establish the“safety”of using dictionary learning.
飑线4.Unified Theory of Simplicity Measures:As afinal topic in this sub-ction,we take a few steps back and adopt a much wider view of Sparland:The 0sparsity has been chon as the driving force for this model becau it rves as an ultimate measure of simplicity.In recent years,low-rankness of a matrix has been also pop-ularized as an alternative simplicity measure[40].How are the two connected?Recent results show a unified view of the two,including a common theoretical study of recovery problems[41].Are there other measures of simplicity we should be thinking of?Is there a unified view of such measures that would include sparsity,low-rankness,and others(such as low-entropy),as special cas?This may lead to a new theory that considers an abstract notion of simplicity in general inver problems.
B.Model Improvements
Behind the deep and elegant theory developed for Sparland,stand the desire tofind better ways for modeling of data.As such,Sparland has been shown to be quite successful and better than its predecessors. However,if the goal is indeed modeling,we must ask ourlves whether Sparland is the ultimate model.Are thereflaws in this model that call for modifications? Could we envision ways to improve it?We mentioned above the existence of an evolution of models,improving over time,and there is no reason to believe that this evolution ends here.Thus,Sparland is nothing more than one
stop in a long list of generations of models to
