Home for SRC

What is SRC

SRC, Sparse Representation-based Classification, is an algorithm in Pattern Recognition area.

Sparse linear combination

Training sample vector

$A_{i} = [ v_{i,1} , v_{i,2} , ... , v_{i,n_{i}} ]\in IR^{m\times n_{i}}$

Test sample y be projected in the relevant linear space of its class.

$y = a _{i,1}v _{i,1} + a _{i,2}v _{i,2} + ... + a _{i,ni}v _{i,ni}$

Training sample set

$A = [ A_{1}, A_{2},..., A_{k} ] = [ v_{1,1}, v_{1,2},..., v_{k,n_{k}} ]$

Training sample y should be

$y = Ax_{0} \in IR^{m}$

In which the x。should be

$x_{0} = [0,...,0,a_{i,1}, a_{i,2},...,a_{i,n_{i}}, 0,...,0]^{T} \in IR^{n}$

It is not only one solution for y = Ax since it is always underdetermined.

We could determine the solution by calculate the minimum L2 norm.

(L2) $\hat{x}_{2} = arg[ min ||x||_{2} ]$ In which the Ax = y.

The resolved x2 is dense in general. It is hard to be classified.

In stead, we will looking for the sparsest resolution for the following formula, in which the Ax = y. The procedure to solve is a NP problem.

(L0) $\hat{x}_{0} = arg[ min ||x||_{0} ]$

We could find the approximate solution of L1 norm instead of L0 norm.

(L1) $\hat{x}_{1} = arg[ min ||x||_{1} ]$ in which the Ax = y.

L1 norm can be resolved by standard linear programming tool for polynomial. It will be more efficient if the resolution is sparse.

There is noise in the real data,

$y = Ax_{0} + z$ in which $z\in IR^{m}$ is a noise.

So , x。can be resolved by approximate solution of L1 norm.

$(L^{_{s}^{l}}) \hat{x}_{1} = arg [min||x||_{1}]$ , in which $|| Ax - y ||_{2} \leqslant \varepsilon$

Sparse Representation

Use $\delta _{i}$ as the eigenfunction to filter the corresponding coefficient of class i. It is a new vector in which the non-zero values are related to class i. We can classify y by the minimum residual between y and $\hat{y}_{i}$

$min_{i} : r_{i}(y) = ||y - A\delta _{i} (\hat{x_{i}})||_{2}$

SRC Algorithm

1 Input : Training sample matrix

$A = [ A_{1}, A_{2}, ... , A_{k}] \in IR^{m \times n}$

for k kinds of classes, test samples $y \in IR^{m \times n}$ , Fault tolerance coefficient $\varepsilon \geqslant 0$

2 Normalize the columns of A , to make L2 norm unit.

3 Minimize L1 :

$\hat{x}_{1} = arg [min||x||_{1}]$ , in which $||Ax - y ||_{2} \leq \varepsilon$

4 Calculate the residual.

$r_{i}(y) = || y - A\delta _{i} (\hat{x}_{1})_{2}$

5 Output : Make choice among $(y) = arg [min_{i}r_{i}(y)]$

Test result on ORL face lib.

There are 40 classes in ORL face lib. Choose 5 as training samples in each class. Choose the left 5 as the test samples in each class.

Firstly use the PCA as feature extraction. Project the training samples on principal vectors. Then classify the test samples by SRC classifier.

The recognition rate is 96% when the PCA=80 .

How to run

1 Config the two ORL face lib path in file orl_src.m . Default path is E:\ORL_face\orlnumtotal\

2 Run orl_src.m

Provide feedback

Saved searches

Use saved searches to filter your results more quickly