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.