Fast L1-Minimization Algorithms For Robust Face Recognition

By Allen Yuqing Yang, Zihan Zhou, Arvind Ganesh, S. Sastry, Yi Ma. 2010

311 citations recorded by the source corpus.

L1-minimization refers to finding the minimum L1-norm solution to an underdetermined linear system b=Ax. Under certain conditions as described in compressive sensing theory, the minimum L1-norm solution is also the sparsest solution. In this paper, our study addresses 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 very 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 (ALM). The new convex solvers provide a viable solution to real-world, time-critical applications such as face recognition. We conduct extensive experiments to validate and compare the performance of the ALM algorithms against several popular L1-minimization solvers, including interior-point method, Homotopy, FISTA, SESOP-PCD, approximate message passing (AMP) and TFOCS. To aid peer evaluation, the code for all the algorithms has been made publicly available.

Subfields: Aerospace Engineering, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/ae8d60c777e6cd82eec6e59d32d7af4f27c1727f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

From Denoising to Compressed Sensing (2014, unknown): “See [17], [18] for a complete set of references.”
Visual Domain Adaptation: A survey of recent advances (2015, unknown): “One can also adapt fast `1 solvers for sparse coding [96], [97] rather than using greedy orthogonal matching pursuit algorithms.”
A Generalized Iterated Shrinkage Algorithm for Non-convex Sparse Coding (2013, methodology): “Then, by simply replacing the soft-thresholding operator in ALM by the proposed GST operator, we can embed the proposed GISA algorithm into the ALM method for solving the SRC model with arbitrary values of p and q .”
Parallel Direction Method of Multipliers (2014, unknown): “For large scale optimization problems, it is often difficult to solve the entire augmented Lagrangian efficiently.”