About SparseLab
David Donoho, Victoria Stodden, Yaakov Tsaig
Stanford University
Version 2.0
March, 2007
Abstract
Changes and Enhancements for Release 2.0: 4 papers have been added to Sparse-
lab 200: ”Fast Solution of l1-norm Minimization Problems When the Solutions May be
Sparse”; ”Why Simple Shrinkage is Still Relevant For Redundant Representations”; ”Sta-
ble Recovery of Sparse Overcomplete Representations in the Presence of Noise”; ”On the
Stability of Basis Pursuit in the Presence of Noise.”
SparseLab 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.
SparseLab has over 400 .m files which are documented, indexed and cross-referenced in
various ways. In this document we suggest several ways to get started using SparseLab: (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.
SparseLab 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. SparseLab 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.
Acknowledgment of Support. This work was partially supported by NSF DMS-05-05303
(Stanford).
1
3
4
4
4
4
5
5
5
6
7
8
8
9
9
9
10
12
12
12
12
13
13
14
16
16
16
17
17
17
17
17
18
Contents
1 Introduction
2 Access and Installation
2.1 Platform-Specific Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 WEB Acess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3
2.4 Pathnames
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5 Checklists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1 UNIX Checklist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.2 Macintosh Checklist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.3 PC Checklist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Success
3 Getting Started
3.1 Snooping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Contents Files
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Help for Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3
Source Browsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 Documentation Directory . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.5 Dataset Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Demos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 Demo Inventory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Examples
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Reproducible Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Freeware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4 Fine Print
4.1 Dependence on Matlab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Registration – SparseLab Registration . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4 Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5 No Charge – No Charge for SparseLab Software . . . . . . . . . . . . . . . . . . .
4.6 No Warranty – No Warranty on SparseLab software . . . . . . . . . . . . . . . .
4.7 Copyright – SparseLab Copying Permissions . . . . . . . . . . . . . . . . . . . . .
4.8 Thanks – Thanks to contributors . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1 Introduction
SparseLab 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 SparseLab 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 SparseLab 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 SparseLab. First, there is a Sparse-
Lab Architecture guide which gives details about how SparseLab 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 SparseLab. 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.
3
2 Access and Installation
The SparseLab library contains .m files (Matlab code), datasets, documentation scripts and
workouts (both also .m files) for reproducing the figures in articles by the authors.
The whole library consists of over 400 files.
It requires more than 200MB and less than
400MB 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 compo-
nents.
This documentation refers to Version 2.0 of SparseLab.
2.1 Platform-Specific Information
SparseLab 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
.zip 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. Matlab/Toolbox/Sparselab rather
than Matlab\Toolbox\SparseLab or Matlab:Toolbox:WaveLab. You have to transliterate what
we say into the version appropriate for your platform.
2.2 WEB Acess
To download the compressed archive from the web, point your web browser to http://sparselab.stanford.edu
to access the SparseLab web-page. Once there, mouse click the ”Download” link in the left frame.
2.3 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 .zip file
Sparselab200.zip. On a personal computer (Macintosh or Windows), the archives should be
decompressed and installed as a subdirectory of the Toolbox directory inside the matlab folder.
On a UNIX workstation or server, the archives could either be installed in the systemwide matlab
directory, if you have permission to do this, or in your own personal matlab directory, if you do
not.
Once the actual files are installed, you should have a number of files and subdirectories in
the directory Sparselab. If you look in the files Contents.m inside of the Sparselab directory, you
will see a plan of what is inside:
Contents.m
SparsePath.m
.m files in this directory
% SparseLab Main Directory, Version 100
%
% This is the main directory of the SparseLab package.
%
%
%
%
%
%
%
%
%
%
%
%
/About SparseLab
/SparseLab Architecture
Examples
/nnfEX
Subdirectories
Documentation
-
-
-
-
-
This file
Sets up global variables and pathnames
System-Wide Documentation
Detailed examples of SparseLab finding sparse solutions
Nonnegative Factorization Example
4
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
/reconstructionEx
/RegEx
/TFDecompEx
Papers
/ExtCS
/HDCPNPD
/NPSSULE
/NRPSHD
/SNSULELP
Solvers
Tests
Utilities
shell_tools
-
-
-
-
-
-
-
-
-
-
-
-
-
Signal Reconstruction Example
Regression Example
Time-Frequency Reconstruction Example
Scripts for reproducing figures in published articles
figures for "Extensions of Compressed Sensing"
figures for "High-Dimensional Centrosymmetric
Polytopes with Neighborliness Proportional to Dimension"
table in "Neighborly Polytopes and Sparse
Solutions of Underdetermined Linear Equations"
figures for "Neighborliness of
Randomly-Projected Simplices in High Dimensions"
figures for "Sparse Nonnegative Solutions of
Underdetermined Linear Equations by Linear Programming"
Sparse solver packages
Simple pedagogical workouts
General tools for developers and users
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 sparselab@stanford.edu
Make a local directory listing to see if your hard disk actually has these files and subdirecto-
ries.
2.4 Pathnames
Matlab can automatically, at startup time, make all the SparseLab software available. The script
SparsePath.m is provided as part of SparseLab to enable this feature. It should be invoked from
the user’s Startup.m file.
PC Startup.m is located in the matlab\local directory on MS-Windows.
Insert the line
SparsePath in that file, and put a copy of SparsePath.m in that directory.
Mac Startup.m may be located anywhere inside the Matlab directory on Macintosh. Insert the
line SparsePath in that file. Since SparseLab contains a Startup.m file, if you have no
other Startup.m file, there is nothing to do once SparseLab is installed.
Unix This file is located in the matlab subdirectory of your home directory on UNIX. If you
don’t have such a subdirectory, use mkdir ∼/matlab to make one. Create a file named
Startup.m and insert the line SparsePath in that file. Then put a copy of SparsePath.m
in that directory.
2.5 Checklists
To reinforce the above points, we furnish here step-by-step installation checklists.
2.5.1 UNIX Checklist
1. Binary Download the archive to the directory you want SparseLab to reside.
2. Uncompress the archive: SparseLab100.zip
3. Decide where you want the SparseLab directory to reside. It will have a number of subdi-
rectories and occupy at least 200MB disk space.
5
4. After you decompress the file for your machine, you should have the following directory
structure.
Sparselab200
Sparselab200/ Solvers
Sparselab200/ Datasets
Sparselab200/ Documentation
Sparselab200/ Papers
Sparselab200/ Examples
Sparselab200/ Utilities
5. Copy all the SparseLab files from the place you put the original SparseLab archive (for ex-
ample /tmp) to their final destination, for example in your home directory ˜user/matlab/Sparselab200.
6. Launch Matlab; In Matlab set the current path to matlabroot/toolbox/Sparselab200 or
alternatively copy the file SparsePath.m from < MatlabToolboxPath > /Sparselab200 to
/local
7. Run SparsePath.m; If the default pathname is not right the program will ask you to enter
the correct path.
8. Type installMEX to compile and install the .mex files.
Trouble-Shooting UNIX: Compare the output of ls -r SparseLab100 with Documentation
to see if you have all the files. Compare the output of the Matlab command path with the list
above to see if you have all the directories in your path.
2.5.2 Macintosh Checklist
To follow these instructions you will need:
(1) A Macintosh running MacOS 10.3 or later.
(2) A program which can unzip .zipf
ile.
¯
(3) Matlab 6.x or 7.x for Mac.
Steps:
1. Binary Download the file Sparselab200.zip to your Macintosh.
2. Extract the archive to the Toolbox folder of your Matlab folder. After you extract the file
you should have the following subdirectory structure:
Sparselab200
Sparselab200/ Solvers
Sparselab200/ Datasets
Sparselab200/ Documentation
Sparselab200/ Papers
Sparselab200/ Examples
Sparselab200/ Utilities
3. Launch Matlab; In Matlab set the current path to matlabroot/toolbox/Sparselab200 or
alternatively copy the file SparsePath.m from < MatlabToolboxPath >/Sparselab200 to
/local
4. Run SparsePath.m at the command prompt to start SparseLab. You will see a ”Welcome
to SparseLab” message as shown in the section Success below.
6
Note:
1. If you want to automatically load Sparselab200 upon the start-up copy the file SparsePath.m
from the folder Sparselab200 to the folder Matlab/Toolbox/local. Determine if you have
any file named startup.m besides the one that is in Sparselab200 directory. If you don’t,
go to step 3.
2. if you have Startup.m , then copy the contents of SparsePath.m into this file.
3. If you don’t have any Startup.m , then copy the file Startup.m from Sparselab200 directory
to /local
2.5.3 PC Checklist
To follow these instructions you will need:
(1) An Intel Platform running Windows 2000 or XP.
(2) A program such as Winzip which can unzip .zip file.
(3) Matlab 6.x or 7.x for Windows.
1. Binary Download the file Sparselab200.zip to your PC.
2. Extract the archive to the Toolbox folder of your Matlab folder. After you extract the file
you should have the following subdirectory structure:
Sparselab200
Sparselab200/ Solvers
Sparselab200/ Datasets
Sparselab200/ Documentation
Sparselab200/ Papers
Sparselab200/ Examples
Sparselab200/ Utilities
3. Launch Matlab; In Matlab set the current path to matlabroot\toolbox \Sparselab200 or
alternatively copy the file SparsePath.m from < MatlabToolboxPath > \Sparselab200 to
\local
4. Run SparsePath.m at the command prompt to start SparseLab. You will see a ”Welcome
to SparseLab” message as shown in the section Success below.
Note:
1. If you want to automatically load Sparselab200 upon the start-up copy the file SparsePath.m
from the folder Sparselab200 to the folder Matlab \Toolbox \local. Determine if you have
any file named startup.m besides the one that is in Sparselab200 directory. If you don’t go
to step 3.
2. if you have Startup.m then copy the contents of SparsePath.m into this file.
3. If you don’t have any Startup.m then copy the file Startup.m from Sparselab200 directory
to \local
7
2.6 Success
When you have a successful installation, you should see something like the following when you
invoke Matlab:
Welcome to SparseLab v 100
Setting Global Variables:
global MATLABVERSION = 7
global SparseLABVERSION = 100
global SparseLABPATH = C:\Program Files\MATLAB704\work\SparseLab\SparseLab100\
global PATHNAMESEPARATOR = "\"
global PREFERIMAGEGRAPHICS = 1
SparseLab 100 Setup Complete
Currently available browsers for reproducing figures from the
following papers:
ExtCSDemo
HDCPNPDDemo - demo for paper "High-Dimensional Centrosymmetric Polytopes with
- demo for paper "Extensions of Compressed Sensing"
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
NRPSHDDemo
- demo for paper "Neighborliness of Randomly-Projected Simplices
Underdetermined Linear Equations"
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"
Currently available examples:
Nonnegative Factorization
Signal Reconstruction
Regression Example
Time-Frequency Separation
For more information, please visit:
http://sparselab.stanford.edu
Please ignore the following message if WaveLab has been installed.
There are SparseLab functions which call WaveLab functions. We
recommend that the users download WaveLab from the website
http://www-stat.stanford.edu/~wavelab
and install the package in the directory
C:\Program Files\MATLAB704\toolbox
3 Getting Started
There are several ways to get started with SparseLab. First, you can snoop around the directory
structure to see what’s there. Second, you can try running some of the demos to see what they
do. Third, you can try the pedagogical examples.
8