# 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

 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