aboutsparselab.tex

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

As new articles are written by members of our group, we will add new subdirectories.

Each subdirectory contains a ``demo'' file, such as {\tt ExtCSDemo.m}, which allows you to
reproduce the figures in the corresponding article.

When you invoke that file in \Matlab\ by typing its name (without the \dotm\ extension), a new
window will appear on the screen.  If you mouse-click on the push button {\tt Show All Figures} you
will see, in sequence, each figure in the corresponding article.  As each figure appears in
{\Matlab}'s figure window, the command window will contain narrative explaining what you see in the
figure window.


\subsubsection{Demo Inventory}

Here is an up-to-date listing of demos in version \WLVersion,
and the articles to which they correspond:
\begin{verbatim}
   ExtCSDemo    - demo for paper "Extensions of Compressed Sensing"
   HDCPNPDDemo  - demo for paper "High-Dimensional Centrosymmetric Polytopes with
                  Neighborliness Proportional to Dimension"
   MSNVENODemo  - demo for paper "Breakdown Point of Model Selection When the
                  Number of Variables Exceeds the Number of Observations"
   NPSSULEDemo  - demo for paper "Neighborly Polytopes and Sparse Solutions of
                  Underdetermined Linear Equations"
   NRPSHDDemo   - demo for paper "Neighborliness of Randomly-Projected Simplices
                  in High Dimensions"
   SNSULELPDemo - demo for paper "Sparse Nonnegative Solutions of Underdetermined
                  Linear Equations by Linear Programming"
   StOMPDemo    - demo for paper "Sparse Solution of Underdetermined Linear Equations
                  by Stagewise Orthogonal Matching Pursuit"
\end{verbatim}


\subsection{Examples}

We include 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             Nonnegative Factorization
   reconstructionEx  Signal Reconstruction
   RegEx             Model Selection in Regression
   TFDecompEx        Time Frequency Decomposition
\end{verbatim}

Each example is documented on the SparseLab website and can be run by running the correspondingly
named .m file in each directory. All scripts are documented to allow users to modify parameters
such as noise level, number of variables or observations, algorithm used, etc.

\subsection{Reproducible Research}

Jon Claerbout, a distinguished exploration geophysicist at Stanford, has in recent years championed
the concept of {\it really reproducible research} in the ``Computational Sciences.''

The ``Computational Sciences'' he has in mind are fields in which mathematical and computer science
heuristics may suggest algorithms to be tried on scientific signal processing and imaging problems,
but mathematical analysis alone is not able to predict fully the behavior and suitability of
algorithms for specific datasets. Therefore experiments are necessary and such experiments ought,
in principle, to be reproducible, just as experiments in other fields of science.

Some background information may help the reader.  Suppose we are working in an area like
exploration seismology where the goal is an image of the subsurface, and computational science
aims to produce better images. However, the deliverable is not an image itself, but instead the
software environment that, applied in the right way, produces the image, and which, hopefully,
could be applied to other datasets to produce equally nice images. The scientific findings may turn
out to be a {\it knowledge of parameter settings} for this complex software environment that seem
to lead to good results on real datasets.

With this as background, reproducibility of experiments requires  having the complete software
environment available in other  laboratories and the full source code available for inspection,
modification, and application under varied parameter settings.

Reducing this to a slogan: {\it An article about computational science in a scientific publication
is {\bf not} the scholarship itself, it is merely {\bf advertising} of the scholarship.  The actual
scholarship is the complete software development environment and the complete set of instructions
which generated the figures.}

The advantage of reproducibility for the progress of the discipline is clear. When a really good
idea is found, everyone else can be using it right away. When a  mistaken finding is reported, it
is rooted out almost immediately, etc.

The barriers to sharing complete software environments are also clear: if you are the developer of
a nice piece of software, you may not want to give other people the benefit of your investment of
time simply for the benefit of an abstract principle such as scientific progress. Even if you are
altruistic enough to  make your work available to others in this way, it's a lot of extra work to
generate code clean enough for others to look at; most people prefer to make the figures for their
articles using quick-and-dirty undocumented code, and move on to the next project.

Claerbout and his colleagues have developed a discipline for building their own software, so that
from the start, they expect it to be made available to others as part of the publication of their
work.  Specifically, they publish CD-ROMs (available from Stanford University Press) which contain
the text of their books along with a special viewer that makes those books {\it interactive
documents}, where as one reads the document, each figure is accompanied by the possibility of
pop-up windows which allow one to interact with the code that generated the figure, to ``burn'' the
illustration (i.e., erase the postscript  file supplied with the distribution),  and to rebuild the
figure from scratch on one's own machine.  By following the discipline of planning to  publish in
this way from the beginning, they maintain all their work  in a form which is easy to make
available to others at any point in time.

Why do we think this concept is significant for the research community? It is our perception that
as we approach specific applications using sparse solvers, we are becoming a computational science
like seismic imaging. In this setting, publishing figures or results without the complete software
environment could be compared to publishing an announcement of a mathematical theorem without
giving the proof.

