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
近期下载者:
相关文件:
收藏者: