Accession Number:

ADA525384

Title:

A Review of Fast L(1)-Minimization Algorithms for Robust Face Recognition

Descriptive Note:

Research rept.

Corporate Author:

CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Report Date:

2010-07-01

Pagination or Media Count:

38.0

Abstract:

1-minimization refers to finding the minimum 1-norm solution to an underdetermined linear system b Ax. It has recently received much attention, mainly motivated by the new compressive sensing theory that shows that under quite general conditions the minimum 1-norm solution is also the sparsest solution to the system of linear equations. Although the underlying problem is a linear program, conventional algorithms such as interior-point methods suffer from poor scalability for large-scale real world problems. A number of accelerated algorithms have been recently proposed that take advantage of the special structure of the 1-minimization problem. In this paper we provide a comprehensive review of five representative approaches, namely, Gradient Projection, Homotopy, Iterative Shrinkage-Thresholding, Proximal Gradient, and Augmented Lagrange Multiplier. The work 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 particular, the paper will focus on a recently proposed face recognition algorithm, where a sparse representation framework has been used to recover human identities from facial images that may be affected by illumination occlusion, and facial disguise. MATLAB implementations of the algorithms described in this paper have been made publicly available.

Subject Categories:

  • Numerical Mathematics
  • Computer Programming and Software
  • Miscellaneous Detection and Detectors

Distribution Statement:

APPROVED FOR PUBLIC RELEASE