Part1: TheorySparsity?D is adapted to x if it can represent it with afew basis vectors(calledatoms)-that is,thereexists a sparsevectora in Rp such that DaxWecall a the sparsecode(α[1])α[2]did2~x(α[p])XERmDERmXpQERPsparse
Part1: Theory Sparsity ?
Part1: TheorySparse ModelAsp-0 weOur signal model iscount of therX=Dα where α is sparsethus:inthevectorala→%p-→02p<11-pCojj-1+1-1X= Dα where all ≤L
Part1: Theory Sparse Model -1 +1 1 p f x x x k p p p j j1 1 1 2 2 p p p 1 p 0 p p As p 0 we get a count of the non-zeros in the vector 0 0 x D where is sparse Our signal model is thus: 0 0 x D where L
Part1: TheoryProblemNumerical Problems:How should we solveor approximatethesolutionoftheproblemmin [al s.t. [Pα-yl ≤?min Pα-yl s.t. ll ≤Loraamin aal + Pα-yrQ. Theoretical Problems:Istherea uniquesparserepresentation?Ifwe are to approximate the solution somehow,how close will we get?Practical Problems:What dictionary D should we use,suchthatallthis leads toeffective representations?Will all this work inapplications?
Part1: Theory Problem min y s.t. L 0 0 2 2 D 2 2 2 0 0 min s.t. y D 0 2 0 2 min y D q Numerical Problems: How should we solve or approximate the solution of the problem or or ? q Theoretical Problems: Is there a unique sparse representation? If we are to approximate the solution somehow, how close will we get? q Practical Problems: What dictionary D should we use, such that all this leads to effective representations? Will all this work in applications?
Part2: Numerical problemsGoalSuppose we build a signal bythe relation路Dα=XP国We aim to find the signal'srepresentation:α = Arg Min alls.t. X = DαaWhy should we necessarily get α = α?Uniquenessa < It might happenthat eventually
Part2: Numerical problems Goal 0 0 ˆ ArgMin s.t. x D We aim to find the signal’s representation: Suppose we build a signal by the relation D x Why should we necessarily get ˆ ? It might happen that eventually . 0 0 0 0 ˆ Uniqueness
Part2:Numerical problemsGoal Ial s.t. IPα-yl2minThis is acombinatorialaproblem,proventobe NP-Hard!Hereisa recipeforsolvingthisproblem:SolvetheLSproblemGatherall themin Dα-yls.t.supp(α)=Si→LSerror ≤ 2?Set L=1Isupports(S)iCof cardinalityLYesNoforeachsupportSet L=L+1Assume: K=1000, L=10 (known!),1 nano-sec per each LSDoneWeshall need~8e+6yearstosolvethisproblem!!!!!
Part2: Numerical problems Goal Here is a recipe for solving this problem: Set L=1 Gather all the supports {Si}i of cardinality L LS error ≤ ε 2 ? 2 2 2 0 0 min s.t. y D Solve the LS problem for each support i 2 2 min y s.t. supp S D Set L=L+1 No Yes Assume: K=1000, L=10 (known!), 1 nano-sec per each LS Done We shall need ~8e+6 years to solve this problem !!!!! This is a combinatorial problem, proven to be NP-Hard!