1、Sparse Coding第x 章 稀疏編碼稀疏編碼與稀疏感知簡(jiǎn)介優(yōu)化算法 - MP，BP，K-SVD小結(jié)1Better Basis ?Better bases for compression or representation? WaveletsHow about data-dependent bases?How about learning?Sparse CodingIntroduction to sparse coding & sensing2First stage of visual processing in brain: V1Edge detection(Olshausen & F

2、ield, Nature, 1996)Sparse CodingIntroduction to sparse coding & sensing3Schematic of simple cellActual simple cell“Gabor functions.”Why sparsity?Sparse CodingIntroduction to sparse coding & sensing4Which do you want?Assume full rank, N d Choose the x with theleast nonzero componentWhy sparsity?The m

3、ore concise, the more betterIn some domain, there naturally exists a sparse latent vector that controls the data we saw. (ex. MRI, music)In some domain, samples from the same class have the sparse property.The domain can be learned.Sparse CodingIntroduction to sparse coding & sensing5A k-sparse doma

4、in means that each b can be constructed by a x vector with at most k nonzero element Sparse Sensing VS. Sparse CodingAssume that: Sparse CodingIntroduction to sparse coding & sensing6Sparse codingSparse sensingNote: p is based on the sparsity of the data (on k)Sparse Sensing VS. Sparse CodingSparse

5、sensing (compressed sensing):It spends much time or money to get b, so get y first then recover bSparse coding (sparse representation):Believe that there exists the sparse property in the data, otherwise sparse representation means nothing.x is used to be the feature of bx can be used to efficiently

6、 store b and reconstruct bSparse CodingIntroduction to sparse coding & sensing7Sparse Sensing VS. Sparse CodingSolution:There is no algorithm other than exhaustively searching to solve:While in some situations (ex. special form of A), the solution of l1 minimization approaches the one of l0 minimiza

7、tion Sparse CodingIntroduction to sparse coding & sensing8Sparse CodingIntroduction to sparse coding & sensing9KNFixed DictionarySparse & random vectorND=XSparse codingEvery column in D (dictionary) is a prototype signal (atom).The vector is generated randomly with few non-zeros in random locations

8、and with random values. Sparse CodingIntroduction to sparse coding & sensing10Sparse codingSimple: Every signal is built as a linear combination of a few atoms from the dictionary D.Effective: Recent works adopt this model and successfully deploy it to applications.Empirically established: Neurologi

9、cal studies show similarity between this model and early vision processes. Olshausen & Field (96)Sparse CodingIntroduction to sparse coding & sensing11Sparse codingGiven x, find the that generated it in D.XSparse CodingIntroduction to sparse coding & sensing12Sparse codingWe need to solve an under-d

10、etermined linear system of equations:Among all (infinitely many) possible solutions we want the sparsest ! We will measure sparsity using the L0 norm:DXSparse CodingIntroduction to sparse coding & sensing13Measure of SparsityAs p 0 we get a count of the non-zeros in the vector-1+11Multiply by DA spa

11、rse & random vectorSparse CodingIntroduction to sparse coding & sensingThree major questions:NP-hard: practical ways to get ?Is ?How do we know D ? 14Sparse CodingIntroduction to sparse coding & sensingThe sparse sensing:15Suppose we observe , a degraded and noisy version of x with . How do we recov

12、er x?How about find the that generated y ? NoiseQMSparse CodingIntroduction to sparse coding & sensingThree major questions:How can we compute ?Is ?What D should we use? 16Multiply by DA sparse & random vectorblur by HSparse CodingIntroduction to sparse coding & sensingThe sparse coding and sensing:

13、Our dream for now: Find the sparsest solution to Put formally:17Sparse codingSparse sensingSparse CodingIntroduction to sparse coding & sensingWhy should we necessarily get ?It might happen that eventually .18Are there reasonable ways to find ?Sparse Coding第x 章 稀疏編碼與感知稀疏編碼與稀疏感知簡(jiǎn)介算法 - MP，BP，K-SVD小結(jié)19

14、Sparse CodingSparse AlgorithmsMatching Pursuit (MP):The MP is a greedy algorithm that finds one atom at a time.Step 1: find the one atom that best matches the signal. Next steps: given the previously found atoms, find the next one to best fit The Orthogonal MP (OMP) is an improved version that re-ev

15、aluates the coefficients after each round.20Mallat & Zhang (1993)Sparse CodingSparse AlgorithmsBasis Pursuit (BP):The newly defined problem is convex (linear programming).Very efficient solvers can be deployed:Interior point methods Chen, Donoho, & Saunders (95)Iterated shrinkage Figuerido & Nowak (

16、03), Daubechies, Defrise, & Demole (04), Elad (05), Elad, Matalon, & Zibulevsky (06).21Instead of solvingSolve thisSparse CodingSparse AlgorithmsApprox. Quality? How effective are MP/BP ?MP and BP are different in general (hard to say which is better).The below results correspond to the worst-case.A

17、verage performance results available too, showing much better bounds Donoho (04), Candes et.al. (04), Tanner et.al. (05), Tropp et.al. (06).22Donoho & Elad (02)Gribonval & Nielsen(03)Tropp (03) Temlyakov (03)Given a signal x with a representation , if then BP and MP are guaranteed to find it. Sparse

18、 CodingSparse AlgorithmsWhat about the dictionary?-The quest for the origin of signals Given P examples and a fixed size (NK) dictionary, how would we find D?23Sparse CodingSparse AlgorithmsThe Objective Function 24DXASparse CodingSparse AlgorithmsThe Objective Function 25The examples are linear com

19、binations of atoms from DEach example has a sparse representation with no more than L atoms(N,K,L are assumed known, D has normalized columns)Sparse CodingSparse Algorithms26DInitializeDSparse CodingUse MP or BPDictionary UpdateColumn-by-Column by SVD computationAharon, Elad & Bruckstein (04)XTK-SVD

20、Sparse CodingSparse Algorithms27For the jth example we solve Ordinary Sparse Coding !DXTK-SVDSparse CodingSparse Algorithms28DXTFor the kth atomwe solve (the residual)K-SVDSparse CodingSparse Algorithms29dkakTWe want to solve:EkOnly some of the examples use column dk!When updating ak, only recompute the coefficients corresponding to those examplesSolve with SVD!K-SVDSparse CodingSparse Algorithms30DInitializeDSparse CodingUse MP or BPDictionary UpdateC