# basisPursuit

Recover sparse signal using the basis pursuit algorithm

## Description

example

[Xr,MSE,lambda] = basisPursuit(A,Y) recovers the sparse signal approximation Xr of Y by solving the Basis Pursuit Denoising Problem using the sensingDictionary A. The basisPursuit function also returns the minimum mean squared error MSE and the corresponding Lagrangian parameter lambda.

[Xr,MSE,lambda] = basisPursuit(___,Name=Value) specifies options using one or more name-value arguments in addition to the input argument in the previous syntax. For example, [Xr,MSE,lambda] = basisPursuit(A,Y,RelTol=5e-2) sets a relative tolerance of 5e-2.

## Examples

collapse all

Create a sensing dictionary that can be applied to the signal. Use the dct basis type.

D = sensingDictionary(Size=length(wecg),Type={'dct'});

Obtain the best fit for the signal using the dictionary and basis pursuit. Obtain the minimum mean squared error.

[XBP,MSE,lambda] = basisPursuit(D,wecg);
MSE
MSE = 1.2349e-04

Extract the sensing dictionary matrix. Use the matrix to construct the approximation.

A = subdict(D,1:D.Size(1),1:D.Size(2));
wecgR = A*XBP;

Obtain the norm of the difference between the original signal and its approximation.

norm(wecg-wecgR)
ans = 0.5029

Plot the signal and the approximation. Plot the difference at the same scale.

subplot(2,1,1)
plot(wecg)
hold on
plot(wecgR)
hold off
legend("Original","Approximation")
title("Original Signal and Approximation")
ylimits = get(gca,"YLim");
subplot(2,1,2)
plot(wecg-wecgR)
ylim(ylimits)
title("Difference Between Original Signal and Approximation")

## Input Arguments

collapse all

Sensing dictionary, specified as a sensingDictionary object.

Sensor measurements, specified as a vector Y such that Y = AX, where X is a sparse signal.

Data Types: single | double
Complex Number Support: Yes

### Name-Value Arguments

Specify optional pairs of arguments as Name1=Value1,...,NameN=ValueN, where Name is the argument name and Value is the corresponding value. Name-value arguments must appear after other arguments, but the order of the pairs does not matter.

Example: Xr = basisPursuit(A,Y,RelTol=1e-3) recovers Xr using stopping criteria based on a relative tolerance of 1e-3.

Maximum number of iterations executed to recover the sparse signal, specified as a positive integer.

Example: Xr = basisPursuit(A,Y,maxIterations=35) recovers Xr using at most 35 iterations.

Data Types: single | double

Relative tolerance used to recover the signal, specified as a positive scalar. The stopping criteria is based on the relative tolerance.

Example: Xr = basisPursuit(A,Y,RelTol=1e-3) recovers Xr using stopping criteria based on a relative tolerance of 1e-3.

Data Types: single | double

Absolute tolerance used to recover the signal, specified as a positive scalar. The stopping criteria is based on the absolute tolerance.

Example: Xr = basisPursuit(A,Y,AbsTol=1e-4) recovers Xr using stopping criteria based on a absolute tolerance of 1e-4.

Data Types: single | double

Maximum error used to recover the signal, specified as a positive scalar. The basisPursuit function recovers the Xr that satisfies

$‖Y-A{X}_{r}{‖}_{2}^{2}\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}\text{MaxErr}\text{.}$

If unspecified, Xr is the solution of the Basis Pursuit Denoising Problem.

Example: Xr = basisPursuit(A,Y,MaxErr=1e-1) recovers Xr using stopping criteria based on a maximum error of 1e-1.

Data Types: single | double

## Output Arguments

collapse all

Sparse signal recovered, returned as a vector.

Data Types: single | double
Complex Number Support: Yes

Minimum mean squared error, returned as a scalar.

Data Types: single | double

Lagrangian parameter, returned as a scalar.

Data Types: single | double

collapse all

### Basis Pursuit Denoising Problem

Basis pursuit denoising recovers the sparse signal Xr by solving

$\underset{X}{\mathrm{min}}\frac{1}{2}‖Y-AX{‖}_{2}^{2}+\lambda ‖X{‖}_{1},$

where

• A — Sensing dictionary

• Y — Measurement vector

• λ — Lagrangian parameter. Adjusting λ controls the balance between sparsity and accuracy of reconstruction.

## Version History

Introduced in R2022a