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 CR-Sparse.

The sparse recovery problems can be modeled as (underdetermined) linear systems:

(1)\[\bb = \bA \bx + \br\]

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:

(2)\[\bb = \Phi \by.\]

Expanding \(\by\), we get:

(3)\[\bb = \Phi \Psi \bx\]

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 multi-channel 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

Problem

A sparse signal recovery problem

API

names()	Returns the names of available problems
generate(name[, key])	Generates a test problem by its name and problem specific arguments
plot(problem[, height])	Plots the figures associated with a problem
analyze_solution(problem, solution[, perc])	Provides a quick analysis of sparse recovery by one of the algorithms in CR-Sparse

List of Problems

Look at the associated examples to see these test problems in action.

Name	Signal	Dictionary	Measurements	Examples
heavi-sine:fourier:heavi-side	HeaviSine	Fourier-Heaviside	Identity	HeaviSine Signal in Fourier-HeaviSide Basis
blocks:haar	Blocks	Haar Wavelet	Identity	Blocks Signal in Haar Basis
cosine-spikes:dirac-dct	Real Cosines + Real Spikes	Dirac-Cosine	Identity	Cosine+Spikes in Dirac-Cosine Basis
complex:sinusoid-spikes:dirac-fourier	Complex Sinusoids+Complex Spikes	Dirac-Fourier	Identity	Complex Sinusoids+Complex-Spikes in Dirac-Fourier Basis
cosine-spikes:dirac-dct:gaussian	Real Cosines + Real Spikes	Dirac-Cosine	Gaussian	Cosine+Spikes, Dirac-Cosine Basis, Gaussian Measurements
piecewise-cubic-poly:daubechies:gaussian	Piecewise Cubic Polynomial	Daubechies Wavelet	Gaussian	Piecewise Cubic, Daubechies Basis, Gaussian Measurements
signed-spikes:dirac:gaussian	Real Signed Spikes	Identity	Gaussian	Signed Spikes, Gaussian Measurements
complex:signed-spikes:dirac:gaussian	Complex Signed Spikes	Identity	Gaussian
blocks:heavi-side	Blocks	HeaviSide (Unnormalized)	Identity
blocks:normalized-heavi-side	Blocks	HeaviSide (Normalized)	Identity
gaussian-spikes:dirac:gaussian	Gaussian Spikes	Identity	Gaussian
src-sep-1	Mixture of Guitar and Piano Sounds	Windowed Discrete Cosine	Mixing Matrix	Source Separation I