sparsearch.tex

SparseLab is a Matlab software package designed to find sparse solutions to systems of linear equati

%  SparseArch.tex

\documentclass[11pt,jeep]{book}
\pagestyle{headings}

\begin{document}

\input SparseMacros.tex

%=========================================

\title{\Huge SparseLab Architecture}
\author{
David Donoho, Victoria Stodden, and Yaakov Tsaig\\
Stanford University
\thanks{{\bf Acknowledgment of Support.}
This work was partially supported by NSF DMS-05-05303 and by other
sponsors.} }
\date{Version \WLVersion\\ \WLDate}

\maketitle

%\tableofcontents

%=============================================
%                Chapter 1
%=============================================
\chapter[Introduction]{Introduction}
\label{wlarch}

{\bf Changes and Enhancements for Release 2.0}: 4 papers have been added to Sparselab 2.0: "Fast
Solution of l1-norm Minimization Problems When the Solutions May be Sparse"; "Why Simple Shrinkage
is Still Relevant For Redundant Representations"; "Stable Recovery of Sparse Overcomplete
Representations in the Presence of Noise"; "On the Stability of Basis Pursuit in the Presence of
Noise."

This document describes the architecture of \WaveLab\ version \WLVersion.  It is designed for users
who already have had day-to-day interaction with the package and now need specific details about
the architecture of the package, for example to modify components for their own research.

For an introduction to \WaveLab\ at an elementary level, see {\it About SparseLab}. This document
may be accessed via WWW  through the \WaveLab\ Home Page: \WLWEB.

Before beginning, we mention the main components of the \WaveLab\ package, to standardize
terminology. First, there are the basic ``system components'':

\begin{itemize}
\item[1.] {\it Source.}  There is source code, in \Matlab, \TeX, Perl.

\item[2.] {\it Build.}  The source code is assembled into a standard release.
The current release is \WLVersion.

\item[3.] {\it Archives.} Compressed archives of the standard release available
for three platforms, Mac, Unix and PC, which users can download and install on
their machines.

\item[4.] {\it Web Documents.} A web home page (which can be viewed using any
web browser) and a series of postscript and pdf files which explain
what \WaveLab\ is and how to get it.  The URL is \WLWEB.
\end {itemize}

Next there are the  basic ``user components'' of an installed system:

\begin {itemize}
\item[1.] {\it \WaveLab\ Main Directory.}  A subdirectory /\WLName\/ of the {\tt
Matlab/work} directory, containing the currently released version of
\WaveLab\ software, datasets and documentation.

\item[2.] {\it Papers.} A directory \PaperDir\ in /\WLName\/ containing scripts
reproducing figures in various articles and technical reports.

\item[3.] {\it Examples.} A directory \WorkoutDir\ in /\WLName\
containing pedagogical examples that exercise various aspects of
\WaveLab.

\item[4.] {\it Solvers.} A directory /Sparselab100/Solvers/ in /\WLName\/ containing
the various solver engines of SparseLab.

\item[5.] {\it Documentation.} Both pdf and
Postscript files available by WWW access.

\item[6.] {\it Datasets.} The largest are included as separate downloads:
Sparselabvers\_DataSupplementExtCS and Sparselabvers\_DataSupplementStOMP, where vers is replaced
by the current SparseLab version. Numerical and image data used to illustrate various aspects of
sparse analysis by the scripts and workouts.
\end{itemize}

The following document describes all these various components from a
systems-level point of view. An individual needing to modify \WaveLab\ or add to
it would be interested in this information.

%=============================================
%                Chapter 2
%=============================================
\chapter[Papers]{Papers}
\label{scsec}

We briefly describe the contents and architecture of the
\PaperDir\ subdirectory of \WaveLab.

%-------------------------------------------------------------------------------
\section[Script Philosophy]{Script Philosophy}
\label{scphilo} The makeup of \PaperDir\ is the whole raison d'\^etre of the \WaveLab\ package. The
idea is that, when doing research in a computational science, one works to develop reproducible
knowledge about the results of computational experiments. The {\tt /Papers} directory is the end
product of such an effort. It makes available to researchers around the world, via the Internet,
the computations that produced figures which have been published in hardcopy form as technical
reports at Stanford University and in forthcoming journal articles. Other researchers can obtain
the \Matlab\ code which generated these figures, and can reproduce the calculations that underly
the figures.  They can, if they wish, modify the calculations by editing the underlying \Matlab\
code. They can use the algorithms on other datasets. They can try their own favorite methods on the
same datasets.

