readme

％ Atomizer Main Directory, Version .802 里面信号含有分解去噪合成过程的代码 ％---------------------------------------

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