Main Content

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

    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")

    Figure contains 2 axes objects. Axes object 1 with title Original Signal and Approximation contains 2 objects of type line. These objects represent Original, Approximation. Axes object 2 with title Difference Between Original Signal and Approximation contains an object of type line.

    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

    YAXr22MaxErr.

    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

    More About

    collapse all

    Basis Pursuit Denoising Problem

    Basis pursuit denoising recovers the sparse signal Xr by solving

    minX12YAX22+λX1,

    where

    • A — Sensing dictionary

    • Y — Measurement vector

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

    Extended Capabilities

    Version History

    Introduced in R2022a