basisPursuit

Recover sparse signal using the basis pursuit algorithm

Since R2022a

Syntax

[Xr,MSE,lambda] = basisPursuit(A,Y)

[Xr,MSE,lambda] = basisPursuit(___,Name=Value)

Description

[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

Basis Pursuit Approximation of Signal

Load the ECG signal.

load wecg

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

A — Sensing dictionary

sensingDictionary object

Sensing dictionary, specified as a sensingDictionary object.

Y — Sensor measurements

vector

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.

maxIterations — Maximum number of iterations

200 (default) | positive integer

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

RelTol — Relative tolerance

1e-4 (default) | positive scalar

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

AbsTol — Absolute tolerance

1e-5 (default) | positive scalar

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

MaxErr — Maximum error

positive scalar

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

$$\Vert Y-A{X}_r{\Vert }_2^2\le \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

Xr — Sparse signal

vector

Sparse signal recovered, returned as a vector.

Data Types: single | double
Complex Number Support: Yes

MSE — Minimum mean squared error

scalar

Minimum mean squared error, returned as a scalar.

Data Types: single | double

lambda — Lagrangian parameter

scalar

Lagrangian parameter, returned as a scalar.

Data Types: single | double

More About

Basis Pursuit Denoising Problem

Basis pursuit denoising recovers the sparse signal Xr by solving

$$\underset{X}{\min }\frac{1}{2}\Vert Y-AX{\Vert }_2^2+\lambda \Vert X{\Vert }_1,$$

where

• A — Sensing dictionary

• Y — Measurement vector

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

Extended Capabilities

Tall Arrays

Calculate with arrays that have more rows than fit in memory.

This function supports tall arrays with the limitations:

• If the value of the CustomDictionary property of the sensingDictionary A is a tall array, then the sensor measurements Y must also be a tall array.

For more information, see Tall Arrays.

Version History

Introduced in R2022a