A fast $\ell_1$-solver and its applications to robust face recognition

Huining Qiu; Xiaoming Chen; Wanquan Liu; Guanglu Zhou; Yiju Wang; Jianhuang Lai

doi:10.3934/jimo.2012.8.163

Previous Article
Topological essentiality in infinite games
JIMO Home
This Issue
Next Article
A common cycle approach for solving the economic lot and inspection scheduling problem

January 2012, 8(1): 163-178. doi: 10.3934/jimo.2012.8.163

A fast $\ell_1$-solver and its applications to robust face recognition

Huining Qiu ^1, , Xiaoming Chen ^1, , Wanquan Liu ^2, , Guanglu Zhou ^2, , Yiju Wang ^3, and Jianhuang Lai ^1,

1.	Sun Yat-sen Univeristy, NO.135 Xiguangxi Road, Guangzhou 510275, China, China, China
2.	Curtin University, GPO Box U1987, Perth, WA 6845, Australia, Australia
3.	Qufu Normal University, Rizhao 276800, Shandong, China

Received February 2011 Revised July 2011 Published November 2011

Abstract
Related Papers

In this paper we apply a recently proposed Lagrange Dual Method (LDM) to design a new Sparse Representation-based Classification (LDM-SRC) algorithm for robust face recognition problem. The proposed approach improves the efficiency of the SRC algorithm significantly. The proposed algorithm has the following advantages: (1) it employs the LDM $\ell_1$-solver to find solution of the $\ell_1$-norm minimization problem, which is much faster than other state-of-the-art $\ell_1$-solvers, e.g. $\ell_1$-magic and $\ell_1-\ell_2$. (2) The LDM $\ell_1$-solver utilizes a new Lagrange-dual reformulation of the original $\ell_1$-norm minimization problem, not only reducing the problem size when the dimension of training image data is much less than the number of training samples, but also making the dual problem become smooth and convex. Therefore it converts the non-smooth $\ell_1$-norm minimization problem into a sequence of smooth optimization problems. (3) The LDM-SRC algorithm can maintain good recognition accuracy whilst reducing the computational time dramatically. Experimental results are presented on some benchmark face databases.

Keywords: $\ell_1$ optimization, Compressed sensing, Lagrange dual, face recognition..

Mathematics Subject Classification: Primary: 65D18, 68U10; Secondary: 65K0.

Citation: Huining Qiu, Xiaoming Chen, Wanquan Liu, Guanglu Zhou, Yiju Wang, Jianhuang Lai. A fast $\ell_1$-solver and its applications to robust face recognition. Journal of Industrial & Management Optimization, 2012, 8 (1) : 163-178. doi: 10.3934/jimo.2012.8.163

References:

