Sparse representation of images using alternating linear programming

Based on nonnegative matrix factorization, a set of images are represented by a product of two nonnegative matrices, over-complete basis matrix (features) and nonnegative coefficient matrix (sparse coding) in this paper. Under the objective that both basis matrix and coefficient matrix are sparse, an alternating linear programming (ALP) algorithm is proposed. And the ALP algorithm is proved to be convergent. After the very large scale alternating linear programming problems are converted to equivalent sets of linear programming subproblems, they can be solved much more efficiently. Furthermore, the ALP algorithm is extended and generalized to an alternating iterative optimization (AIO) algorithm. At last, simulation results show the validity of the proposed approach.