mpv2
Class MatchingPursuit

java.lang.Object
  mpv2.MatchingPursuit

public class MatchingPursuit
extends java.lang.Object

This class includes several closely related algorithmes for Matching Pursuit (MP).
MP finds a sparse, only few non-zero elements, vector w such that the product of this vector and a dictionary (matrix) is close to a given vector x. Assume w is K-by-1 and sparse, x is N-by-1, and D is N-by-K, then the MP algoritms are greedy algoritms that (try to) minimize the representation error, err = ||x - Dw||, given a sparsness limit (for w) or error limit (err).
The MP methods are:

• Select Best, return only one (the best fit) non-zero weight.
• Basic Matching Pursuit (BMP)
• Orthogonal Matching Pursuit (OMP)
• Order Recursive Matching Pursuit (ORMP)
• Partial Search (PS)

The dictionary D to use is given as an argument when an object of this class is constructed. The Dictionary should be an object of a descendant of the AllMatrices abstract class. The innerproducts, a symmetric matrix, D'*D, may be given as a second argument.
Note that the values of the matrices are not copied into this object, so any changes done after construction will affect vector seclection.
The few used methods belonging to the dictionary, which by the way should be effectivly implemented, are:

• getN(), getK(), get the dictionary (matrix) dimension
• innerProduct(k1, k2), the inner product of two columns in the matrix. The inner products may be stored in a matrix supplied when the MatchingPursuit object is constructed.
• transposeTimes(x, c), c = D'*x
• addColumn(k, s, r), r = r + s*D(:,k)

Constructor Summary

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

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

Method Summary

boolean	checkNormalized() Check if dictionary is normalized, and update the normalized indicator.
void	clearNormalized() Clear dictionary normalized indicator, set it to false, without checking.
boolean	getNormalized() Get dictionary normalized indicator without checking dictionary.
void	setNormalized() Set dictionary normalized indicator to true without checking.
double[]	vsBMP(double[] x, int S) Use 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) Do 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(AllMatrices D)

Instantiate an object of this class, and thus making the vector selection algorithms available to the calling program.

Parameters:

D - the dictionary, i.e. a matrix (object of descendant of AllMatrices)

MatchingPursuit

public MatchingPursuit(AllMatrices D,
                       SymmetricMatrix M)

Instantiate an object of this class, and thus making the vector selection algorithms available to the calling program.

Parameters:

D - the dictionary, i.e. a matrix (object of descendant of AllMatrices)

M - matrix of innerproducts (D'*D)

Method Detail

checkNormalized

public boolean checkNormalized()

Check if dictionary is normalized, and update the normalized indicator. Nornalized means that each column has 2-norm equal to 1

Returns:

a boolean that is true if dictionary is normalized

getNormalized

public boolean getNormalized()

Get dictionary normalized indicator without checking dictionary.

Returns:

the value of the dictionary normalized indicator

setNormalized

public void setNormalized()

Set dictionary normalized indicator to true without checking.

clearNormalized

public void clearNormalized()

Clear dictionary normalized indicator, set it to false, without checking.

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)

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

Do 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