aboutsparselab.tex

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

\WavePath\ from $<$ MatlabToolboxPath $>$ \BS \WLName\ to
$<$MatlabToolboxPath$>$ \BS 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{enumerate}

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 \BS Toolbox \BS 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$>$ \BS local
 \end{enumerate}


\subsection{Success}

When you have a successful installation,
you should see something like the following when you invoke \Matlab:

\begin{verbatim}
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    - 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"

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


\end{verbatim}

\section{Getting Started}

There are several ways to get started with \WaveLab. 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.

\subsection{Snooping}

If you just snoop around in the \WaveLab\ file structure, you will notice many
directories and a great range of different information about the system itself
and what it can do.  We list here some basic facts.

\subsubsection{Contents Files}

Each directory has a {\tt Contents.m} file, which explains the
contents and purpose of that directory. The directory {\tt Solvers}
contains the central program solver tools; its {\tt Contents.m} file
looks as follows:
\begin{verbatim}
% SparseLab Solvers Directory
%
% This is directory houses the solvers for the SparseLab package.
%
%              .m files in this directory
%
%   Contents.m           -    This file
%   fdrthresh.m          -    Uses the False Discovery Rate to Threshold a
%                             Signal
%   HardThresh.m         -    Implements Hard Thresholding
%   lsqrms.m             -    Iterative least squares
%   pdco.m               -    Primal-Dual Barrier Method for Convex
%                             Objectives (Michael Saunders 2003)
%   pdcoSet.m            -    creates or alters options structure for
%                             pdco.m
%   SoftThresh.m         -    Soft Thresholding
%   SolveBP.m            -    Basis Pursuit
%   SolveIRWLS.m         -    Iteratively ReWeighted Least Squares
%   SolveIST.m           -    Iterative Soft Thresholding
%   SolveISTBlock.m      -    Iterative Soft Thresholding, block variant
%                             with least squares projection
%   SolveLasso.m         -    Implements LARS/Lasso Agorithms
%   SolveMP.m            -    Matching Pursuit
%   SolveOMP.m           -    Orthogonal Matching Pursuit
%   SolveStepwise.m      -    Forward Stepwise
%   SolveStepwiseFDR.m   -    Forward Stepwise with FDR Threshold
%   SolveStOMP.m         -    Stagewise Orthogonal Matching Pursuit
%

%
% 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}

\subsubsection{Help for Functions}

Each function in \WaveLab\ has help documentation.  For example,
{\tt SolveMP} is Mallat and Zhang's Matching Pursuit algorithm. If
you are in \Matlab\ and type {\tt help SolveMP}, \Matlab\ will type
out the following documentation:

\begin{verbatim}
% SolveMP: Matching Pursuit (non-orthogonal)
% Usage
%   [sol iters activationHist] = SolveMP(A, b, maxIters, NoiseLevel, verbose)
% Input
%   A           dictionary (dxn matrix), rank(A) = min(d,n) by assumption
%   y           data vector, length d.
%   maxIters    number of atoms in the decomposition
%   NoiseLevel  estimated norm of noise, default noiseless, i.e. 1e-5
%   verbose     1 to print out detailed progress at each iteration, 0 for
%               no output (default)
% Outputs
%    sol             solution of MP
%    iters           number of iterations performed
%    activationHist  Array of indices showing elements entering
%                    the solution set
% Description
%   SolveMP implements the greedy pursuit algorithm to estimate the
%   solution of the sparse approximation problem
%      min ||x||_0 s.t. A*x = y
% See Also
%   SolveOMP
% References
%   Matching Pursuit With Time-Frequency Dictionaries (1993) Mallat, Zhang
%   IEEE Transactions on Signal Processing
%
\end{verbatim}

\subsubsection{Source Browsing}

All the algorithms in \WaveLab\ are available for inspection. For
example, if you are in \Matlab\ and type {\tt type SolveMP} you get
the following documentation:

