mp
Class MatchingPursuit

java.lang.Object
  mp.MatchingPursuit

public class MatchingPursuit

extends java.lang.Object

This class includes several closely related algorithmes for Matching Pursuit. These are Basic Matching Pursuit (BMP), Orthogonal Matching Pursuit (OMP), Order Recursive Matching Pursuit (ORMP) and Partial Search (PS). The dictionary D to use is given when an object of this class is created.

Constructor Summary

MatchingPursuit(MPDictionary D)
Instantiate an object of this class, and thus making the vector selection algorithms available to the calling program.

Method Summary

double[]	vsBMP(double[] x, int S) Uses the Basic Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsOMP(double[] x, double errLim) Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsOMP(double[] x, int S) Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsOMP(double[] x, int S, double errLim) Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsORMP(double[] x, double errLim) Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsORMP(double[] x, int S) Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsORMP(double[] x, int S, double errLim) Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w.
double[]	vsPS(double[] x, int S, double errLim, int nComb) Does Vector Selection by Partial Search.
double[]	vsSelectBest(double[] x) Finds the dictionary vector that best match the given signal.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MatchingPursuit

public MatchingPursuit(MPDictionary D)

Instantiate an object of this class, and thus making the vector selection algorithms available to the calling program. The dictionary to use is given as input argument.

Parameters:

D - the dictionary

Method Detail

vsSelectBest

public double[] vsSelectBest(double[] x)

Finds the dictionary vector that best match the given signal. The returned weight vector w will have one non-zero entry and it is selected such that the 2-norm of the residual is minimized, i.e. ||x-D·w|| is minimum.
The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

Returns:

the results, the sparse weight vector (one non-zero value)

vsBMP

public double[] vsBMP(double[] x,                      int S)

Uses the Basic Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - the number of allowed non-zero weights in w.

Returns:

the results, the sparse weight vector.

vsOMP

public double[] vsOMP(double[] x,                      int S)

Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - the number of allowed non-zero weights in w. Note that when this function is called from Matlab we must have int32(S) as argument.

Returns:

the results, the sparse weight vector

vsOMP

public double[] vsOMP(double[] x,                      double errLim)

Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

errLim - function returns when this error limit is reached, i.e. ||r|| < errLim·||x||, or when maximum number of vectors are selected.

Returns:

the results, the sparse weight vector

vsOMP

public double[] vsOMP(double[] x,                      int S,                      double errLim)

Uses the Orthogonal Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - the number of allowed non-zero weights in w

errLim - function returns when this error limit is reached, i.e. ||r|| < errLim·||x||, or when maximum number of vectors are selected.

Returns:

the results, the sparse weight vector

vsORMP

public double[] vsORMP(double[] x,                       int S)

Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - the number of allowed non-zero weights in w. Note that when this function is called from Matlab we must have int32(S) as argument.

Returns:

the results, the sparse weight vector

vsORMP

public double[] vsORMP(double[] x,                       double errLim)

Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

errLim - function returns when this error limit is reached, i.e. ||r|| < errLim·||x||, or when maximum number of vectors are selected.

Returns:

the results, the sparse weight vector

vsORMP

public double[] vsORMP(double[] x,                       int S,                       double errLim)

Uses the Order Recursive Matching Pursuit algoritm to find the sparse weight vector w such that ||x-D·w|| is minimized (but not minimal) subject to sparseness in w. The dimensions are: D is N×K, x is N×1, and w is K×1.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - the number of allowed non-zero weights in w

errLim - function returns when this error limit is reached, i.e. ||r|| < errLim·||x||, or when maximum number of vectors are selected.

Returns:

the results, the sparse weight vector

vsPS

public double[] vsPS(double[] x,                     int S,                     double errLim,                     int nComb)

Does Vector Selection by Partial Search.

Parameters:

x - the signal to be approximated by the sparse representation. It is unchanged.

S - allowed number of non-zeros weights in w, or frame vectors used.

errLim - function returns when this error limit is reached, i.e. ||r|| < errLim·||x||, or when maximum number of vectors are selected.

nComb - number of combinations to do

Returns:

the results, the sparse weight vector