[1]	M. S. Bartlett, J. R. Movellan and T. J. Sejnowski, Face recognition by independent component analysis,, IEEE Transactions on Neural Networks, 6 (2002), 1450. doi: 10.1109/TNN.2002.804287. Google Scholar
[2]	M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", John Wiley & Sons, (1979). Google Scholar
[3]	P. N. Belhumeur, J. Hespanha and D. J. Kriegman, Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 7 (1997), 711. doi: 10.1109/34.598228. Google Scholar
[4]	E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions,, SIAM Journal on Scientific Computing, 31 (): 890. Google Scholar
[5]	S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar
[6]	R. H. Byrd, P. Lu, J. Nocedal and C. Zhu, A limited memory algorithm for bound constrained optimization,, SIAM Journal on Scientific Computing, 16 (1995), 1190. doi: 10.1137/0916069. Google Scholar
[7]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,, IEEE Transactions on Information Theory, 52 (2006), 489. doi: 10.1109/TIT.2005.862083. Google Scholar
[8]	E. J. Candès and M. Wakin, An introduction to compressive sampling,, IEEE Signal Processing Magazine, 2 (2008), 21. Google Scholar
[9]	E. J. Candès and J. Romberg, The code package $\mathcall_1$ -magic:, , (). Google Scholar
[10]	R. Chellappa, P. Sinha and P. J. Phillips, Face recognition by computers and humans,, Computer, 2 (2010), 46. doi: 10.1109/MC.2010.37. Google Scholar
[11]	I. Dagher and R. Nachar, Face recognition using IPCA-ICA algorithm,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (2006), 996. doi: 10.1109/TPAMI.2006.118. Google Scholar
[12]	D. L. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar
[13]	M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, Selected Topics in IEEE Journal of Signal Processing, 4 (2007), 586. doi: 10.1109/JSTSP.2007.910281. Google Scholar
[14]	J.-J. Fuchs, On sparse representations in arbitrary redundant bases,, IEEE Transactions on Information Theory, 50 (2004), 1341. doi: 10.1109/TIT.2004.828141. Google Scholar
[15]	J.-J. Fuchs, Recovery of exact sparse representations in the presence of noise,, Proceedings of the IEEE International Conference on Acoustics, 2 (2004). Google Scholar
[16]	J.-J. Fuchs, Fast implementation of a $mathcall_1$-$\mathcall_1$ regularized sparse representations algorithm,, Proceedings of the IEEE International Conference on Acoustics, (2009), 3329. Google Scholar
[17]	X. He, S. Yan, Y. Hu, P. Niyogi and H. Zhang, Face recognition using laplacianfaces,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 3 (2005), 328. Google Scholar
[18]	K. Koh, S.-J. Kim and S. Boyd, The code package $\mathcall_1-\mathcall_s$:, , (). Google Scholar
[19]	D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization,, Nature, 6755 (1999), 788. Google Scholar
[20]	S. Z. Li, X. Hou, H. Zhang and Q. Cheng, Learning spatially localized, parts-based representation,, Proceedings of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'01), 1 (2001). Google Scholar
[21]	P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer, J. Chang, K. Hoffman, J. Marques, J. Min and W. Worek, Overview of the face recognition grand challenge,, Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 1 (2005), 947. Google Scholar
[22]	P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer and W. Worek, Preliminary face recognition grand challenge results,, The 7^th International Conference on Automatic Face and Gesture Recognition (AFGR'06), (2006), 15. Google Scholar
[23]	J. Lu, K. N. Plataniotis and A. N. Venetsanopoulos, Face recognition using LDA-based algorithms,, IEEE Transactions on Neural Networks, 1 (2003), 195. Google Scholar
[24]	O. L. Mangasarian and R. R. Meyer, Nonlinear perturbation of linear programs,, SIAM Journal on Control and Optimization, 17 (1979), 745. doi: 10.1137/0317052. Google Scholar
[25]	A. M. Martinez and A. C. Kak, PCA versus LDA,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2001), 228. doi: 10.1109/34.908974. Google Scholar
[26]	A. J. O'Toole, P. J. Phillips and A. Narvekar, FRVT 2002 evaluation report,, NISTIR TR-6965, (2003). Google Scholar
[27]	P. J. Phillips, W. T. Scruggs, A. J. O'Toole, P. J. Flynn, K. W. Bowyer, C. L. Schott and M. Sharpe, FRVT 2006 and ICE 2006 large-scale experimental results,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 5 (2010), 831. doi: 10.1109/TPAMI.2009.59. Google Scholar
[28]	M. Turk and A. Pentland, Eigenfaces for recognition,, Journal of Cognitive Neuroscience, 1 (1991), 71. doi: 10.1162/jocn.1991.3.1.71. Google Scholar
[29]	H.-Y. Wang and X.-J. Wu, Weighted PCA space and its application in face recognition,, Proceedings of 2005 International Conference on Machine Learning and Cybernetics, 7 (2005), 4522. Google Scholar
[30]	X.-G. Wang and X.-O. Tang, A unified framework for subspace face recognition,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9 (2004), 1222. doi: 10.1109/TPAMI.2004.57. Google Scholar
[31]	Y. Wang, G. Zhou, L. Caccetta and W. Liu, An alternative Lagrange-dual based algorithm for sparse signal reconstruction,, IEEE Transactions on Signal Processing, 4 (2011), 1895. doi: 10.1109/TSP.2010.2103066. Google Scholar
[32]	J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry and Yi Ma, Robust face recognition via sparse representation,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2009), 210. doi: 10.1109/TPAMI.2008.79. Google Scholar
[33]	S. J. Wright, R. D. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479. doi: 10.1109/TSP.2009.2016892. Google Scholar
[34]	J. Yang and Y. Zhang, Alternating direction algorithms for $\mathcall_1$ problems in compressive sensing,, SIAM Journal on Scientific Computing, 33 (2011), 250. doi: 10.1137/090777761. Google Scholar
[35]	S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang and S. Lin, Graph embedding and extensions: A general framework for dimensionality reduction,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1 (2007), 40. doi: 10.1109/TPAMI.2007.250598. Google Scholar
[36]	W. Zhao, R. Chellappa, P. J. Phillips and A. Rosenfeld, Face recognition: A literature survey,, ACM Computing Surveys, 4 (2003), 399. doi: 10.1145/954339.954342. Google Scholar

