Sparse Representation-based Object Recognition - Sparse Representations and Compressive Sensing for Imaging and Vision - page 64

with coefficients α ij ∈ R . The above equation can be written more compactly as

y = B α , (5.5)

where

T

α =[ α 11 ,..., α 1 n | α 21 ,..., α 2 n |......| α L 1 ,..., α Ln ] (5.6)

T denotes the transposition operation. We assume that given sufficient training
samples of the k th class, B k , any new test image y

and .

N that belongs to the same class
will lie approximately in the linear span of the training samples from the class k .
This implies that most of the coefficients not associated with class k in ( 5.6 ) will be
close to zero. Hence,

∈ R

is be a sparse vector.
In order to represent an observed vector y

α

N

∈ R as a sparse vector α , one needs to

solve the system of linear equations ( 5.5 ). Typically L N and hence the system

of linear equations ( 5.5 ) is under-determined and has no unique solution. As we saw
earlier, if

. n

α is sparse enough and B satisfies certain properties, then the sparsest α

can be recovered by solving the following optimization problem

α α 1

α .

ˆ

α = arg min subject to y = B (5.7)

When noisy observations are given, Basis Pursuit DeNoising (BPDN) can be used
to approximate α

α α 1

α 2 ≤ ε ,

ˆ

α = arg min subject to y − B (5.8)

where we have assumed that the observations are of the following form

y = B α + η (5.9)

with .

Given an observation vector y from one of the L classes in the training set, one
can compute its coefficients ˆ

η ≤ ε

2

by solving either ( 5.7 )or( 5.8 ). One can perform
classification based on the fact that high values of the coefficients

α

ˆ

will be
associated with the columns of B from a single class. This can be done comparing
how well the different parts of the estimated coefficients,

α

ˆ

,represent y .The
minimum of the representation error or the residual error can then be used to
identify the correct class. The residual error of class k is calculated by keeping
the coefficients associated with that class and setting the coefficients not associated
with class k to zero. This can be done by introducing a characteristic function,
Π k :

α

n n , that selects the coefficients associated with the k th class as follows

R → R

ˆ

r k ( y )= y − B Π k ( α ) . (5.10)

2