BPDN

所属分类:matlab编程
开发工具:matlab
文件大小:2897KB
下载次数:187
上传日期:2014-09-26 15:26:46
上 传 者搭讪达人
说明:  基于字典学习的匹配追踪算法,可以用来稀疏表示信号。包含matlab书和代码
(Atomizer is a package of Matlab routines for atomic decomposition of signals in various dictionaries)

文件列表:
Atomizer0802 (0, 2014-09-26)
Atomizer0802\AboutAtomizer1208.pdf (229423, 2012-10-02)
Atomizer0802\AtomizerPath.m (2158, 2001-04-18)
Atomizer0802\CHANGES (616, 2001-04-14)
Atomizer0802\Contents - 副本 (2) - 副本 - 副本.m (1773, 2001-04-14)
Atomizer0802\Contents - 副本 (2) - 副本.m (1773, 2001-04-14)
Atomizer0802\Contents - 副本 (2).m (1773, 2001-04-14)
Atomizer0802\Contents - 副本.m (1773, 2001-04-14)
Atomizer0802\Contents.m (1773, 2001-04-14)
Atomizer0802\Datasets (0, 2014-09-26)
Atomizer0802\Datasets\BrowseImages.m (1118, 2013-05-15)
Atomizer0802\Datasets\Contents.m (3127, 2013-05-15)
Atomizer0802\Datasets\HochNMR.asc (36864, 2013-05-15)
Atomizer0802\Datasets\HochNMR.txt (222, 2013-05-15)
Atomizer0802\Datasets\ImageFig.m (1537, 2013-05-15)
Atomizer0802\Datasets\InputSignal.m (5185, 2013-05-15)
Atomizer0802\Datasets\Internet.lnk (104, 2013-05-15)
Atomizer0802\Datasets\Make2dSignal.m (1203, 2013-05-15)
Atomizer0802\Datasets\MakeBrownian.m (1181, 2013-05-15)
Atomizer0802\Datasets\MakeCantor.m (946, 2013-05-15)
Atomizer0802\Datasets\MakeFractal.m (1155, 2013-05-15)
Atomizer0802\Datasets\MakeImage.m (5038, 2013-05-15)
Atomizer0802\Datasets\MakeProcess.m (1543, 2013-05-15)
Atomizer0802\Datasets\MakeSignal.m (8768, 2013-05-15)
Atomizer0802\Datasets\MakeSignal.m~ (8573, 2013-05-15)
Atomizer0802\Datasets\RaphNMR.asc (18432, 2013-05-15)
Atomizer0802\Datasets\RaphNMR.txt (431, 2013-05-15)
Atomizer0802\Datasets\ReadImage.m (3375, 2013-05-15)
Atomizer0802\Datasets\ReadSignal.m (2908, 2013-05-16)
Atomizer0802\Datasets\SonRemy.asc (250882, 2013-05-15)
Atomizer0802\Datasets\SonRemy.txt (115, 2013-05-15)
Atomizer0802\Datasets\barb.raw (262144, 2013-05-15)
Atomizer0802\Datasets\barb.txt (3, 2013-05-15)
Atomizer0802\Datasets\barton.raw (167936, 2013-05-15)
Atomizer0802\Datasets\barton.txt (567, 2013-05-15)
Atomizer0802\Datasets\canaletto.raw (262144, 2013-05-15)
Atomizer0802\Datasets\canaletto.txt (620, 2013-05-15)
Atomizer0802\Datasets\caruso.asc (305133, 2013-05-15)
Atomizer0802\Datasets\caruso.txt (509, 2013-05-15)
Atomizer0802\Datasets\coifman.raw (65536, 2013-05-15)
... ...

