Face Recognition from Incomplete Measurements via l₁-Optimization

Miguel Argaez, Reinaldo Sanchez, Carlos Ramirez

Department of Mathematical Sciences, The University of Texas at El Paso, El Paso, USA.
Program in Computational Science, The University of Texas at El Paso, El Paso, USA.

DOI: 10.4236/ajcm.2012.24039                

Abstract

In this work, we consider a homotopic principle for solving large-scale and dense l₁underdetermined problems and its applications in image processing and classification. We solve the face recognition problem where the input image contains corrupted and/or lost pixels. The approach involves two steps: first, the incomplete or corrupted image is subject to an inpainting process, and secondly, the restored image is used to carry out the classification or recognition task. Addressing these two steps involves solving large scale l₁minimization problems. To that end, we propose to solve a sequence of linear equality constrained multiquadric problems that depends on a regularization parameter that converges to zero. The procedure generates a central path that converges to a point on the solution set of the l₁underdetermined problem. In order to solve each subproblem, a conjugate gradient algorithm is formulated. When noise is present in the model, inexact directions are taken so that an approximate solution is computed faster. This prevents the ill conditioning produced when the conjugate gradient is required to iterate until a zero residual is attained.

Keywords

Sparse Representation; l₁Minimization; Face Recognition; Sparse Recovery; Interior Point Methods;Sparse Regularization

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	B. K. Natarajan, “Sparse Approximate Solutions to Linear Systems”, SIAM Journal on Computing, Vol. 24, No. 2, 1995, pp. 227-234. doi:10.1137/S0097539792240406
[2]	M. Figueiredo, R. Nowak and S. Wright, “Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other Inverse Problems,” IEEE Journal of Selected Topics in Signal Processing, Vol. 1, No. 4, 2007, pp. 586-597.
[3]	E. Hale, W. Yin and Y. Zhang, “A Fixed-Point Continuation Method for l1Regularized Minimization with Applications to Compresses Sensing,” Technical Report TR07-07, Department of Computational and Applied Mathematics, Rice University, Houston, 2007.
[4]	S. Kim, K. Koh, M. Lustig, S. Boyd and D. Gorinvesky, “A Method for Large-Scale lsub>1-Regularized Least Squares Problems with Applications in Signal Processing and Statistics,” IEEE Journal of Selected Topics in Signal Processing, 2007. www.stanford.edu/?boyd/l1_ls.html
[5]	E. Candes, J. Romberg and T. Tao, “Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information,” IEEE Transactions on Information Theory, Vol. 52, No. 2, 2006, pp. 489-509. doi:10.1109/TIT.2005.862083
[6]	S. Chen, D. Donoho and M. Saunders, “Atomic Decomposition by Basis Pursuit,” SIAM Review, Vol. 43, No. 1, 2001, pp. 129-159. doi:10.1137/S003614450037906X
[7]	D. Donoho, “Compressed Sensing,” IEEE Transactions on Information Theory, Vol. 52, No. 4, 2006, pp. 1289-1306. doi:10.1109/TIT.2006.871582
[8]	S. Chen, D. Donoho and M. Saunders, “Atomic Decomposition by Basis Pursuit,” SIAM Review, Vol. 43, No. 1, 2001, pp. 129-159. doi:10.1137/S003614450037906X
[9]	D. Donoho and X. Huo, “Uncertainty Principles and Ideal Atomic Decomposition,” IEEE Transactions on Information Theory, Vol. 47, No. 7, 2001, pp. 2845-2862. doi:10.1109/18.959265
[10]	M. Argaez, C. Ramirez and R. Sanchez, “An l1Algorithm for Underdetermined Systems and Applications,” IEEE Conference Proceedings on North American Fuzzy Information Processing Society, El Paso, 18-20 March 2011, pp. 1-6. doi:10.1109/NAFIPS.2011.5752016
[11]	S. Wright, R. Nowak and M. Figueiredo, “Sparse Reconstruction by Separable Approximation,” IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2008, Las Vagas, 31 March-4 April 2008. doi:10.1109/ICASSP.2008.4518374
[12]	R. Kohavi, “A Study of Cross-Validation and Bootstrap for Accuracy Estimation and Model Selection,” Proceedings of International Joint Conference on AI, Quebec, 20-25 August 1995, pp. 1137-1145.
[13]	R. Sanchez, M. Argáez and P. Guillen. “Sparse Representation via l1-Minimization for Underdetermined Systems in Classification of Tumors with Gene Expression Data. IEEE 33rd Annual International Conference Proceedings of the Engineering in Medicine and Biology Society, Boston, 30 August-3 September 2011, pp. 3362- 3366.
[14]	J. Wright, Y. Yang, A. Ganesh, S. Shankar and Y. Ma, “Robust Face Recognition via Sparse Representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 31, No. 2, 2009, pp. 210-227. doi:10.1109/TPAMI.2008.79