Fast L1-Minimization Algorithms and an Application in Robust Face Recognition: A Review

Authors:
Yang, Allen
Ganesh, Arvind
Sastry, Shankar
Ma, Yi
Technical Report Identifier: EECS-2010-13
February 5, 2010
EECS-2010-13.pdf

Abstract: L1-minimization solves the minimum L1-norm solution to an underdetermined linear system y=Ax. It has recently received much attention, mainly motivated by the new compressive sensing theory that shows that under certain conditions an L1-minimization solution is also the sparsest solution to that system. Although classical solutions to L1-minimization have been well studied in the past, including primal-dual interior-point methods and orthogonal matching pursuit, they suffer from either expensive computational cost or insufficient estimation accuracy in many real-world, large-scale applications. In the past five years, many new algorithms have been proposed. We provide a comprehensive review of five representative approaches, namely, gradient projection, homotopy, iterative shrinkage-thresholding, proximal gradient, and alternating direction. The repository is intended to fill in a gap in the existing literature to systematically benchmark the performance of these algorithms using a consistent experimental setting. In addition, the experiment will be focused on the application of robust face recognition, where a sparse representation framework has recently been developed to recover human identities from facial images that may be affected by illumination, occlusion, and facial disguise. The paper also provides useful guidelines to practitioners working in similar fields.