title: Fast l₁-minimization algorithms for robust face recognition.
abstract: l1-minimization refers to finding the minimum l1-norm solution to an underdetermined linear system [Formula: see text]. Under certain conditions as described in compressive sensing theory, the minimum l1-norm solution is also the sparsest solution. In this paper, we study the speed and scalability of its algorithms. In particular, we focus on the numerical implementation of a sparsity-based classification framework in robust face recognition, where sparse representation is sought to recover human identities from high-dimensional facial images that may be corrupted by illumination, facial disguise, and pose variation. Although the underlying numerical problem is a linear program, traditional algorithms are known to suffer poor scalability for large-scale applications. We investigate a new solution based on a classical convex optimization framework, known as augmented Lagrangian methods. We conduct extensive experiments to validate and compare its performance against several popular l1-minimization solvers, including interior-point method, Homotopy, FISTA, SESOP-PCD, approximate message passing, and TFOCS. To aid peer evaluation, the code for all the algorithms has been made publicly available.
authors.affiliation: Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720, USA. yang@eecs.berkeley.edu
authors.forename: Allen Y
authors.initials: AY
authors.lastname: Yang
authors.forename: Zihan
authors.initials: Z
authors.lastname: Zhou
authors.forename: Arvind Ganesh
authors.initials: AG
authors.lastname: Balasubramanian
authors.forename: S Shankar
authors.initials: SS
authors.lastname: Sastry
authors.forename: Yi
authors.initials: Y
authors.lastname: Ma
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D005145:Face / Q000033:anatomy & histology*; D006801:Humans; D007089:Image Enhancement / Q000379:methods; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated / Q000379:methods*; D015203:Reproducibility of Results; D012371:Robotics / Q000379:methods*; D012680:Sensitivity and Specificity; D013382:Subtraction Technique