Chapter 3 Sparse Signal Recovery
Chapter 3 Sparse Signal Recovery
3.1 Sparsity:Applications and Development What is sparse? 1.Many data mining tasks can be represented using a vector or a matrix. 2.Sparsity implies many zeros in a vector or a matrix
3.1 Sparsity: Applications and Development What is sparse? 1. Many data mining tasks can be represented using a vector or a matrix. 2. Sparsity implies many zeros in a vector or a matrix
3.1 Sparsity:Applications and Development As seen in the last chapter in linear regression,we are actually solving this problem: y Φ w y(x,w)=wrφ(x)+n Where n is noise. 十 We have learned that,if p >n,there will be serious over-fitting. n×1 nxp pxI n×1 To suppress over-fitting,we can add a p>>n regularizer.We can add a sparse regularizer (LASSO)to render the target vector sparse,to select a small number of basis function
3.1 Sparsity: Applications and Development As seen in the last chapter in linear regression, we are actually solving this problem: Where is noise. We have learned that, if , there will be serious over-fitting. To suppress over-fitting, we can add a regularizer. We can add a sparse regularizer (LASSO) to render the target vector sparse, to select a small number of basis function. 𝒘 𝒏
3.1 Sparsity:Applications and Development In image processing,to compress a image,we first do a transformation to the pixel matrix to render it sparse,such transformations are 1 Singular Value Decomposition 2 Discrete Cosine Transform 3 Wavelet Transform... Note that the black pixels indicate the matrix values are close to zero ft corner thus making the matrix easy to compress 2 layer discrete cosine transfornpmed in with Haar wavelet basis
3.1 Sparsity: Applications and Development In image processing, to compress a image, we first do a transformation to the pixel matrix to render it sparse, such transformations are 1 Singular Value Decomposition 2 Discrete Cosine Transform 3 Wavelet Transform… Note that the black pixels indicate the matrix values are close to zero thus making the matrix easy to compress 2 layer discrete cosine transform with Haar wavelet basis U S V SVD Up left corner zoomed in DCT Original
3.1 Sparsity:Applications and Development Some times,on Weibo,interesting news originate from certain users and is forwarded many times by other users.We now know who forwards the messages and when the messages are forwarded. Now we want to construct a relationship (who friended whose Weibo) network from the above information.This can be abstracted as a topological graph. Sparsity:each node is linked to a small number of neighbors. Equivalent matrix representation
3.1 Sparsity: Applications and Development Some times, on Weibo, interesting news originate from certain users and is forwarded many times by other users. We now know who forwards the messages and when the messages are forwarded. Now we want to construct a relationship (who friended whose Weibo) network from the above information. This can be abstracted as a topological graph. Sparsity: each node is linked to a small number of neighbors