Representation recovery via L₁-norm minimization with corrupted data

Abstract

This paper studies the recovery probability of a state-of-the-art sparse recovery method, the optimization problem of YALL1, which has been rigorously used in face recognition, dense error correction, anomaly detection, etc. This work generalizes a theoretical work which is based on a special case of the optimization problem of YALL1. Furthermore, the new results cover more practical cases which do not fulfill the bouquet model proposed in the early work. The results also show that not only the special case but also some other cases of the optimization problem of YALL1; which fulfill certain conditions; can also recover any sufficiently sparse coefficient vector x when the fraction of the support of the error e is bounded away from 1 and the support of x is a very small fraction of its dimension m as m becomes large. The trade-off parameter λ in the optimization problem of YALL1 allows the recovery probability to be optimally tuned than the special case. Experimental results also show that the optimization problem of YALL1 (the Eq. (7)) with primal augmented Lagrangian optimization technique outperforms the state-of-the-art sparse recovery methods using their corresponding optimization techniques in term of the speed.