With the recent rapid spread of Internet facilities worldwide and the standardization of scientific
computing on about five machine architectures, most of which are UNIX-based, it becomes feasible
and timely to actually experiment with protocols implementing the goal of reproducible research. We
may forget that in other sciences, the canonical form for scientific articles was arrived at
incrementally. For example, it has been said  that Pasteur introduced the notion of publishing a
full description of methods, materials and laboratory procedures.

The publication of \WaveLab\ is a modest step in this direction. Partly to indicate our esteem for
the work of Claerbout and the Stanford Exploration Project, we are making available code which will
allow the interested Internet-nik to reproduce the figures in our articles and to study the exact
parameter settings and algorithms which were used in those articles. This arrangement does not, at
the moment, conform to the Stanford Exploration Project's idea of interactive document, in which a
special TeX viewer is tied to special code resources that can rebuild and vary the figures in a
paper. However, at a primitive level, it provides the interested researcher with the TeX files of
the documents and everything necessary (sans \Matlab) to rebuild and modify the figures in those
articles.

We hope to publish code in this way for several forthcoming articles and also to learn more about
the concepts of {\it Interactive Document} and {reproducible research}.

\subsection{Freeware}

Richard Stallman and others associated with the GNU project have pioneered the idea of free
software -- software that can freely be redistributed by users. (This does not mean free of cost;
it means the rights any one person has over the software are the same as those of any other).  We
have been influenced by this, but obviously cannot completely follow them since we require of users
that they have \Matlab, which is not freely redistributable. In fact, Richard Stallman told one of
us that making our software available in \Matlab\ was the worst thing we could do, as this might
encourage people to buy \Matlab!

In our opinion, the Freeware concept is useful and has had a major impact. However, the Freeware
concept has limits, and the \Matlab\ example shows this clearly. Modern scientific computing
depends on {\it quantitative programming environments} like \Matlab, {\sc SPlus}, {\sc R}, {\sc
Mathematica}, {\sc X-Math}, {\sc IDL} and so on. These are widely available, widely understood
high-level languages in which key concepts of scientific discourse (Fast Fourier Transform, etc.)
are available as built-in, easily usable features.  At the moment, a complete Freeware
implementation of one's computational experiments requires, more or less, emulating Jon Claerbout's
example and writing all one's tools from scratch in C or Fortran.  Claerbout is forced to do this
because of the massive size of the datasets he uses, which exceed the bounds of \Matlab\ or other
QPE's. Most working scientists have smaller-scale datasets than Claerbout, and so they can use
modern QPE's. Moreover they are busy, and view scientific computing only as a sideshow.  They
cannot be expected to start from scratch and develop all their code in C when they can get, much
more quickly and reliably, the same results in a very high-level language. Thus the temptation to
work in a QPE is almost irresistible.

Stallman might retort that there are now freeware QPE's.  Octave is a \Matlab\ work-alike in many
ways, developed by John Eaton at the University of Texas Chemical Engineering department.  Octave
is developed strictly within the GNU philosophy, and so makes available a Stallman-acceptable QPE.
In the latest release, version 1.1, it comes close to \Matlab\ 4.X in many key ways, so that a
large fraction of what we do will run under Octave.  Perhaps one day an Octave port of \WaveLab\
will be feasible.

But where does a working scientist spend his/her effort? On ports to noncommercial systems that
will satisfy the urges towards binary liberation? Perhaps, but only with a lower priority than
other activities. It is our impression that, at the moment, there are relatively few scientists who
would complain about lack of access to \WaveLab\ due to the cost of \Matlab, and far fewer who
would complain that we fall short of full reproducibility by our dependence on a commercial tool at
one stage. Sorry to let you down, Richard.

\pagebreak

\section{Fine Print}

In making available our software, the authors have tried to follow some simple
guidelines.  We spell them out in this section  to avoid misunderstandings about
what we are offering, why we are offering it, what rights we give you and what
rights we retain for ourselves.

The directory {\tt SparseLab/Documentation} contains the following
files:
\begin{verbatim}
ADDINGNEWFEATURES       -  How to Add New Features to SparseLab

BUGREPORT               -  How to report bugs about SparseLab

COPYING -  SparseLab Copying Permissions

DATASTRUCTURES          - Basic data structures in SparseLab

FEEDBACK                -  Give feedback about SparseLab

GETTINGSTARTED          -  Ideas for getting started with SparseLab

INSTALLATION            - Installation of SparseLab

LIMITATIONS -  SparseLab known limitations

PAYMENT -  No Charge for SparseLab Software

REGISTRATION - SparseLab Registration

SUPPORT - SparseLab Support

THANKS - Thanks to contributors

VERSION -  Part of SparseLab Version v$VERSION$

WARRANTY - No Warranty on SparseLab software
\end{verbatim}
These describe the philosophy and limitations of our package.  The key points
are summarized here, by reprinting the contents of some of those files.

\subsection{Dependence on \Matlab}

\Matlab\ is a product of The Mathworks, a successful company based in Natick, Massachusetts. Their
product is expensive. You need it to run our software. We do not offer it. You must get it from
them. You need version 6.X or later. We have no connection with them. They have no connection with
us.

\subsection{Registration -- \WaveLab\ Registration}

(from file {\tt REGISTRATION.m})

Please Register yourself as a user of \WaveLab\ so that we can send you e-mail about upgrades and
enhancements. To Register: go to the Download page of the Sparselab website \WLWEB and click on the
link \underline{REGISTER}. If you like, please include information about the version of \Matlab\
you are using and about the type of machine you are using.

\subsection{Limitations}

This package has been designed to reproduce the figures in our research. Accordingly, it may not
solve the problems you have in mind. Please see the file {\tt LIMITATIONS.m} before complaining.
Perhaps we are already aware of the problem you have and are seeking to fix it!

\subsection{Support}

(from file {\tt SUPPORT.m})

This software has been developed as part of the research effort of the authors under various
federally supported grants.  If you find that it does not work correctly, please e-mail a
notification of your problem to \WaveLab.  Use the format indicated in the file {\tt BUGREPORTS.m}.

To the extent that we can isolate the problem and develop a solution, and to the extent that it
fits in with our schedule with releasing a new version, we will attempt to fix the problem.

\subsection{No Charge -- No Charge for \WaveLab\ Software}

(From file \Payment)

\WaveLab\ software is available at NO CHARGE from the SparseLab website at\\
\centerline{\WLWEB.} The software is copyrighted. For permissions to copy, see the file \Copying\
or you may e-mail \eWaveLab. If you use this software to produce scientific articles, we would
appreciate being informed of the article's title, authors, topic, and place of appearance. If this
software played a major enabling role in your scientific work, and you are so moved, you might
acknowledge us in your article.

\subsection{No Warranty -- No Warranty on SparseLab software}

(From file \Warranty)

There is no warranty attached to the \WaveLab\ software.

If you find that it does not work correctly, use the file BUGREPORTS.m as a template to compile a
description of the problem, including as far as possible a complete m-file script that generates
the error. E-mail the description to: \eWaveLab. Resources permitting, an effort will be made to
correct the problem for a future release.

\vskip .1in
\centerline{\bf FORMAL LEGAL DISCLAIMER OF WARRANTY}

We make no warranties, explicit or implicit, that the programs contained in this collection are
free of error, or are consistent with any particular standard of accuracy, or that they will meet
your requirements for any particular application. They should not be relied on for any purpose
where incorrect results could result in loss of property or personal injury. If you do use programs
for any such purpose it is at your own risk. The authors disclaim all liability of any kind, either
direct or consequential, resulting from your use of these programs.

\subsection{Copyright -- \WaveLab\ Copying Permissions}

(From file \Copying)

This software was developed with partial support of the National Science Foundation Grant DMS
92-07266. Contributors to this effort include David Donoho, Iddo Drori, Michael Saunders, Victoria
Stodden, Joshua Sweetkind-Singer, and Yaakov Tsaig.

In EVERY case, the software is COPYRIGHTED by the original author. For permissions, e-mail
\eWaveLab.

\vskip .1in
\centerline{\bf COPYLEFT NOTICE}

Permission is granted to make and distribute verbatim copies of this entire software package,
provided that all files, directories, and subdirectories are copied {\it together} as a {\it unit}.

Here {\it copying as a unit} means: all the files listed in the file {\tt SLFiles} are copied, so
that among other things  the \Thanks\ notice, and this permission notice accompany all copies of
the full software, and every ``\dotm'' file continues to contain a copy of the file {\tt VERSION.m}
inside it.

Permission is granted to make and distribute modified copies of this software, under the conditions
for verbatim copying, provided that the entire resulting derived work is distributed under the
terms of a permission notice identical to this one. Names of new authors, their affiliations and
information about their improvements may be added to the files \Copying\ and \Thanks.

The purpose of this permission notice is to allow you to make copies of the software and distribute
them to others subject to the constraint that you maintain the collection of tools here as a unit.
This enables people to whom you give the software to be aware of its origins, to ask questions  of
us by e-mail, to request improvements, obtain later releases, etc.

If you seek permission to copy and distribute translations of this software into another language,
please e-mail a specific request to \eWaveLab. If you seek permission to excerpt a {\it part} of
the software library  for example to appear in a scientific publication, please e-mail a specific
request to \eWaveLab.


\subsection{Thanks -- Thanks to contributors}

(from file \Thanks)

This software was developed with support of the National Science
Foundation grant DMS 00-07266. Contributors to this effort include
David Donoho, Iddo Drori, Michael Saunders, Victoria Stodden, Joshua
Sweetkind-Singer, and Yaakov Tsaig.

Further contributions are welcome, for info e-mail \eWaveLab.

%{\bf Contributors of Data}: The following have contributed data
%hich is part of our system. Evan Hurowitz, University of California San Francisco Department of
%Biopharmaceutical Sciences.

\input References.tex

\end{document}