README.txt: README file for gbp_package.zip / gbp_package.tar.gz

gbp_package includes the following files:

* gbp.m
* gbp_safe
* gbp_demo.m
* random_bp_problem.m

gbp.m is a basic implementation of Greedy Basis Pursuit (GBP).
It is essentially GBP as described in the tech report (YALEU/DCS/TR-1359),
without a check of the condition of the biorthogonal system.

gbp_safe.m implements GBP and includes a periodic check of the condition
of the biorthogonal system and an iterative pseudoinverse method to
recompute the biorthogonal system should it become ill-conditioned.
gbp_safe.m is therefore more stable than gbp.m but also marginally slower.

gbp_demo.m runs GBP and Matlab's LINPROG function, with both interior point
and simplex method settings on a set of randomly generate problems, and
outputs the results (running times, L1-norms, errors). Note that gbp_demo.m
includes a doubling of the dictionary (to include negative components of
the random dictionary) and a perturbation of the dictionary. (Here the
perturbation ensures that matrix inverses can be computed by Matlab's
linear programming routines; similar pertubations are useful for GBP in
the case of dictinoaries that may not be in general position, e.g.,
specially defined wavelet dictionaries.)

random_bp_problem.m generates a random signal representation problem
of specified size. The atoms and the signal are chosen uniformly at
random from the unit sphere in R^d.

See individual files for details.

Email questions/comments to: huggins@cs.yale.edu

Patrick Huggins
09/01/05