Allen Yang, Arvind Ganesh, Shankar Sastry and Yi Ma

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2010-13
February 5, 2010

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-13.pdf

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.

BibTeX citation:

@techreport{Yang:EECS-2010-13,
    Author = {Yang, Allen and Ganesh, Arvind and Sastry, Shankar and Ma, Yi},
    Title = {Fast L1-Minimization Algorithms and An Application in Robust Face Recognition: A Review},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2010},
    Month = {Feb},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-13.html},
    Number = {UCB/EECS-2010-13},
    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.}
}

EndNote citation:

%0 Report
%A Yang, Allen
%A Ganesh, Arvind
%A Sastry, Shankar
%A Ma, Yi
%T Fast L1-Minimization Algorithms and An Application in Robust Face Recognition: A Review
%I EECS Department, University of California, Berkeley
%D 2010
%8 February 5
%@ UCB/EECS-2010-13
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-13.html
%F Yang:EECS-2010-13