Contents: I. Objective II. Directory Structure III. Data Structure IV. Getting Started V. Customizing VI. Access and Installation I. Objective Atomizer is a package of MATLAB routines for atomic decomposition of 1-d signals in various dictionaries. The atomic decomposition techniques include basis pursuit, the method of frames, best orthogonal basis method for wavelet/cosine packets, and matching pursuit. Atomizer mainly supports dictionaries with fast analysis and fast synthesis operators, such as diracs, heavisides, discrete cosines, discrete sines, wavelets, stationary wavelets, quadratic splines, wavelet packets and cosine packets, or any combination of the above. Since Atomizer is designed in an object-oriented fashion, one can easily extend it to decompose in other dictionaries (see V. Customizing). Decomposition of signals into overcomplete dictionaries is not unique. Basis pursuit chooses the representation with minimum $l^1$ norm of coefficients. The method of frames selects the representation with minimum $l^2$ norm of coefficients. Matching pursuit is a stepwise greedy algorithm, a strategy that selects an atom with the biggest correlation with the residual. The best orthogonal basis method is specially designed for wavelet packets and cosine packets. It finds the best orthogonal basis representation by minimizing an additive entropy measure of coefficients. All the four methods can be accommodated to denoising signals in white noise. Basis pursuit denoising is a $l^1$ penalizing least square scheme. Method-of-frames denoising is a $l^2$ penalizing least square scheme. Matching pursuit denoising runs matching pursuit until the coefficient of the selected atom is below a certain threshold. Specially designed for wavelet packets and cosine packets, best orthogonal basis denoising is a thresholding scheme in the best orthogonal basis chosed by minimizing a special additive entropy. Basis pursuit can be reformulated as a linear program in standard form. Because of that connection, Atomizer has two algorithms for basis pursuit: BP-Interior and BP-Simplex. Designed for dictionaries with fast analysis and fast synthesis operators, BP-Interior implements a primal-dual logarithmic barrier interior point algorithm with a conjugate gradients solver for linear equations arising in interior point algorithm iterations. BP-Simplex is a simplex method, where one needs to provide dictionary matrices. Similarly, basis pursuit denoising can be reformulated as a quadratic program in standard form, and Atomizer has two implementations, namely BPDeNoise-Interior and BPDeNoise-Simplex. Atomizer implements the method of frames by a conjugate gradients solver. In some examples, basis pursuit exhibits several advantages over the method of frames, matching pursuit and best orthogonal basis, including better sparsity, super-resolution and better stability. The full complexity for solving a linear program is $O(n^3.5)$. Here we do not attempt to solve the basis pursuit criterion precisely, instead, we only attempt to get approximate optima (See V. Customing for details). As a result, the complexity of BP-Interior is $C_{BP} n \log(n)$, where $C_{BP}$ is tipically $50$. The complexity for the method of frames and the best orthogonal basis method are $O(n \logn)$. The complexity of matching pursuit is $C_{MP} n \log(n)$, where $C_{MP}$ is the number of atoms selected by matching pursuit. One can get an overview of the methodology from the article "Atomic Decomposition by Basis Pursuit" (Chen, Donoho and Saunders http://www-stat.stanford.edu/~Atomizer). One can also find there detailed discussion and references to the method of frames, matching pursuit and the best orthogonal basis method. Atomizer has been used as a basis for the authors' research on basis pursuit, and may be used to reproduce their published articles, and to redo their figures with variations in parameters. Atomizer is available free of charge over the Internet by WWW access; instructions are given below. II. Directory Structure Atomizer contains about 50 files, consisting of .m files, .mex files, and data sets. Atomizer has the following subdirectories: Datasets/ - Data for use with Atomizer DeNoising/ - DeNoising techniques: MOFDN, BOBDN, MPDN and BPDN Decomposition/ - Atomic decomposition techniques: MOF, BOB, MP and BP Dictionaries/ - Fast Analysis/Synthesis routines for various dictionaries Display/ - Displaying tools for representation in various dictionaries Documentation/ - Installation guide MexSource/ - C source files for .mex files Scripts/BP/ - Scripts reproducing the figures in the article 'Atomic Decomposition by Basis Pursuit' Scripts/Thesis/ - Scripts reproducing the figures in the Ph.D. thesis 'Basis Pursuit' Scripts/Tutor/ - Tutoring Scripts Each subdirectory has a file Contents.m, which explains the files in that subdirectory. Each file has a head of self-documentation. The Decomposition/ subdirectory contains routines performing atomic decomposition of 1-d signals: BP_Interior (Basis Pursuit), MOF (the Method of Frames), MP (Matching Pursuit) OMP (Orthogonal Matching Pursuit) and BOB (Best Orthogonal Basis). We also have correponding routines for dictionaries without fast algorithms: BP_Simplex, MOF_Matrix, MP_Matrix and OMP_Matrix (One needs to allocate memory for the whole dictionary). The DeNoising/ subdirectory consists of routines implementing atomic decomposition denoising techinques for signals with additive white noise: BPDN_Interior (Basis Pursuit DeNoising), MOFDN (MOF DeNoising) and MPDN (Matching Pursuit DeNoising). The Dictionaries/ subdirectory contains the fast analysis and fast synthesis routines for various dictionaries mentioned above, as well as routines defining the LIST data structures for accessing mixture dictionaries. FastA and FastS allow an object-oriented way for acessing analysis and synthesis operators for all the dictinaries implemented in Atomizer One should store the LSSOL simplex code in the LSSOL/ subdirectory. The Scripts/Tutor subdirectory provides tutorial scripts for one to learn how to use the major atomic decomposition routines in Atomizer. The Scripts/BP subdirectory provides scripts for reproducing all the figures in the article 'Atomic Decomposition by Basis Pursuit'. One can also run the same computing enviorment on his own signals, or tune the optimization parameters by simply modifying these scripts. We believe that one can get a good understanding of Atomizer by studying these scripts. The Scripts/Thesis subdirectory provides scripts for reproducing all the figures and tables in the Ph.D. thesis 'Basis Pursuit'. The MexSource/ subdirectory contains all the C source files to compile the mex files in Atomizer. According to our experience, mex files increase the computation speed at least 10 times on Unix machines. One can use the routine InputSignal in Dataset/ subdirectory to produce the synthesized signals, or access datasets provided in Atomizer. III. Data Structures Here we discuss the data structures for signals, coefficients and dictionaries ($s = \Phi \alpha$) in Atomizer. 1-d signals are represented, preferably, as n-by-1 matrices (i.e. n = 2^J). Atomic decompositions of 1-d signals are specified by coefficients. Coefficients are represented as n-by-1 matrices. A dictionary is specified by the following 4 arguments: NameOfDict, par1, par2, par3. NameOfDict is the name of the dictionary; it is a string. par1, par2, par3 are the parameters associated with the dictionary; they are numbers or vectors. If a dictionary has less than three parameters, one can simply assign the unused parameters to 0, or anything. E.g. (NameOfDict = 'PBS', par1 = log2(n), par2 = qmf, par3 = dqmf) specifies a periodized-biorthogonal-symmetric wavelet dictionary, where n is the signal length; qmf and dqmf are vectors of quadrature mirror filters. (NameOfDict = 'DCT', par1 = 4, par2 = 0, par3 = 0) would specify a discrete cosine dictionary 4 times finer in frequency than the standard frequency resolution (pi / n). We give a list of dictionaries implemented in Atomizer with their (NameOfDict, par1, par2, par3) at the end of this reference. Atomizer uses a list data structure to represent compound dictionaries, which are combinations of the standard implemented dictionaries. In this case (NameOfDict, par1, par2, par3) are all lists. For example, if NameOfDict = List(N^1, N^2), par1 = List(p1^1, p1^2), par2 = List(p2^1, p2^2), par3 = List(p3^1, p3^2), then (NameOfDict, par1, par2, par3) represents the combined dictionary of (N^1, p1^1, p2^1, p3^1) and (N^2, p1^2, p2^2,p3^2). One can use routine MakeList to make a list of any number of vectors, or a list of any number of strings. Because of the convenient data structure for dictionaries, all the atomic decomposition techniques in Atomizer are implemented in a object-oriented way, in the sense that one can do atomic decomposition in a certain dictionary by simply supplying the the four dictionary arguments (NameOfDict, par1, par2, par3). Also one can extend Atomizer to his own dictionary by supplying the fast analysis/synthesis routines in a certain fashion (See V. Customizing for detail). In order to apply Atomizer to images, one needs to convert 2-d images (n-by-n matrix) into 1-d objects (n^2-by-1 matrix), and design the fast analysis/synthesis operators for his dictionary in the same fashion. IV. Getting Started One should first install the software (See VI. Access and Installation), and get the article "Atomic Decomposition by Basis Pursuit" by Chen, Donoho and Saunders (http:/www-stat.stanford.edu/~Atomizer) to have to overview of the methodology in Atomizer. One can then start on Atomizer by studying and trying out the demo scripts in the Scripts/Demos subdirectory. Hopefully one can then be ready to analyze some of the datasets in the Datasets/ subdirectory using the atomic decomposition routines in Atomizer. It should also be very helpful for one to study and try the scripts in Scripts/BP to reproduce figures in Chen and Donoho. V. Customizing V.1 Tuning optimzation paramters BP_Interior: Our implementation of basis pursuit is based on a primal-dual log barrier interior point method. Since it takes a huge amount of computation ($n^3.5$) to achieve exact optimality, BP_Interior only attemps to calculate "approximate" optimal solutions within affordable time and storage. The accuracy of BP_Interior is controlled by several parameters. MaxBPIter controls the maximum number of interior point iterations. FeaTol and OptTol are two stopping criterions for BP_Interior; once the current iteration achieves the amount of feasibility defined by FeaTol and the amount primal-dual gap defined by OptTol, BP_Interior will stop. Inside each BP_Interior iteration, a linear system is solved by conjugate gradients method. The accuracy of the conjugate gradients solver is controlled by CGAccuracy; MaxCGIter defines the maximum number of conjugate gradients iterations. delta and gamma are two perturbation parameters. We suggest that one should set OptTol, FeaTol and CGAccuracy at the same level and set delta and gamma to one tenth of that level. According to our experience, the level 10^(-1) would give a decent approximation and the level 10^(-3) would give a very good approximation. MOF: We use a conjugate gradients solver to calculate the generalized inverse in MOF. The accuracy of the conjugate gradients solver is controlled by CGAccuracy (default = 10 ^ -5); When dictionary matrices are poorly conditioned, one might want to increase the maximum number of conjugate gradients iterations defined by MaxCGIter. MP: The number of atoms admitted by matching pursuit is controlled by two paramters. natom defines the maximum number of atoms admitted; MP stops once the coefficient of the selected atom gets below a fraction (defined by frac) of the orignal signal energy. Also the implementation of MP assumes that dictionary atoms are normalized by $l^2$ norms; otherwise one has to change the way MP calculates coefficients for atoms. BOB: One can change the entropy in the best orthogonal basis algorithm by changing the parameter entropy and par. The default entropy is the $l^1$ entropy. The denoising routines can be tuned in similar ways as their counterparts discussed above, except they have a thresholding parameter $\lambda$. For BPDN_Interior and MOFDN, $\lambda$ is the penalization (or regulaization) parameter. For MPDN, $\lambda$ plays the same role as frac in MP. The default values for $\lambda$ for all the denoising routines are set to be $\sqrt{2 m \log(m)}$ where $m$ is the cardinality of the dictionary. There are good reasons that we choose such $\lambda$ for BPDN_Interior and MPDN, one shouldn't change that for usual purpose. V.2 Merging dictionaries One can merge any of the implemented dictionaries to form a new mega dictionary by using MakeList. e.g. dict1 = 'WP' ; par11 = D; par12 = qmf; par13 = 0; dict2 = 'DCT'; par21 = 2; par22 = 0; par23 = 0; One can use: dict = MakeList(dict1, dict2); par1 = MakeList(par11, par21); par2 = MakeList(par12, par22); par3 = MakeList(par13, par23); to represent the merged dictionary V.3 Adding new dictionaries One can add a new dictionary by supplying the routines for the analysis and synthesis operator in the following format: Analysis: function c = Fast"NAMEOFDICT"Analysis(x, par1, par2, par3) Synthesis: function x = Fast"NAMEOFDICT"Synthesis(c, par1, par2, par3) e.g. If one wants to add a new dictionary with parameters NameOfDict = 'SHIFT' par1 = Amount of SHIFT he needs to supply the following two matlab functions: FastSHIFTAnalysis.m function c = FastSHIFTAnalysis(x, par1, par2, par3) n = length(x); c = [x(par1+1:n); x(1:par1)]; FastSHIFTSynthesis function x = FastSHIFTSynthesis(c, par1, par2, par3) n = length(c); x = [c(n-par1+1:n); c(1:n-par1)]; VI. Access and Installation Atomizer is freeware and may be obtained via: * World-Wide-Web: http://www-stat.stanford.edu/~Atomizer Your WWW browser may be used to peruse the documentation. Please send comments or questions to Atomizer@stat.stanford.edu VII. Appendix Here is the list of dictionaries implemented in Atomizer with their specification. Dictionaries normalized by l^2 norm o Dirac NameOfDict = 'DIRAC' o Discrete Cosine Transform NameOfDict = 'DCT' par1 = overcompleteness (integer) o Discrete Sine Transform NameOfDict = 'DST' par1 = overcompleteness (integer) o Periodized-Orthogonal Wavelet NameOfDict = 'WAVE' par1 = L, coarsest level par2 = qmf o Periodized-Biothogonal-Symmetric Wavelet NameOfDict = 'PBS' par1 = L, coarsest level par2 = qmf par3 = dqmf o Stationary PO Wavelet NameOfDict = 'STAT' par1 = D, degree of finest frequency partition par2 = qmf o Spline (Stationary PBS Wavelet) NameOfDict = 'SP' par1 = D, degree of finest frequency partition par2 = qmf par3 = dqmf o Wavelet Packet NameOfDict = 'WP' par1 = D, degree of finest frequency partition par2 = qmf o Cosine Packet NameOfDict = 'CP' par1 = D, depth of finest time splitting o Multi-Duration-Cosines NameOfDict = 'MCD' par1 = the depth, 0<=D<=log2(n) par2 = overcompleteness (integer) Dictionaries normalized by total variation o HeaviSide NameOfDict = 'HeaviSide' o Jump (Smoothed Heaviside) NameOfDict = 'JUMP' par1 = the decaying speed, 0 < par1 < 1, where small values correspond to faster decaying o POTV (PO Wavelet normalized by Total Variation) NameOfDict = 'JUMP' par1 = L, coarsest level par2 = qmf

近期下载者

相关文件


收藏者