zhenliangli的个人博客分享 http://blog.sciencenet.cn/u/zhenliangli


Basis Pursuit

已有 6357 次阅读 2012-3-24 20:03 |个人分类:Signal processing|系统分类:科研笔记| Basis, coding, sparse, norm

From my first blog article-An introduction to sparse representation.
We have noticed that the sparse coding for the input datasets is very useful to signal processing and machine learning.
Zero norm is the direct solution for the sparse coding problem. However, D.L. Donoho[1] proved that 1 norm solution is also the sparsest solution, and it is equals to zero norm solution.
Standard BP

The form without noise[2].


Basis pursuit denoise(Three forms).

BP is relaxed to obtain the basis pursuit denoise (BPDN) problem.[2]

The parameter  is used to estimate the noise level of the input data sets.It becomes a standard BP problem when   equals to  zero.
E.V.D. Berg, etl, have proposed an efficient algorithm[3] for  problem. 

Using Lagrange-operater into problem (2), it turn problem (2) into problem (3).
It is first proposed by Chen, Donoho, and Sunders[2].

It was proposed by R. T.IBSHIRNI[4].

For the case where an estimate of the noise level   is known, Chen, Donoho, etl [2] argue that the choice  has important optimality properties.


[1]  D. L. Donoho, For most large underdetermined systems of linear equations the minimal 1-
norm solution is also the sparsest solution,        Comm. Pure Appl. Math., 59 (2006), pp. 797–829.
[2]   S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit,SIAM Rev.   43 (2001), pp. 129–159.
[3]   E.V.D. Berg and M.P. Friedlander,  Probing the pareto frontier for basis puisuit solutions.  SIAM J. Sci. Comput.     31(2008), pp.  890-912.
[4]     R. Tibshirani, Regression shrinkage and selection via the Lasso, J. Roy. Statist. Soc. Ser. B.    58 (1996), pp. 267–288. 


上一篇:Sparse Representation (Cont.)

3 田灿荣 崔全顺 Coo

该博文允许注册用户评论 请点击登录 评论 (1 个评论)


Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-4-13 03:37

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社