show all references

References:

[1]	M. S. Bartlett, J. R. Movellan and T. J. Sejnowski, Face recognition by independent component analysis,, IEEE Transactions on Neural Networks, 6 (2002), 1450. doi: 10.1109/TNN.2002.804287. Google Scholar
[2]	M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", John Wiley & Sons, (1979). Google Scholar
[3]	P. N. Belhumeur, J. Hespanha and D. J. Kriegman, Eigenfaces vs. Fisherfaces: Recognition using class specific linear projection,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 7 (1997), 711. doi: 10.1109/34.598228. Google Scholar
[4]	E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions,, SIAM Journal on Scientific Computing, 31 (): 890. Google Scholar
[5]	S. Boyd and L. Vandenberghe, "Convex Optimization,", Cambridge University Press, (2004). Google Scholar
[6]	R. H. Byrd, P. Lu, J. Nocedal and C. Zhu, A limited memory algorithm for bound constrained optimization,, SIAM Journal on Scientific Computing, 16 (1995), 1190. doi: 10.1137/0916069. Google Scholar
[7]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,, IEEE Transactions on Information Theory, 52 (2006), 489. doi: 10.1109/TIT.2005.862083. Google Scholar
[8]	E. J. Candès and M. Wakin, An introduction to compressive sampling,, IEEE Signal Processing Magazine, 2 (2008), 21. Google Scholar
[9]	E. J. Candès and J. Romberg, The code package $\mathcall_1$ -magic:, , (). Google Scholar
[10]	R. Chellappa, P. Sinha and P. J. Phillips, Face recognition by computers and humans,, Computer, 2 (2010), 46. doi: 10.1109/MC.2010.37. Google Scholar
[11]	I. Dagher and R. Nachar, Face recognition using IPCA-ICA algorithm,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (2006), 996. doi: 10.1109/TPAMI.2006.118. Google Scholar
[12]	D. L. Donoho, Compressed sensing,, IEEE Transactions on Information Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar
[13]	M. A. T. Figueiredo, R. D. Nowak and S. J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems,, Selected Topics in IEEE Journal of Signal Processing, 4 (2007), 586. doi: 10.1109/JSTSP.2007.910281. Google Scholar
[14]	J.-J. Fuchs, On sparse representations in arbitrary redundant bases,, IEEE Transactions on Information Theory, 50 (2004), 1341. doi: 10.1109/TIT.2004.828141. Google Scholar
[15]	J.-J. Fuchs, Recovery of exact sparse representations in the presence of noise,, Proceedings of the IEEE International Conference on Acoustics, 2 (2004). Google Scholar
[16]	J.-J. Fuchs, Fast implementation of a $mathcall_1$-$\mathcall_1$ regularized sparse representations algorithm,, Proceedings of the IEEE International Conference on Acoustics, (2009), 3329. Google Scholar
[17]	X. He, S. Yan, Y. Hu, P. Niyogi and H. Zhang, Face recognition using laplacianfaces,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 3 (2005), 328. Google Scholar
[18]	K. Koh, S.-J. Kim and S. Boyd, The code package $\mathcall_1-\mathcall_s$:, , (). Google Scholar
[19]	D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization,, Nature, 6755 (1999), 788. Google Scholar
[20]	S. Z. Li, X. Hou, H. Zhang and Q. Cheng, Learning spatially localized, parts-based representation,, Proceedings of 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'01), 1 (2001). Google Scholar
[21]	P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer, J. Chang, K. Hoffman, J. Marques, J. Min and W. Worek, Overview of the face recognition grand challenge,, Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), 1 (2005), 947. Google Scholar
[22]	P. J. Phillips, P. J. Flynn, T. Scruggs, K. W. Bowyer and W. Worek, Preliminary face recognition grand challenge results,, The 7^th International Conference on Automatic Face and Gesture Recognition (AFGR'06), (2006), 15. Google Scholar
[23]	J. Lu, K. N. Plataniotis and A. N. Venetsanopoulos, Face recognition using LDA-based algorithms,, IEEE Transactions on Neural Networks, 1 (2003), 195. Google Scholar
[24]	O. L. Mangasarian and R. R. Meyer, Nonlinear perturbation of linear programs,, SIAM Journal on Control and Optimization, 17 (1979), 745. doi: 10.1137/0317052. Google Scholar
[25]	A. M. Martinez and A. C. Kak, PCA versus LDA,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2001), 228. doi: 10.1109/34.908974. Google Scholar
[26]	A. J. O'Toole, P. J. Phillips and A. Narvekar, FRVT 2002 evaluation report,, NISTIR TR-6965, (2003). Google Scholar
[27]	P. J. Phillips, W. T. Scruggs, A. J. O'Toole, P. J. Flynn, K. W. Bowyer, C. L. Schott and M. Sharpe, FRVT 2006 and ICE 2006 large-scale experimental results,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 5 (2010), 831. doi: 10.1109/TPAMI.2009.59. Google Scholar
[28]	M. Turk and A. Pentland, Eigenfaces for recognition,, Journal of Cognitive Neuroscience, 1 (1991), 71. doi: 10.1162/jocn.1991.3.1.71. Google Scholar
[29]	H.-Y. Wang and X.-J. Wu, Weighted PCA space and its application in face recognition,, Proceedings of 2005 International Conference on Machine Learning and Cybernetics, 7 (2005), 4522. Google Scholar
[30]	X.-G. Wang and X.-O. Tang, A unified framework for subspace face recognition,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 9 (2004), 1222. doi: 10.1109/TPAMI.2004.57. Google Scholar
[31]	Y. Wang, G. Zhou, L. Caccetta and W. Liu, An alternative Lagrange-dual based algorithm for sparse signal reconstruction,, IEEE Transactions on Signal Processing, 4 (2011), 1895. doi: 10.1109/TSP.2010.2103066. Google Scholar
[32]	J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry and Yi Ma, Robust face recognition via sparse representation,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2009), 210. doi: 10.1109/TPAMI.2008.79. Google Scholar
[33]	S. J. Wright, R. D. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation,, IEEE Transactions on Signal Processing, 57 (2009), 2479. doi: 10.1109/TSP.2009.2016892. Google Scholar
[34]	J. Yang and Y. Zhang, Alternating direction algorithms for $\mathcall_1$ problems in compressive sensing,, SIAM Journal on Scientific Computing, 33 (2011), 250. doi: 10.1137/090777761. Google Scholar
[35]	S. Yan, D. Xu, B. Zhang, H.-J. Zhang, Q. Yang and S. Lin, Graph embedding and extensions: A general framework for dimensionality reduction,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1 (2007), 40. doi: 10.1109/TPAMI.2007.250598. Google Scholar
[36]	W. Zhao, R. Chellappa, P. J. Phillips and A. Rosenfeld, Face recognition: A literature survey,, ACM Computing Surveys, 4 (2003), 399. doi: 10.1145/954339.954342. Google Scholar

[1]	Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[2]	Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[3]	Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[4]	Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[5]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[6]	Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379
[7]	Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[8]	Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[9]	Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021 doi: 10.3934/naco.2021008
[10]	Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[11]	Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[12]	Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045
[13]	Ravi Anand, Dibyendu Roy, Santanu Sarkar. Some results on lightweight stream ciphers Fountain v1 & Lizard. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020128
[14]	Hirofumi Notsu, Masato Kimura. Symmetry and positive definiteness of the tensor-valued spring constant derived from P1-FEM for the equations of linear elasticity. Networks & Heterogeneous Media, 2014, 9 (4) : 617-634. doi: 10.3934/nhm.2014.9.617
[15]	Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

A fast $\ell_1$-solver and its applications to robust face recognition

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

A fast $\ell_1$-solver and its applications to robust face recognition

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors