matchingPursuit

Recover sparse signal using matching pursuit algorithm

Since R2022a

Syntax

[Xr,YI,I,R] = matchingPursuit(A,Y)

[Xr,YI,I,R] = matchingPursuit(___,Name=Value)

Description

[Xr,YI,I,R] = matchingPursuit(A,Y) recovers the sparse signal Xr using the sensingDictionary A and sensor measurement Y. By default, the sparse recovery algorithm is matching pursuit. The I output is the support of Xr identified by the matching pursuit algorithm. The YI output is the best fit for Y corresponding to the bases indexed by the elements of I, and R is the residual.

[Xr,YI,I,R] = matchingPursuit(___,Name=Value) specifies options using one or more name-value arguments in addition to the input argument in the previous syntax. For example, [Xr,YI,I,R] = matchingPursuit(A,Y,Algorithm="WMP") specifies the weak matching pursuit algorithm.

Examples

Obtain Sparse Approximation

Load a signal.

load cuspamax

Create a sensing dictionary consisting of the basis types poly and walsh that can be applied to the signal.

lsig = length(cuspamax);
A = sensingDictionary(Size=lsig,Type={'poly','walsh'})

A = 
  sensingDictionary with properties:

                Type: {'poly'  'walsh'}
                Name: {''  ''}
               Level: [0 0]
    CustomDictionary: []
                Size: [1024 2048]

Use the dictionary to obtain a sparse approximation of the signal using weak matching pursuit.

[Xr,YI,I,R] = matchingPursuit(A,cuspamax, ...
    Algorithm="WMP",maxerr={"L2",1});

Plot the original signal and the approximation.

plot(cuspamax,"k")
hold on
plot(YI,LineWidth=2)
legend("Original Signal","Weak Matching Pursuit")
hold off

Extract the vectors from the dictionary that correspond to the approximation. Multiply with the associated coefficients and confirm the result is equal to the approximation.

Amat = subdict(A,1:1024,I);
x = Amat*Xr(I,:);
max(abs(x-YI))

ans = 
0

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 = matchingPursuit(D,Y,Algorithm="WMP") recovers the sparse signal using weak matching pursuit.

Algorithm — Recovery algorithm

"BMP" (default) | "OMP" | "WMP"

Recovery algorithm, specified as one of these:

• "BMP" — Matching pursuit

• "OMP" — Orthogonal matching pursuit

• "WMP" — Weak matching pursuit

For more information, see Matching Pursuit Algorithms.

Example: [Xr,YI,I,R] = matchingPursuit(D,Y,Algorithm="OMP") recovers the sparse signal using orthogonal matching pursuit.

wmpcfs — Optimality factor

0.6 (default) | positive scalar

Optimality factor for weak orthogonal matching pursuit, specified as a scalar in the interval (0,1]. This option is valid only when Algorithm is "WMP".

Example: [Xr,YI,I,R] = matchingPursuit(D,Y,Algorithm="WMP",wmpcfs=0.7) specifies an optimality factor of 0.7.

Data Types: single | double

maxIterations — Maximum number of iterations

25 (default) | positive integer

Maximum number of iterations to recover the sparse signal, specified as a positive integer. The pursuit algorithm stops if the number of iterations reaches maxIterations. Note that the number of iterations matchingPursuit performs to recover the sparse signal is equal to the length of the index vector I.

Example: [Xr,YI,I,R] = matchingPursuit(D,Y,maxIterations=15) iterates at most 15 times to recover the sparse signal.

Data Types: single | double

maxerr — Maximum error criteria

{"L2",1} (default) | cell

Maximum error criteria used to recover the sparse signal, specified as cell array {NORME,ME}. NORME specifies the norm used in the error computation. Valid options are "L1", "L2", and "Linf". ME is a positive scalar in the interval (0,100] that specifies the maximum percentage of the relative admissible value.

The relative error expressed as a percentage is

$$100\frac{\Vert R\Vert }{\Vert Y\Vert }$$

where R is the residual at each iteration and Y is the input signal. For example, {"L1",10} sets maximum acceptable ratio of the L1 norms of the residual to the input signal to 0.10.

If you specify maxerr, the matching pursuit terminates when the first of the following conditions is satisfied:

• The number of iterations reaches maxIterations.

• The relative error falls below the percentage you specify with the maxerr name-value argument.

Example: [Xr,YI,I,R] = matchingPursuit(D,Y,maxerr={"L1",20}) specifies the L1 norm and a relative error of 20%.

Data Types: cell

Output Arguments

Xr — Sparse signal

vector

Sparse signal recovered, returned as a vector.

Data Types: single | double
Complex Number Support: Yes

YI — Best fit

vector

Best fit to the sensor measurements, returned as a vector. YI is the best fit for Y corresponding to the bases indexed by the elements of I. The best fit is defined as YI = A(:,I)*Xr(I,:).

Data Types: single | double
Complex Number Support: Yes

I — Index

vector

Index of basis elements identified by the matching pursuit algorithm, returned as a vector. For matching pursuit algorithms, the length of I corresponds to the number of iterations the algorithm needed before termination.

Data Types: double

R — Residual

vector

Residual, returned as a vector. The vectors R and Y are equal in size. The residual is defined as R = Y-(A(:,I)*Xr(I,:)) = Y-YI.

Data Types: single | double
Complex Number Support: Yes

Version History

Introduced in R2022a