We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmoothminimization problems. Building on the powerful Kurdyka-Aojasiewicz property, we derive...
详细信息
We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmoothminimization problems. Building on the powerful Kurdyka-Aojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward-backward algorithms with semi-algebraic problem's data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem.
Mining and exploring databases should provide users with knowledge and new insights. Tiles of data strive to unveil true underlying structure and distinguish valuable information from various kinds of noise. We propos...
详细信息
Mining and exploring databases should provide users with knowledge and new insights. Tiles of data strive to unveil true underlying structure and distinguish valuable information from various kinds of noise. We propose a novel Boolean matrix factorization algorithm to solve the tiling problem, based on recent results from optimization theory. In contrast to existing work, the new algorithm minimizes the description length of the resulting factorization. This approach is well known for model selection and data compression, but not for finding suitable factorizations via numerical optimization. We demonstrate the superior robustness of the new approach in the presence of several kinds of noise and types of underlying structure. Moreover, our general framework can work with any cost measure having a suitable real-valued relaxation. Thereby, no convexity assumptions have to be met. The experimental results on synthetic data and image data show that the new method identifies interpretable patterns which explain the data almost always better than the competing algorithms.
We consider a broad class of regularized structured total least squares (RSTLS) problems encompassing many scenarios in image processing. This class of problems results in a nonconvex and often nonsmooth model in larg...
详细信息
We consider a broad class of regularized structured total least squares (RSTLS) problems encompassing many scenarios in image processing. This class of problems results in a nonconvex and often nonsmooth model in large dimension. To tackle this difficult class of problems we introduce a novel algorithm which blends proximal and alternating minimization methods by beneficially exploiting data information and structures inherently present in RSTLS. The proposed algorithm, which can also be applied to more general problems, is proven to globally converge to critical points and is amenable to efficient and simple computational steps. We illustrate our theoretical findings by presenting numerical experiments on deblurring large scale images, which demonstrate the viability and effectiveness of the proposed method.
We propose a general alternating minimization algorithm for nonconvex optimization problems with separable structure and nonconvex coupling between blocks of variables. To fix our ideas, we apply the methodology to th...
详细信息
We propose a general alternating minimization algorithm for nonconvex optimization problems with separable structure and nonconvex coupling between blocks of variables. To fix our ideas, we apply the methodology to the problem of blind ptychographic imaging. Compared to other schemes in the literature, our approach differs in two ways: (i) it is posed within a clear mathematical framework with practical verifiable assumptions, and (ii) under the given assumptions, it is provably convergent to critical points. A numerical comparison of our proposed algorithm with the current state of the art on simulated and experimental data validates our approach and points toward directions for further improvement.
暂无评论