Class BlockFrame

java.lang.Object
  extended byBlockFrame

public class BlockFrame
extends java.lang.Object

This software is now (Feb 2006) quite well tested and works very well.
Note that the term frame in this context has no connection to the class java.awt.Frame.
In this class the term frame has a mathematical meaning, being an extension of the mathematical term basis. In the context a frame is supposed to be used here, i.e. sparse representations, it could just as well be denoted as a dictionary.

Block-oriented frame representation.
A (finite) block-oriented frame can be represented by a matrix F of size N×K with N<=K. The frame has K frame vectors and each is one of the columns of F. The length of each frame vector (columns) is N. We assume that the frame vectors span the space, i.e. RN. A signal (vector) x of length N may be represented as a linear combination of the frame vectors, i.e. x=F·w, where w is a vector of length K containing the coefficients. Usually w is not unique, many possible vectors w can give an exact representation of x. In a sparse representation a sparseness constraint is imposed on the coefficients, we allow only a limited number of the coefficients, i.e. entries in w, to be non-zero.

Vector selection methods.
A set of methods are implemented for vector selection using a frame. Several variants of each method are available, making it possible to use different argument lists.

The Matching Pursuit (MP) algoritms find a sparse weight vector w such that ||x-F·w|| is minimized subject to sparseness in w. The norm used is the 2-norm. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F. The vector selection algorithms are greedy, they return when the allowed number of non-zero weights is selected or when the relative error is below a given limit. The sizes are: w is K×1, F is N×K, xr and x are N×1. OMP and ORMP are heuristic to this in general NP-hard problem, the optimal solution is usually not found, but often a acceptable good solution is found.

Matlab notes.
The class was developed to get faster functions available in Matlab. Experiments (VS2003\test02) confirm that these methods are faster than the corresponding functions in Matlab. They are almost as fast as the C++ program for vector selection. To use these Java-methods from Matlab there are some points that one must be aware of:
Only output argument is returned to Matlab, i.e. changes in arguments on the input argument list are unnoticed in Matlab.
Matlab arguments are converted to Java arguments according to Table 5-2 in Matlab documentation External interfaces (version 6), chapter 5 "Calling Java from Matlab".
Experiments done (VS2003\test02) gave only small performance differences if we used float instead of double, so there is no good reason to use float (Matlab uses double).


Constructor Summary
BlockFrame(BlockFrame fb, int M)
          Constructs a block-oriented frame by repeating another block-oriented frame M times.
BlockFrame(int sizeN, int sizeK)
          Constructs a (sizeN × sizeK) frame with random values.
BlockFrame(int sizeN, int sizeK, double[] val)
          Constructs a (sizeN × sizeK) frame with values from given array.
BlockFrame(OverlappingFrame fo, int M)
          Constructs a block-oriented frame by repeating the overlapping frame M times.
 
Method Summary
 double getIpValue(int k1, int k2)
          Returns the inner product of two frame vectors.
 int getK()
          Returns frame size variable K, number of frame vectors.
 java.lang.String getLastMessage()
          Returns the last message generated, i.e. error, warning or information message.
static int getMaxK()
           
static int getMaxN()
           
static int getMaxS()
           
 int getN()
          Returns frame size variable N, length of frame vectors.
 int getSupportEnd(int k)
          Returns the support end position of a frame vector.
 int getSupportLength(int k)
          Returns the support length of a frame vector.
 int getSupportStart(int k)
          Returns the support start position of a frame vector.
 double getValue(int k, int n)
          Returns an entry (a value) in the frame.
 boolean isUniform()
          Tells if frame is uniform, i.e. the norm of all frame vectors is one, or not.
 void makeUniform()
          Makes the frame uniform.
 double[] mult(double[] w)
          Multiplies the matrix F (the frame) by array w and returns the result in an array.
 void setValue(int k, int n, double val)
          Set an entry (a value) in the frame.
 void setValues(double[] val)
          Set new values into the frame.
 void setValues(int k, double[] val)
          Set new values to a vector in the frame.
 void setVerboseLevel(int level)
          Set how verbose functions in this class are on information-, warning- and error-messages.
 double[] trMult(double[] r)
          Multiplies the transposed of matrix F (the frame) by array r and returns the result in an array.
 double[] vsBMP(double[] x, int S)
          uses the Basic Matching Pursuit algoritm to find the sparse weight vector w such that ||x-F·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-F·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-F·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-F·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-F·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-F·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-F·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 frame 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

BlockFrame

public BlockFrame(int sizeN,
                  int sizeK)
Constructs a (sizeN × sizeK) frame with random values.

Parameters:
sizeN - length of frame vectors
sizeK - number of frame vectors

BlockFrame

public BlockFrame(int sizeN,
                  int sizeK,
                  double[] val)
Constructs a (sizeN × sizeK) frame with values from given array.

Parameters:
sizeN - length of frame vectors
sizeK - number of frame vectors
val - the values (ordered by column, i.e. by frame vectors)

BlockFrame

public BlockFrame(OverlappingFrame fo,
                  int M)
