ProPPA: A Fast Algorithm for $\ell_1$ Minimization and Low-Rank Matrix Completion (implementation)

You may have seen the name in Dirk Lorenz ppp_l1.m which implements the projection proximal point method for l^1 minimization presented in Numerical Functional Analysis and Optimization but it is a different algorithm and this one also does Low Rank Matrix Completion.

ProPPA: A Fast Algorithm for $\ell_1$ Minimization and Low-Rank Matrix Completion by Ranch Y.Q. Lai, Pong C. Yuen. The abstract reads:

We propose a Projected Proximal Point Algorithm (ProPPA) for solving a class of optimization problems. The algorithm iteratively computes the proximal point of the last estimated solution projected into an affine space which itself is parallel and approaching to the feasible set. We provide convergence analysis theoretically supporting the general algorithm, and then apply it for solving $\ell_1$-minimization problems and the matrix completion problem. These problems arise in many applications including machine learning, image and signal processing. We compare our algorithm with the existing state-of-the-art algorithms. Experimental results on solving these problems show that our algorithm is very efficient and competitive.

The algorithm implementation is here and is listed in both the Compressive Sensing Big Picture page and the Advanced Matrix Factorization Jungle page.

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.