\begin{verbatim}
function [sol iters activationHist] = SolveMP(A, y, maxIters,
NoiseLevel, verbose)
% SolveMP: Matching Pursuit (non-orthogonal)
% Usage
%   [sol iters activationHist] = SolveMP(A, b, maxIters, NoiseLevel, verbose)
% Input
%   A           dictionary (dxn matrix), rank(A) = min(d,n) by assumption
%   y           data vector, length d.
%   maxIters    number of atoms in the decomposition
%   NoiseLevel  estimated norm of noise, default noiseless, i.e. 1e-5
%   verbose     1 to print out detailed progress at each iteration, 0 for
%               no output (default)
% Outputs
%    sol             solution of MP
%    iters           number of iterations performed
%    activationHist  Array of indices showing elements entering
%                    the solution set
% Description
%   SolveMP implements the greedy pursuit algorithm to estimate the
%   solution of the sparse approximation problem
%      min ||x||_0 s.t. A*x = y
% See Also
%   SolveOMP
% References
%   Matching Pursuit With Time-Frequency Dictionaries (1993) Mallat, Zhang
%   IEEE Transactions on Signal Processing
%


if nargin < 5,
    verbose = 0;
end

if nargin < 4,
    NoiseLevel = 1e-5;
end

if nargin < 3,
    maxIters = 10*length(y);
end

% Initialize
[d,n] = size(A); activationHist = []; iters = 0; res = y; sol =
zeros(n,1);

normb = norm(y); resnorm = normb; coef = [];

while (iters < maxIters) & (resnorm > NoiseLevel)

    [maxcorr i] = max(abs(A'*res));
    newIndex = i(1);

    % Project residual onto maximal vector
    Ai = A(:, newIndex);
    newCoeff = res' * Ai;
    res = res - (newCoeff ./ norm(Ai)) .* Ai;

    % Update solution
    sol(newIndex) = sol(newIndex) + newCoeff;
    activationHist = [activationHist newIndex];

    if verbose
        fprintf('Iteration %d: Adding variable %d\n', iters, newIndex);
    end
    iters = iters+1;

    resnorm = norm(res);

end

%
% Part of SparseLab Version:100
% Built:Sunday,18-Dec-2005 00:00:00
% This is Copyrighted Material
% For Copying permissions see COPYING.m
% Comments? e-mail [e-mail]
%
\end{verbatim}

Notice that the source contains information about the author and
date of compilation, as well as copyright, of the routine.  Also,
the help information is built in as the first thing following the
function header.

\subsubsection{Documentation Directory}

The \WaveLab\ system also has extensive built-in documentation about the system
itself.  If you look in the directory {\tt Documentation}, you will find several
files of general interest:

\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 v090
% WARRANTY                -  No Warranty on SparseLab software
%
%              Subdirectories
%
%   AboutSparseLab        -  documentation for AboutSparseLab document
%   SparseLaArchitecture  -  documentation for SparseLabArchitecture document

\end{verbatim}



\subsubsection{Dataset Documentation}

Datasets are also documented. If you look in the directory {\tt
Datasets}, you will find that each dataset (\dotraw\ or \dotasc) is
accompanied by a \dotdoc\ file.
%The dataset {\tt daubechies.raw} is
%accompanied by the file {\tt daubechies.doc}, which contains the
%following:

%\begin{verbatim}
%daubechies.raw -- Gray-scale image of Ingrid Daubechies

%Access
%   Ingrid = ReadImage('Daubechies');

%Size
%   256 by 256

%Gray Levels
%   256

%Description
%   Ingrid Daubechies is a very active researcher in the field of
%   wavelet analysis and author of the book "Ten Lectures on Wavelets",
%   SIAM, 1992.  She is inventor of smooth orthonormal wavelets
%   of compact support.

%Source
%   Photograph of Ingrid Daubechies at the 1993 AMS winter meetings
%   in San Antonio, Texas. Taken by David Donoho with Canon XapShot
%   video still frame camera.
%\end{verbatim}

\subsection{Demos}

After browsing around to see what files \WaveLab\ contains,
it's time to see what \WaveLab\ can do!

The subdirectory {\tt \WLName /Papers} itself contains several subdirectories; each one of these
contains scripts that were used to produce figures in our published articles.