Introduction Sparse Representation Experiments Discussion

Robust Face Recognition via Sparse Representation 

Allen Y. Yang 

<yang@eecs.berkeley.edu>

April 18, 2008, NIST 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Face Recognition: “Where amazing happens”

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Face Recognition: “Where amazing happens”

Figure: Steve Nash, Kevin Garnett, Jason Kidd. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Sparse Representation 

Sparsity 

A signal is sparse if most of its coeÿcients are (approximately) zero. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Sparse Representation 

Sparsity 

A signal is sparse if most of its coeÿcients are (approximately) zero. 

1 Sparsity in frequency domain 

Figure: 2-D DCT transform. 

2 Sparsity in spatial domain 

Figure: Gene microarray data. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Sparsity in human visual cortex [Olshausen & Field 1997, Serre & Poggio 2006] 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Sparsity in human visual cortex [Olshausen & Field 1997, Serre & Poggio 2006] 

1

2

3

Feed-forward: No iterative feedback loop. 

Redundancy: Average 80-200 neurons for each feature representation. 

Recognition: Information exchange between stages is not about individual neurons, but 

rather how many neurons as a group fre together. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Problem Formulation 

1 Notation

Training: For K classes, collect training samples {v1,1, · · · , v1,n1 }, · · · , {vK,1, · · · , vK,nK } 2 RD . 

Test: Present a new y 2 R , solve for label(y) 2 [1, 2, · · · , K]. D

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Problem Formulation 

1 Notation

Training: For K classes, collect training samples {v1,1, · · · , v1,n1 }, · · · , {vK,1, · · · , vK,nK } 2 RD . 

Test: Present a new y 2 R , solve for label(y) 2 [1, 2, · · · , K]. D

2 Data representation in (long) vector form via stacking 

Figure: Assume 3-channel 640 × 480 image, D = 3 · 640 · 480. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
3

Introduction Sparse Representation Experiments Discussion

Problem Formulation 

1 Notation

Training: For K classes, collect training samples {v1,1, · · · , v1,n1 }, · · · , {vK,1, · · · , vK,nK } 2 RD . 

Test: Present a new y 2 R , solve for label(y) 2 [1, 2, · · · , K]. D

2 Data representation in (long) vector form via stacking 

Figure: Assume 3-channel 640 × 480 image, D = 3 · 640 · 480. 

Mixture subspace model for face recognition [Belhumeur et al. 1997, Basri & Jocobs 2003] 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Classifcation of Mixture Subspace Model 

  



1 Assume y belongs to Class i

y = i,1vi,1 + i,2vi,2 + · · · + i,n1 vi,ni , 

= Ai i, 

where Ai = [vi,1, vi,2, · · · , vi,ni ]. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
2

Introduction Sparse Representation Experiments Discussion

Classifcation of Mixture Subspace Model 

  









1 Assume y belongs to Class i

y = i,1vi,1 + i,2vi,2 + · · · + i,n1 vi,ni , 

= Ai i, 

where Ai = [vi,1, vi,2, · · · , vi,ni ]. 

Nevertheless, Class i is the unknown variable we need to solve: 

2 1 3 2 

4 . 5 = Ax 2 R3·640·480 Sparse representation y = [A1, A2, · · · , AK ] . . 

. 

K

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Classifcation of Mixture Subspace Model 

  





2 

Sparse representation y = [A1, A2, · · · , AK ] 4 . 5 = Ax 2 3·

. R 640·480 . . 

K

x T 0 = [ T n 0 ··· 0 i 0 ··· 0 ] 2 R . 

1 Assume y belongs to Class i

y = i,1vi,1 + i,2vi,2 + · · · + i,n1 vi,ni , 

= Ai i, 

where Ai = [vi,1, vi,2, · · · , vi,ni ]. 

2

3

Nevertheless, Class i is the unknown variable we need to solve: 

2 31 

Sparse representation encodes membership! 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Dimensionality Redunction 

1 Construct linear projection R 2 Rd×D , d is the feature dimension. 

.  ̃y = Ry = RAx0 = A ̃x0 2 Rd . 

A ̃ 2 Rd×n, but x0 is unchanged. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Dimensionality Redunction 

1 Construct linear projection R 2 Rd×D , d is the feature dimension. 

. A ̃x0 2 Rd  ̃y = Ry = RAx0 = . 

A ̃ 2 Rd×n, but x0 is unchanged. 

2 Holistic features

Eigenfaces [Turk 1991] 

Fisherfaces [Belhumeur 1997] 

Laplacianfaces [He 2005] 

3 Partial features 

4 Unconventional features 

Downsampled faces 

Random projections 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

1` -Minimization 

1 Ideal solution: `0-Minimization 

(P0) x = arg min kxk0 s.t.  ̃y = A ̃ x. x

k · k0 simply counts the number of nonzero terms. 

However, generally `0-minimization is NP-hard. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

1` -Minimization 

1 Ideal solution: `0-Minimization 

(P0) x = arg min kxk0 s.t.  ̃y = A ̃ x. x

k · k0 simply counts the number of nonzero terms. 

However, generally `0-minimization is NP-hard. 

2 Compressed sensing: Under mild condition, `0-minimization is equivalent to 

(P1) x = arg min kxk1 s.t.  ̃y = A ̃ x, x

where kxk1 = |x1| + |x2| + · · · + |xn|. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

1` -Minimization 

