Test Problems¶
Introduction¶
The cr.sparse.problems
module contains a number of test
problems which can be used to quickly evaluate the correctness
and performance of a sparse recovery algorithm. The design of
these test problems is heavily influenced by Sparco cite{sparco:2007}.
We have ported several synthetic and real life problems from Sparco
to CRSparse
.
The sparse recovery problems can be modeled as (underdetermined) linear systems:
where \(\bA\) is an \(m \times n\) linear operator (real or complex), \(\bb\) is an observed measurement vector of length \(m\) and \(\br\) is an unknown measurement noise vector. Our goal is to reconstruct \(\bx\) from the observed \(\bb\). We have access to the linear operator \(\bA\).
Under compressive sensing paradigm, we may have signals \(\by\) which have a sparse representation in some sparsifying basis (or dictionary) \(\Psi\) and we sample \(\by\) via a measurement matrix \(\Phi\) given by the equation:
Expanding \(\by\), we get:
By letting \(\bA = \Phi \Psi\), we go back to the original formulation \(\bb = \bA \bx\) (assuming no noise).
\(\bb\) belongs to the measurement space. \(\by\) belongs to the signal space. \(\bx\) belongs to the representation space (or model space).
This module provides a generate
function which can be used to generate
specific test problems. Each problem has been given a name and you will need
to pass the name to the generate function (along with other problem specific
parameters) to generate an instance of a problem.
The list of problems is provided below.
An instance of a problem is described by a named tuple
Problem
. This tuple has following attributes:
Attribute 
Description 

name 
Name of the test problem 
Phi 
A linear operator \(\Phi\) representing the compressive sensing process. It may be identity operator if no sensing is involved. 
Psi 
A linear operator \(\Psi\) representing the sparsifying basis. It may be identity operator if the signal is sparse in itself. 
A 
The combined linear operator \(\bA = \Phi \Psi\). If either \(\Phi\) or \(\Psi\) are identity, then \(\bA\) bypasses them. 
b 
An array \(\bb\) representing observed measurements. For simple problems, it is a vector (1D array). For more advanced problems, it may be an nd array (e.g. an image). 
reconstruct 
A function to construct \(\by\) from \(\bx\). Typically, it is the application of the sparsifying basis operator \(\Psi\). 
x 
The sparse representation vector \(\bx\) used to construct the problem. This may not be available for all problems. If available, it can be used to assess the quality of reconstruction. 
y 
The signal \(\by\) which is being sampled by compressive sensing. This may not be available for every problem. If available, it can be used for comparing the reconstructed signal with the original signal. 
figures 
Titles of a list of figures associated with the problem. 
plot 
A function to plot individual figures associated with the problem. The figures are useful in visualizing the problem. 
Note
While the equation \(\bb = \bA \bx\) looks like a matrix vector equation, we should treat it as the application of a linear operator \(\bA\) on the data \(bx\). The data may be a vector or an image or a multichannel audio signal. The implementation of the linear operator \(\bA\) would know how to handle the data layout. One can flatten the arrays \(\bx\) and \(\bb\) to construct the corresponding matrix vector linear system. However, the matrices for the flattened systems tend to be quite sparse and hence not very efficient computationally.
Problems API¶
Data Types
A sparse signal recovery problem 
API

Returns the names of available problems 

Generates a test problem by its name and problem specific arguments 

Plots the figures associated with a problem 

Provides a quick analysis of sparse recovery by one of the algorithms in CRSparse 
List of Problems¶
Look at the associated examples to see these test problems in action.
Name 
Signal 
Dictionary 
Measurements 
Examples 

heavisine:fourier:heaviside 
HeaviSine 
FourierHeaviside 
Identity 

blocks:haar 
Blocks 
Haar Wavelet 
Identity 

cosinespikes:diracdct 
Real Cosines + Real Spikes 
DiracCosine 
Identity 

complex:sinusoidspikes:diracfourier 
Complex Sinusoids+Complex Spikes 
DiracFourier 
Identity 

cosinespikes:diracdct:gaussian 
Real Cosines + Real Spikes 
DiracCosine 
Gaussian 

piecewisecubicpoly:daubechies:gaussian 
Piecewise Cubic Polynomial 
Daubechies Wavelet 
Gaussian 

signedspikes:dirac:gaussian 
Real Signed Spikes 
Identity 
Gaussian 

complex:signedspikes:dirac:gaussian 
Complex Signed Spikes 
Identity 
Gaussian 

blocks:heaviside 
Blocks 
HeaviSide (Unnormalized) 
Identity 

blocks:normalizedheaviside 
Blocks 
HeaviSide (Normalized) 
Identity 

gaussianspikes:dirac:gaussian 
Gaussian Spikes 
Identity 
Gaussian 

srcsep1 
Mixture of Guitar and Piano Sounds 
Windowed Discrete Cosine 
Mixing Matrix 