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].

                       (1)

Basis pursuit denoise(Three forms).

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

             (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. 

                          (3)
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.

Reference

[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. 



http://blog.sciencenet.cn/blog-621576-551341.html

上一篇:Sparse Representation (Cont.)
下一篇:稀疏表达、压缩感知

3 田灿荣 崔全顺 Coo

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

数据加载中...

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

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

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部