1 Ideal solution: `0-Minimization 

(P0) x = arg min kxk0 s.t.  ̃y = A ̃ x. x

k · k0 simply counts the number of nonzero terms. 

However, generally `0-minimization is NP-hard. 

Compressed sensing: Under mild condition, `0-minimization is equivalent to 

(P1) x = arg min kxk1 s.t.  ̃y = A ̃ x, x

where kxk1 = |x1| + |x2| + · · · + |xn|. 

`1-Ball 

2

3

`1-Minimization is convex. 

Solution equal to `0-minimization. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

1-Minimization Routines 

 

 

`

`

Matching pursuit [Mallat 1993] 

1

2

Find most correlated vector vi in A with y: i = arg max hy, vj i. 

A(i) A , xi hy, vi i, y y − xi vi. 

3 Repeat until kyk < . 

Basis pursuit [Chen 1998] 

1

2

Start with number of sparse coeÿcients m = 1. 

Select m linearly independent vectors Bm in A as a basis 

xm = B† 

my. 

Repeat swapping one basis vector in Bm with another vector not in Bm if improve ky − Bmxmk. 

If ky − Bmxmk2 < , stop; Otherwise, m m + 1, repeat Step 2. 

Quadratic solvers: y = Ax0 + z 2 Rd , where kzk2 <  

x = arg min{kxk1 + ky − Axk2} 

[LASSO, Second-order cone programming]: Much more expensive. 

3

4

Matlab Toolboxes for 1-Minimization 

`1-Magic by Candes 

SparseLab by Donoho 

cvx by Boyd 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
1

Introduction Sparse Representation Experiments Discussion

Sparse Representation Classifcation 

 



Solve (P1) ) x1. 

Project x1 onto face subspaces: 

2 3 2 3 2 3 1 0 0 0 2 0 

1(x1) = 4 . 5 , 2(x1) = 4 . 5 , · · · , K (x1) = 4

6 . 57 . (1) . . . . 0 0 K

. . 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Sparse Representation Classifcation 

 



Solve (P1) ) x1. 

1

2

Project x1 onto face subspaces: 

2 3 2 3 2 3 1 0 0 0 2 0 

1(x1) = 4 . 5 , 2(x1) = 4 . 5 , · · · , K (x1) = 4

6 . 57 . (1) . . . . 0 0 K

. . 

Defne residual ri = k ̃y − A ̃i (x1)k2 for Subject i: 

id(y) = arg mini=1,··· ,K {ri} 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Partial Features on Extended Yale B Database 

Features Nose Right Eye Mouth & Chin 

Dimension 4,270 5,040 12,936 

SRC [%] 87.3 93.7 98.3 

nearest-neighbor [%] 49.2 68.8 72.7 

nearest-subspace [%] 83.7 78.6 94.4 

Linear SVM [%] 70.8 85.8 95.3 

SRC: sparse-representation classifer 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Extension I: Outlier Rejection 

`1-Coeÿcients for invalid images 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Extension I: Outlier Rejection 

`1-Coeÿcients for invalid images 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Spar

Outlier Rejection 

When `1-solution is not sparse or concentrated to one subspace, the test sample is invalid. 

. K · maxi ki (x)k1/kxk1 − 1 Sparsity Concentration Index: SCI(x) = 2 [0, 1]. K − 1 

se Representation
Introduction Sparse Representation Experiments Discussion

Figure: ROC curve on Eigenfaces and AR database. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Extension II: Occlusion Compensation 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Extension II: Occlusion Compensation 

1 Sparse representation + sparse error 

y = Ax + e

2 Occlusion compensation 

  �  x y = A | I = Bw e

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

AR Database 

Figure: Training samples for Subject 1. 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

AR Database 

Figure: Training samples for Subject 1. 

(a) random corruption (b) occlusion

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

AR Database 

Figure: Training samples for Subject 1. 

(a) random corruption (b) occlusion

sunglasses 

97.5% 

scarves 

93.5% 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Future Directions 

Open problems:

1

2

Pose variation 

Scalability to > 1000 subjects 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Future Directions 

Open problems:

1

2

Pose variation 

Scalability to > 1000 subjects 

Other databases:

1

2

Multi-PIE (about 350 subjects) 

Chinese CASPEAL (about 1000-3000 subjects ) 

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Future Directions 

Open problems:

1

2

Pose variation 

Scalability to > 1000 subjects 

Other databases:

1

2

Multi-PIE (about 350 subjects) 

Chinese CASPEAL (about 1000-3000 subjects ) 

Wish list: Because few algorithm succeed under all-weather conditions (illumination, expression, 

pose, disguise), we are looking forward to a comprehensive database 

large number of subjects 

carefully controlled subclasses 

1

2

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation
Introduction Sparse Representation Experiments Discussion

Acknowledgments 

Collaborators 

Berkeley: Prof. Shankar Sastry 

UIUC: Prof. Yi Ma, John Wright, Arvind Ganesh 

Funding Support 

ARO MURI: Heterogeneous Sensor Networks (HSNs) 

References 

Robust Face Recognition via Sparse Representation, (in press) PAMI, 2008. 

http://www.eecs.berkeley.edu/~yang

Allen Y. Yang <yang@eecs.berkeley.edu> Robust Face Recognition via Sparse Representation