Constructs a block-oriented frame by repeating the overlapping frame M times. If the overlapping frame has size given by N, K and P, i.e. K frame vectors each of (maximal) length NP, the block-oriented frame will get size (N+P-1)M × KM.


BlockFrame

public BlockFrame(BlockFrame fb,
                  int M)
Constructs a block-oriented frame by repeating another block-oriented frame M times. If the input frame has size given by N, K, i.e. K frame vectors each of (maximal) length N, the constructed block-oriented frame will get size NM × KM.

Method Detail

getMaxN

public static int getMaxN()

getMaxK

public static int getMaxK()

getMaxS

public static int getMaxS()

getN

public int getN()
Returns frame size variable N, length of frame vectors.


getK

public int getK()
Returns frame size variable K, number of frame vectors.


isUniform

public boolean isUniform()
Tells if frame is uniform, i.e. the norm of all frame vectors is one, or not.


getLastMessage

public java.lang.String getLastMessage()
Returns the last message generated, i.e. error, warning or information message.


getValue

public double getValue(int k,
                       int n)
Returns an entry (a value) in the frame.
Matlab note: Indexing is different than in Matlab, a Matlab matrix F representing a N×K frame returns an element using F(n,k) where 1 <= n <= N and 1 <= k <= K. To get the same element from this class the syntax is fb.getValue(k-1,n-1), fb is an object of class BlockFrame.

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)
n - position in frame vector (row in frame) 0 <= n <= (N-1)

getSupportLength

public int getSupportLength(int k)
Returns the support length of a frame vector. The length will be N or shorter.

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)

getSupportStart

public int getSupportStart(int k)
Returns the support start position of a frame vector. This is the same as the number of zeros before the support range starts:
int n = getSupportStart(k);
double v = getValue(k, n);
v contains the first non-zero value of the frame vector. We will have 0 <= n <= (N-1).

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)

getSupportEnd

public int getSupportEnd(int k)
Returns the support end position of a frame vector.
int n = getSupportEnd(k);
double v = getValue(k, n-1);
v contains the last non-zero value of the frame vector. We will have 1 <= n <= N. (The case n==0 would indicate an all zero frame vector, and then it should not be in the frame.)

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)

getIpValue

public double getIpValue(int k1,
                         int k2)
Returns the inner product of two frame vectors.

Parameters:
k1 - number for the first frame vector (column in frame) 0 <= k1 <= (K-1)
k2 - number for the second frame vector (column in frame) 0 <= k2 <= (K-1)

setVerboseLevel

public void setVerboseLevel(int level)
Set how verbose functions in this class are on information-, warning- and error-messages. Last message is available with getLastMessage function.

Parameters:
level - indicate how verbose the functions in this class are
0 : print nothing at all
1 : print only error messages
2 : print error and warning messages
3 : print error, warning and information messages

setValue

public void setValue(int k,
                     int n,
                     double val)
Set an entry (a value) in the frame.
Matlab note: Indexing is different than in Matlab, a Matlab matrix F representing a N×K frame returns an element using F(n,k) where 1 <= n <= N and 1 <= k <= K. To adress the same element from this class the syntax is fb.setValue(k-1,n-1,val), fb is an object of class BlockFrame.

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)
n - position in frame vector (row in frame) 0 <= n <= (N-1)
val - a single double value to be put into the frame.

setValues

public void setValues(int k,
                      double[] val)
Set new values to a vector in the frame.
Matlab note: Indexing is different than in Matlab, in Matlab columns of matrix F are numbered 1 <= k <= K. Here the column is numbered 0 <= k <= (K-1).

Parameters:
k - frame vector number (column in frame) 0 <= k <= (K-1)
val - a length N vector of double values to be put into the frame.

setValues

public void setValues(double[] val)
Set new values into the frame.

Parameters:
val - a length N*K vector where the frame elements are ordered columnwise.

makeUniform

public void makeUniform()
Makes the frame uniform. That is scale all frame vectors so the length (2-norm) is one.


trMult

public double[] trMult(double[] r)
Multiplies the transposed of matrix F (the frame) by array r and returns the result in an array. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.
The corresponding code i Matlab notation would be: c=F'*r and the sizes are: c is K×1, F is N×K, r is N×1.

Parameters:
r - the signal (residual) that is multiplied by the frame. It is unchanged.
Returns:
the results as an array of length K.

mult

public double[] mult(double[] w)
Multiplies the matrix F (the frame) by array w and returns the result in an array. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.
The corresponding code i Matlab notation would be: xr=F*w and the sizes are: w is KL×1, F is N×K, xr is NL×1. L is an integer, L >= 1. The resulting vector (represented as an array) is formed as a linear combination of the frame vectors where the coefficients are given by the weights w.

Parameters:
w - contains the weights that are multiplied by the frame vectors. It is unchanged.
Returns:
the results (reconstructed signal) as an array of length N.

vsSelectBest

public double[] vsSelectBest(double[] x)
Finds the frame 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-F·w|| is minimum. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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-F·w|| is minimized (but not minimal) subject to sparseness in w. The sizes are: w is K×1, F is N×K, xr and x are N×1. The matrix F is the matrix implicit given by setting the frame vectors as the columns of F.

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