An Underdetermined Peaceman-Rachford Splitting Algorithm with Application to Highly Nonsmooth Sparse Learning Problems

• Activity Number: 166
• Type: Topic Contributed
• Date/Time: Monday, August 5, 2013 : 10:30 AM to 12:20 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Zhaoran Wang*+ and Han Liu and Xiaoming Yuan
• Companies: Princeton University and Princeton University and Hong Kong Baptist University
• Keywords: Optimization ; Peaceman-Rachford Splitting Method ; Sparse Learning ; $L_p$-regression ; image reconstruction

Abstract

We propose a new operator-splitting algorithm named Underdetermined Peaceman-Rachford Splitting (UPS) Method for solving highly nonsmooth optimization problems. Our algorithm is related to the Peaceman-Rachford Splitting Method (PRSM) but with an extra relaxation parameter $a\in(0,1)$. When $a\rightarrow 1$, it reduces to the PRSM algorithm. Theoretically, our algorithm converges even in the settings where PRSM fails. Let $k$ be the number of iterations. Under the variational inequality framework, we prove the $O(1/k)$ rate of convergence of UPS. Our algorithm is suitable for solving highly nonsmooth optimization problem. As applications, we apply UPS to the sparse $L_{p}$-regression problem and the image reconstruction problem. UPS outperforms other algorithms on both synthetic and real-world data.