Our idea is that, when doing research, long before we write an article, we prepare ourselves with
the thought that {\it what we do on the computer will ultimately be made available to others, for
their inspection, modification, re-use and criticism}. This implies several things.  First, that
the work product which we are aiming to create will be a subdirectory of \WaveLab\ containing a
series of scripts that will generate, from scratch, all the figures of the corresponding article.
Second, that our work product is {\it not} the printed figures that go into the article, but the
underlying algorithms and code which generate those figures, and which will be made available to
others. Thus, it is no good to print a hardcopy of a figure that we see on the screen and save that
for photocopying into a final version of the paper.  Once we are happy with a figure we see on the
screen, we must save the code that generated the figure, and then edit the code to make it part of
a system that automatically reproduces all the figures of an article.

The philosophy we are adopting can be traced to Jon Claerbout and Martin Karrenbach's article {\it
Electronic Documents Give Reproducible Research New Meaning} ({\tt http://sepwww.stanford.edu}).
We especially like a thought of theirs which we paraphrase as follows:\\
\begin{quote} {\it \noindent A traditionally published article is not the end product of scholarship; it is the advertisement
for the scholarship. The working software environment that produced the figures in the article is
the actual end product of the scholarship.} \end{quote}

To work in accordance with the philosophy, we must adopt a discipline of how we structure our
computational experiments in \Matlab. A benefit of this discipline is, hopefully, to avoid the
sloppiness and errors that are ubiquitous in computational science.

%-------------------------------------------------------------------------------
\section[Script Architecture]{Script Architecture}
\label{scarch}

The architecture of the {\tt /Papers} directory is as follows. At present, it
contains these subdirectories, recreating figures in published articles:
\begin{verbatim}
  ExtCSDemo    - ``Extensions of Compressed Sensing''
  HDCPNPDDemo  - ``High-Dimensional Centrosymmetric Polytopes with Neighborliness Proportional to
  Dimension''
  MSNVENODemo  - ``Breakdown Point of Model Selection when the Number of Variables Exceeds the
  Number of Observations''
  NPSSULEDemo  - ``Neighborly Polytopes and Sparse Solutions of Underdetermined Linear Equations''
  NRPSHDDemo   - ``Neighborliness of Randomly-Projected Simplices in High Dimensions''
  SNSULELPDemo - ``Sparse Nonnegative Solutions of Underdetermined Linear Equations by Linear
  Programming''
  StOMPDemo    - ``Sparse Solution of Underdetermined Linear Equations by Stagewise Orthogonal
  Matching Pursuit''
\end{verbatim}

These subdirectories have been created following several rules,
which should be followed in making future additions.

\begin{itemize}
\item[1.] Each article gets one subdirectory of \PaperDir.

\item[2.] Each subdirectory contains: (a) the paper itself, (b) a subdirectory housing a
demo.

\item[3.] The files in a subdirectory have stylized names, so that the name indicates the function of the file.

\item[4.] Stylized names are based on a {\it name} and a {\it short prefix}.
The name should be short but descriptive, for example, {\tt Adapt} for scripts associated with the
paper {\it Adapting to Unknown Smoothness via Wavelet Shrinkage}  and the prefix should be a
related tag, just two-characters long, for example {\tt ad}.

\item[5.] The subdirectory name reflects the name you have chosen, for example
{\tt \PaperDir Adapt}.
\end {itemize}

\subsection{Demos}

The Demo subdirectory contains (a) meta-routines that run the whole figure-generating process, (b)
scripts that generate individual figures, (c) datasets the scripts draw on, and (d) specialized
tools, not present in \WaveLab\ proper, for generating the figures.

\subsection{Specialized Tools}

There are several tools available in the {\tt Utilities} directory to help you with writing
scripts.  For example, when creating a display through several {\tt Plot} calls, it is preferable
to use \WaveLab\ functions like {\tt LockAxes} and {\tt UnLockAxes} rather than to use the
low-level \Matlab\ routine {\tt hold}. See Chapter \ref{utilsec} below.

\subsection{Scripting Rules}

\begin {itemize}
\item[I.] One script creates one complete figure, not a series of figures, and
not just a subplot of a figure.

\item[II.]  If several scripts need to work with the same variables -- for
example, if you want a variable to be created in one script and then used in
later scripts -- these variables must be made global (see section 4 below).

\item[III.] No {\tt pause}'s, {\tt print}'s, of {\tt figure} calls in a script.

\item[IV.]  As far as possible try to use the tools in the \WaveLab\ {\tt
Utilities} directory to perform actions like setting axes.
\end {itemize}

Inspection of existing scripts will help in following these rules. If you obey these rules, then
your scripts should be upwardly compatible with script-running engines making more sophisticated
use of the \Matlab\ user interface.

\subsection{Documenting Individual Figures}

Each \dotm\ file for an  individual figure contains a help header
which is displayed in the command window at the time the figure is
generated in the plot window.  This provides a kind of on-line
narrative, or caption.  Here is an example from {\tt ExtCSDemo}:

\begin{verbatim}
% GenFig1 -- ExtCSDemo Figure 1: Error of reconstruction versus
% number of samples for signals with a controlled number of nonzeros.
%
% Data files used: DataL0_20.mat, DataL0_50.mat, DataL0_100.mat
%
% See also: GenDataL0.m
\end{verbatim}

%-----------------------------------------------------------------------------
\section[Adding New Scripts]{Adding New Scripts}
\label{scadd}

To add new demonstration scripts to \PaperDir, having the same
format and effect as {\tt ExtCSDemo}:
\begin {enumerate}
\item Decide on a {\it name} for your demo and a {\it short prefix} for files
implementing your demo. For example, {\tt MyOwnDemo} and {\tt mo}.

\item Create a new subdirectory of \PaperDir. For example, {\tt MyOwn}.

\item Create the following m-files:
\begin{verbatim}
    MyOwnDemo    - starts the Demonstration, invokes Choices
    MyOwnInit    - sets up data structures
    MyOwnFig     - called from Choices
    MyOwnIntro   - help file, explains contents of directories
\end{verbatim}

Suggestion: copy the corresponding files in one of the other subdirectories of
{\tt /Papers} into your new subdirectory, giving them these names; then edit these
files to refer to your own new scripts.

\item Create the scripts which implement your demo: {\tt mofig1.m}, {\tt
mofig2.m}, etc.  The scripts need to follow thee rules mentioned
above in sections 2.2, 2.3 and 2.4.
\end{enumerate}

%-----------------------------------------------------------------------------
\section[Modifying Existing Scripts]{Modifying Existing Scripts}
\label{scmodify}

You might want to modify an existing script for several reasons:
\begin{itemize}
\item To try it out on a different dataset;
\item To try it out with different parameters;
\item To insert a different method in place of the existing method,
using the same dataset.
\end {itemize}

Our rules for script creation should help make this possible.  Some issues to
keep in mind:

First, the script that generates a certain figure might be dependent on
computations done in the process of generating earlier figures.  Therefore, the
script cannot be assumed to work correctly in stand-alone mode. If the script
refers to any global variables then, at a minimum, the corresponding {\tt Init}
script has to be run before the indicated script in order to set global
variables up.

Second, in order to generate a certain effect, it might therefore be necessary
to change earlier scripts, not just the script formally associated with the
figure you are interested in.  The change might have to be in the {\tt Init}
script (to affect global variables), and might possibly have to be in other
scripts as well.

Third, when a set of scripts has been well-written, it should be
necessary {\it only} to change the {\tt Init} script to produce most
changes of the type users will want.

%=============================================
%                Chapter 3
%=============================================
\chapter[Examples]{Examples}
\label{wosec}

Here we describe the contents and architecture of the {\tt
/Examples} subdirectory of \WaveLab. We've included a number of
pedagogical examples in SparseLab, so that the user can familiarize
himself or herself with the software and with our intentions in
providing it. Currently we include:
\begin{verbatim}
      nnfEx            Non-negative Matrix Factorization
      reconstrutionEx  Signal Reconstruction
      RegEx            Model Selection in Regression