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

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 and 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-1464. doi: 10.1109/TNN.2002.804287.
[2]	M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms," John Wiley & Sons, New York-Chichester-Brisbane, 1979.
[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-720. doi: 10.1109/34.598228.
[4]	E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM Journal on Scientific Computing, 31 (2008/09), 890-912.
[5]	S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, Cambridge, 2004.
[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-1208. doi: 10.1137/0916069.
[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-509. doi: 10.1109/TIT.2005.862083.
[8]	E. J. Candès and M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 2 (2008), 21-30.
[9]	E. J. Candès and J. Romberg, The code package $\mathcall_1$ -magic: http://www.acm.caltech.edu/l1magic.
[10]	R. Chellappa, P. Sinha and P. J. Phillips, Face recognition by computers and humans, Computer, 2 (2010), 46-55. doi: 10.1109/MC.2010.37.
[11]	I. Dagher and R. Nachar, Face recognition using IPCA-ICA algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (2006), 996-1000. doi: 10.1109/TPAMI.2006.118.
[12]	D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[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-597. doi: 10.1109/JSTSP.2007.910281.
[14]	J.-J. Fuchs, On sparse representations in arbitrary redundant bases, IEEE Transactions on Information Theory, 50 (2004), 1341-1344. doi: 10.1109/TIT.2004.828141.
[15]	J.-J. Fuchs, Recovery of exact sparse representations in the presence of noise, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'04), 2 (2004), II-533-II-536.
[16]	J.-J. Fuchs, Fast implementation of a $mathcall_1$-$\mathcall_1$ regularized sparse representations algorithm, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'09), (2009), 3329-3332.
[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-340.
[18]	K. Koh, S.-J. Kim and S. Boyd, The code package $\mathcall_1-\mathcall_s$: http://www.stanford.edu/~boyd/l1_ls.
[19]	D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 6755 (1999), 788-791.
[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), I-207-I-212.
[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-954.
[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-24.
[23]	J. Lu, K. N. Plataniotis and A. N. Venetsanopoulos, Face recognition using LDA-based algorithms, IEEE Transactions on Neural Networks, 1 (2003), 195-200.
[24]	O. L. Mangasarian and R. R. Meyer, Nonlinear perturbation of linear programs, SIAM Journal on Control and Optimization, 17 (1979), 745-752. doi: 10.1137/0317052.
[25]	A. M. Martinez and A. C. Kak, PCA versus LDA, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2001), 228-233. doi: 10.1109/34.908974.
[26]	A. J. O'Toole, P. J. Phillips and A. Narvekar, FRVT 2002 evaluation report, NISTIR TR-6965, 2003.
[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-846. doi: 10.1109/TPAMI.2009.59.
[28]	M. Turk and A. Pentland, Eigenfaces for recognition, Journal of Cognitive Neuroscience, 1 (1991), 71-86. doi: 10.1162/jocn.1991.3.1.71.
[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-4527.
[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-1228. doi: 10.1109/TPAMI.2004.57.
[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-1901. doi: 10.1109/TSP.2010.2103066.
[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-227. doi: 10.1109/TPAMI.2008.79.
[33]	S. J. Wright, R. D. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.
[34]	J. Yang and Y. Zhang, Alternating direction algorithms for $\mathcall_1$ problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278. doi: 10.1137/090777761.
[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-51. doi: 10.1109/TPAMI.2007.250598.
[36]	W. Zhao, R. Chellappa, P. J. Phillips and A. Rosenfeld, Face recognition: A literature survey, ACM Computing Surveys, 4 (2003), 399-458. doi: 10.1145/954339.954342.

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-1464. doi: 10.1109/TNN.2002.804287.
[2]	M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms," John Wiley & Sons, New York-Chichester-Brisbane, 1979.
[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-720. doi: 10.1109/34.598228.
[4]	E. van den Berg and M. P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM Journal on Scientific Computing, 31 (2008/09), 890-912.
[5]	S. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, Cambridge, 2004.
[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-1208. doi: 10.1137/0916069.
[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-509. doi: 10.1109/TIT.2005.862083.
[8]	E. J. Candès and M. Wakin, An introduction to compressive sampling, IEEE Signal Processing Magazine, 2 (2008), 21-30.
[9]	E. J. Candès and J. Romberg, The code package $\mathcall_1$ -magic: http://www.acm.caltech.edu/l1magic.
[10]	R. Chellappa, P. Sinha and P. J. Phillips, Face recognition by computers and humans, Computer, 2 (2010), 46-55. doi: 10.1109/MC.2010.37.
[11]	I. Dagher and R. Nachar, Face recognition using IPCA-ICA algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, 6 (2006), 996-1000. doi: 10.1109/TPAMI.2006.118.
[12]	D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.
[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-597. doi: 10.1109/JSTSP.2007.910281.
[14]	J.-J. Fuchs, On sparse representations in arbitrary redundant bases, IEEE Transactions on Information Theory, 50 (2004), 1341-1344. doi: 10.1109/TIT.2004.828141.
[15]	J.-J. Fuchs, Recovery of exact sparse representations in the presence of noise, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'04), 2 (2004), II-533-II-536.
[16]	J.-J. Fuchs, Fast implementation of a $mathcall_1$-$\mathcall_1$ regularized sparse representations algorithm, Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP'09), (2009), 3329-3332.
[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-340.
[18]	K. Koh, S.-J. Kim and S. Boyd, The code package $\mathcall_1-\mathcall_s$: http://www.stanford.edu/~boyd/l1_ls.
[19]	D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 6755 (1999), 788-791.
[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), I-207-I-212.
[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-954.
[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-24.
[23]	J. Lu, K. N. Plataniotis and A. N. Venetsanopoulos, Face recognition using LDA-based algorithms, IEEE Transactions on Neural Networks, 1 (2003), 195-200.
[24]	O. L. Mangasarian and R. R. Meyer, Nonlinear perturbation of linear programs, SIAM Journal on Control and Optimization, 17 (1979), 745-752. doi: 10.1137/0317052.
[25]	A. M. Martinez and A. C. Kak, PCA versus LDA, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 (2001), 228-233. doi: 10.1109/34.908974.
[26]	A. J. O'Toole, P. J. Phillips and A. Narvekar, FRVT 2002 evaluation report, NISTIR TR-6965, 2003.
[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-846. doi: 10.1109/TPAMI.2009.59.
[28]	M. Turk and A. Pentland, Eigenfaces for recognition, Journal of Cognitive Neuroscience, 1 (1991), 71-86. doi: 10.1162/jocn.1991.3.1.71.
[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-4527.
[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-1228. doi: 10.1109/TPAMI.2004.57.
[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-1901. doi: 10.1109/TSP.2010.2103066.
[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-227. doi: 10.1109/TPAMI.2008.79.
[33]	S. J. Wright, R. D. Nowak and M. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), 2479-2493. doi: 10.1109/TSP.2009.2016892.
[34]	J. Yang and Y. Zhang, Alternating direction algorithms for $\mathcall_1$ problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278. doi: 10.1137/090777761.
[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-51. doi: 10.1109/TPAMI.2007.250598.
[36]	W. Zhao, R. Chellappa, P. J. Phillips and A. Rosenfeld, Face recognition: A literature survey, ACM Computing Surveys, 4 (2003), 399-458. doi: 10.1145/954339.954342.

[1]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[2]	Hui Huang, Eldad Haber, Lior Horesh. Optimal estimation of $\ell_1$-regularization prior from a regularized empirical Bayesian risk standpoint. Inverse Problems and Imaging, 2012, 6 (3) : 447-464. doi: 10.3934/ipi.2012.6.447
[3]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[4]	Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[5]	Pengbo Geng, Wengu Chen. Unconstrained $ \ell_1 $-$ \ell_2 $ minimization for sparse recovery via mutual coherence. Mathematical Foundations of Computing, 2020, 3 (2) : 65-79. doi: 10.3934/mfc.2020006
[6]	Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[7]	Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021191
[8]	Shuhua Xu, Fei Gao. Weighted two-phase supervised sparse representation based on Gaussian for face recognition. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1385-1400. doi: 10.3934/dcdss.2015.8.1385
[9]	Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060
[10]	Caiping Liu, Heungwing Lee. Lagrange multiplier rules for approximate solutions in vector optimization. Journal of Industrial and Management Optimization, 2012, 8 (3) : 749-764. doi: 10.3934/jimo.2012.8.749
[11]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[12]	Liang Ding, Weimin Han. Morozov's discrepancy principle for $ \alpha\ell_1-\beta\ell_2 $ sparsity regularization. Inverse Problems and Imaging, , () : -. doi: 10.3934/ipi.2022035
[13]	Yi An, Zhuohan Li, Changzhi Wu, Huosheng Hu, Cheng Shao, Bo Li. Earth pressure field modeling for tunnel face stability evaluation of EPB shield machines based on optimization solution. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1721-1741. doi: 10.3934/dcdss.2020101
[14]	Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm. Mathematical Foundations of Computing, 2020, 3 (3) : 205-218. doi: 10.3934/mfc.2020020
[15]	Jae Deok Kim, Ganguk Hwang. Cross-layer modeling and optimization of multi-channel cognitive radio networks under imperfect channel sensing. Journal of Industrial and Management Optimization, 2015, 11 (3) : 807-828. doi: 10.3934/jimo.2015.11.807
[16]	Jian-Wu Xue, Xiao-Kun Xu, Feng Zhang. Big data dynamic compressive sensing system architecture and optimization algorithm for internet of things. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1401-1414. doi: 10.3934/dcdss.2015.8.1401
[17]	Qian Zhao, Bitao Jiang, Xiaogang Yu, Yue Zhang. Collaborative mission optimization for ship rapid search by multiple heterogeneous remote sensing satellites. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2805-2826. doi: 10.3934/jimo.2021092
[18]	Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[19]	Ying Gao, Xinmin Yang, Jin Yang, Hong Yan. Scalarizations and Lagrange multipliers for approximate solutions in the vector optimization problems with set-valued maps. Journal of Industrial and Management Optimization, 2015, 11 (2) : 673-683. doi: 10.3934/jimo.2015.11.673
[20]	Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021028

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Huining Qiu Xiaoming Chen Wanquan Liu Guanglu Zhou Yiju Wang Jianhuang Lai
on Google Scholar
Huining Qiu Xiaoming Chen Wanquan Liu Guanglu Zhou Yiju Wang Jianhuang Lai

[Back to Top]