aboutsparselab.tex

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

% AboutSparseLab.tex

\documentclass{article}

\addtolength{\textwidth}{1in}
\addtolength{\oddsidemargin}{-0.5in}
\addtolength{\textheight}{1.6in}
\addtolength{\topmargin}{-0.8in}
\usepackage{epsf}
\usepackage{graphicx}

\begin{document}

\input SparseMacros.tex

\title{About SparseLab}
\author{
\bigskip \\
David Donoho, Victoria Stodden, Yaakov Tsaig\\
Stanford University}
\date{Version 2.0\\
March, 2007}

\maketitle

\begin{abstract}
{\bf Changes and Enhancements for Release 2.0}: 4 papers have been added to Sparselab 200: "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."

\WaveLab\ is a library of \Matlab\ routines for finding sparse solutions to underdetermined
systems. The library is available free of charge over the Internet. Versions are provided for
Macintosh, UNIX and Windows machines. Downloading and installation instructions are given here.

\WaveLab\ has over 400 \dotm\ files which are documented, indexed and cross-referenced in various
ways.  In this document we suggest several ways to get started using \WaveLab: (a) trying out the
pedagogical examples, (b) running the demonstrations, which illustrate the use of SparseLab in
published papers, and (c) browsing the extensive collection of source files, which are
self-documenting.

\WaveLab\ makes available, in one package, all the code to reproduce all the figures in the
included published articles. The interested reader can inspect the source code to see exactly what
algorithms were used, and how parameters were set in producing our figures, and can then modify the
source to produce variations on our results. \WaveLab\ has been developed, in part, because of
exhortations by Jon Claerbout of Stanford that computational scientists should engage in ``really
reproducible'' research.

This document helps with installation and getting started, as well as describing the philosophy,
limitations and rules of the road for this software.
\end{abstract}

{\bf Acknowledgment of Support.} This work was partially supported
by NSF DMS-05-05303 (Stanford).

\pagebreak

\tableofcontents

\pagebreak

\section{Introduction}

\WaveLab\ is a library of \Matlab\ routines for finding sparse solutions to underdetermined
systems. The library provides the research community with open source tools for sparse
representation, as well as being the basis for research by the authors, and may be used to
reproduce the figures in their published articles, and to redo those figures with variations in the
parameters.

The library is available free of charge over the Internet by WWW access; instructions are given
below.  The material is, however, copyrighted, so that advance permission is required for any
commercial use.

The package approaches the problem of sparse representation from both signal processing and
statistical viewpoints. The user is free to choose the terminology he or she is comfortable with.
SparseLab incorporates software for several published solvers, for example Michael Saunders'
Primal-Dual method for Optimization with Convex Objectives, Mallat and Zhang's Matching Pursuit,
Donoho and Johnstone's Iterative Hard and Soft Thresholding, Efron et al's Least Angle Regression,
and a number of others.

In addition to routines finding sparse solutions to systems, the library contains scripts which
give a quick examples in a variety of different settings. We believe that by studying these scripts
one can quickly learn the practical aspects of sparse representation and one can learn how to use
the \WaveLab\ software library

In this guide we give information which will help you access and install the software on your
machine and get started in exploring the resources contained in the \WaveLab\ distribution. We also
explain the philosophy which underlies our distribution of the software, and some of the fine print
associated with the software.

There are other resources for obtaining information about \WaveLab. First, there is a {\it
SparseLab Architecture} guide which gives details about how \WaveLab\ is constructed and
maintained. Secondly, we give more information on the SparseLab website.

This body of software is under continuing development by a team of researchers supported by a grant
from the NSF, and from other sponsors. We conduct our research with the idea, from the beginning,
that we will implement our tools in \WaveLab. We believe that the discipline this entails makes our
research of a higher quality than otherwise possible.

We welcome your suggestions for further enhancements, and any contributions you might make.

\pagebreak

\section{Access and Installation}

The \WaveLab\ library contains \dotm\ files (\Matlab\ code), datasets, documentation scripts and
workouts (both also \dotm\ files) for reproducing the figures in articles by the authors.

The whole library consists of over 400 files. It requires more than \MinSize\ and less than
\MaxSize\ space on disk once it is downloaded, decompressed and installed. The largest data files
for two demos are included in separate packages: Sparselab100\_DataSupplementExtCS.zip and
Sparselab100\_DataSupplementStOMP.zip -- the majority of the size comes from these components.

This documentation refers to Version \WLVersion\ of \WaveLab.

\subsection{Platform-Specific Information}

\WaveLab\ is available for use in \Matlab\ 6.x or 7.x on three
different platforms: Windows XP or 2000, UNIX/Linux and Macintosh.
The package is made available as a compressed archive, in a \dotzip\
format.\\
 You do have to know about one convention used in the
documentation. We always use the UNIX pathname conventions rather
than PC or Macintosh, e.g.\ {\tt Matlab/Toolbox/\WLDir} rather than
{\tt Matlab\BS Toolbox\BS SparseLab} or {\tt
Matlab:Toolbox:WaveLab}. You have to transliterate what we say into
the version appropriate for your platform.

\subsection {WEB Acess}
To download the compressed archive from the web, point your web
browser to \WLWEB\ to access the \WaveLab\ web-page. Once there,
mouse click the "Download" link in the left frame.

\subsection{Installation}

In this section we first describe the installation process in narrative form,
and later give a step-by-step checklist.

Once the appropriate compressed archive has been transferred to your
machine, it should be decompressed and installed. You will need an
appropriate software to decompress \dotzip\ file \WLName \dotzip. On
a personal computer (Macintosh or Windows), the archives should be
decompressed and installed as a subdirectory of the {\tt Toolbox}
directory inside the {\tt matlab} folder. On a UNIX workstation or
server, the archives could either be installed in the systemwide
{\tt matlab} directory, if you have permission to do this, or in
your own personal {\tt matlab} directory, if you do not.

Once the actual files are installed, you should have a number of files and
subdirectories in the directory \WLDir. If you look in the files
\Contents\ inside of the \WLDir\ directory, you will see a plan of what is inside:

\begin{verbatim}
% SparseLab Main Directory, Version 100
%
% This is the main directory of the SparseLab package.
%
%              .m files in this directory
%
%   Contents.m           -    This file
%   SparsePath.m         -    Sets up global variables and pathnames
%
%              Subdirectories
%   Documentation        -    System-Wide Documentation
%     /About SparseLab
%     /SparseLab Architecture
%   Examples             -    Detailed examples of SparseLab finding sparse solutions
%     /nnfEX             -    Nonnegative Factorization Example
%     /reconstructionEx  -    Signal Reconstruction Example
%     /RegEx             -    Regression Example
%     /TFDecompEx        -    Time-Frequency Reconstruction Example
%   Papers               -    Scripts for reproducing figures in published articles
%     /ExtCS             -    figures for "Extensions of Compressed Sensing"
%     /HDCPNPD           -    figures for "High-Dimensional Centrosymmetric
%                             Polytopes with Neighborliness Proportional to Dimension"
%     /NPSSULE           -    table in "Neighborly Polytopes and Sparse
%                             Solutions of Underdetermined Linear Equations"
%     /NRPSHD            -    figures for "Neighborliness of
%                             Randomly-Projected Simplices in High Dimensions"
%     /SNSULELP          -    figures for "Sparse Nonnegative Solutions of
%                             Underdetermined Linear Equations by Linear Programming"
%   Solvers              -    Sparse solver packages
%   Tests                -    Simple pedagogical workouts
%   Utilities            -    General tools for developers and users
%   shell_tools          -    Tools for use during the SparseLab build process

%
% Part of SparseLab Version:100
% Created Tuesday March 28, 2006
% This is Copyrighted Material
% For Copying permissions see COPYING.m
% Comments? e-mail [e-mail]
\end{verbatim}

Make a local directory listing to see if your hard disk actually has
these files and subdirectories.

\subsection{Pathnames}

\Matlab\ can automatically, at startup time, make all the \WaveLab\ software
available. The script \WavePath\ is provided as part of \WaveLab\ to enable this
feature. It should be invoked from the user's \Startup\ file.

\begin{itemize}
\item[PC] \Startup\ is located in the {\tt matlab\BS local} directory on MS-Windows.
Insert the line {\tt SparsePath} in that file, and put a copy of
\WavePath\ in that directory.

\item[Mac] \Startup\ may be located anywhere inside the {\tt Matlab} directory
on Macintosh. Insert the line {\tt SparsePath} in that file. Since
\WaveLab\ contains a \Startup\ file, if you have no other \Startup\
file, there is nothing to do once \WaveLab\ is installed.

\item[Unix] This file is located in the  {\tt matlab} subdirectory of your home
directory on UNIX. If you don't have such a subdirectory, use {\tt
mkdir $\sim$/matlab} to make one. Create a file named \Startup\ and
insert the line {\tt SparsePath} in that file.  Then put a copy of
\WavePath\ in that directory.

\end{itemize}

\subsection{Checklists}

To reinforce the above points, we furnish here step-by-step installation
checklists.

\subsubsection{UNIX Checklist}
\begin{enumerate}
\item[1.] Binary Download the archive to the directory you want
\WaveLab\ to reside.
\item[2.] Uncompress the archive: {\tt SparseLab100.zip}
\item[3.] Decide where you want the \WaveLab\ directory to reside. It will have
a number of subdirectories and occupy at least \MinSize\ disk space.
\item[4.] After you decompress the file for your machine, you should
have the following directory structure.\\
\WLName \\
\WLName / Solvers\\
\WLName / Datasets \\
\WLName / Documentation\\
\WLName / Papers\\
\WLName / Examples\\
\WLName / Utilities \\
\item[5.] Copy all the SparseLab files from the place you put the original SparseLab
 archive (for example /tmp) to their final destination, for example in your home
 directory
    \~ user/matlab/\WLName.

\item[6.] Launch Matlab; In Matlab set the current path to
matlabroot/toolbox/\WLName\ or alternatively copy the file
\WavePath\ from $<$ MatlabToolboxPath $>$ /\WLName\ to
$<$MatlabToolboxPath$>$ /local

\item[7.] Run \WavePath; If the default pathname is not right the
program will ask you to enter the correct path.
\item[8.] Type {\tt installMEX} to compile and install the \dotmex\ files.
\end{enumerate}

{\it Trouble-Shooting UNIX:} Compare the output of {\tt ls -r
SparseLab100} with {\tt Documentation}  to see if you have all the
files. Compare the output of the \Matlab\ command {\tt path} with
the list above to see if you have all the directories in your path.

\subsubsection{Macintosh Checklist}
To follow these instructions you will need:
\begin{itemize}
\item[(1)] A Macintosh running MacOS 10.3 or later.
\item[(2)] A program which can unzip \dotzip\b
file.
\item[(3)] Matlab 6.x or 7.x for Mac.
\end{itemize}
Steps:\\
\begin{itemize}
\item[1.] Binary Download the file {\tt \WLName \dotzip} to your
Macintosh.
\item[2.] Extract the archive to the Toolbox folder of your Matlab
folder. After you extract the file you should have the following
subdirectory structure: \\
\WLName \\
\WLName / Solvers\\
\WLName / Datasets \\
\WLName / Documentation\\
\WLName / Papers\\
\WLName / Examples\\
\WLName / Utilities \\

\item[3.] Launch Matlab; In Matlab set the current path to
matlabroot/toolbox/\WLName\ or alternatively copy the file
\WavePath\ from $<$ MatlabToolboxPath $>$/\WLName\ to
$<$MatlabToolboxPath$>$/local
\item[4.] Run \WavePath\ at the command prompt to start \WaveLab.
You will see a "Welcome to SparseLab" message as shown in the section Success below.
\end{itemize}
Note: \\
\begin{enumerate}
\item If you want to automatically load \WLName\ upon the start-up
copy the file \WavePath\ from the folder \WLName\ to the folder
Matlab/Toolbox/local. Determine if you have any file named startup.m
besides the one that is in \WLName\ directory. If you don't, go to
step 3.\\
 \item if you have \Startup\ , then copy the contents of \WavePath\
 into this file.
 \item If you don't have any \Startup\ , then copy the file \Startup\ from
 \WLName\ directory to
 $<$MatlabToolboxPath$>$/local
 \end{enumerate}

\subsubsection{PC Checklist}
To follow these instructions you will need:
\begin{itemize}
\item[(1)] An Intel Platform running Windows 2000 or XP.
\item[(2)] A program such as Winzip which can unzip \dotzip\
file.
\item[(3)] Matlab 6.x or 7.x for Windows.
\end{itemize}
\begin{enumerate}
\item[1.] Binary Download the file {\tt \WLName \dotzip} to your
PC.
\item[2.] Extract the archive to the Toolbox folder of your Matlab
folder. After you extract the file you should have the following
subdirectory structure: \\
\WLName \\
\WLName / Solvers\\
\WLName / Datasets \\
\WLName / Documentation\\
\WLName / Papers\\
\WLName / Examples\\
\WLName / Utilities \\

\item[3.] Launch Matlab; In Matlab set the current path to
matlabroot\BS toolbox \BS \WLName\ or alternatively copy the file