We consider the nonnegative matrix factorization (NMF) problem with sparsity constraints formulated as a nonconvex composite minimization problem. We introduce four novel proximal gradient based algorithms proven globally convergent to a critical point and which are applicable to sparsity constrained NMF models. Our approach builds on recent results allowing one to lift the classical global Lipschitz continuity requirement through the use of a non-Euclidean Bregman based distance. Since under the proposed framework we are not restricted by the gradient Lipschitz continuity assumption, we can consider new decomposition settings of the NMF problem. Two of the derived schemes are genuine non-Euclidean proximal methods that tackle nonstandard decompositions of the NMF problem. The two other schemes are novel extensions of the well-known state-of-the-art methods (the multiplicative and hierarchical alternating least squares), thus allowing one to significantly broaden the scope of these algorithms. Numerical experiments illustrate the performance of the proposed methods.

We consider the class of Iterative Shrinkage-Thresholding Algorithms (ISTA) for solving linear inverse problems arising in signal/image processing. This class of methods is attractive due to its simplicity, however, they are also known to converge quite slowly. In this paper we present a Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) which preserves the computational simplicity of ISTA, but with a global rate of convergence which is proven to be significantly better, both theoretically and practically. Initial promising numerical results for wavelet-based image deblurring demonstrate the capabilities of FISTA.

Abstract. We consider the class of iterative shrinkage-thresholding algorithms (ISTA) for solving linear inverse problems arising in signal/image processing. This class of methods, which can be viewed as an extension of the classical gradient algorithm, is attractive due to its simplicity and thus is adequate for solving large-scale problems even with dense matrix data. However, such methods are also known to converge quite slowly. In this paper we present a new fast iterative shrinkage-thresholding algorithm (FISTA) which preserves the computational simplicity of ISTA but with a global rate of convergence which is proven to be significantly better, both theoretically and practically. Initial promising numerical results for wavelet-based image deblurring demonstrate the capabilities of FISTA which is shown to be faster than ISTA by several orders of magnitude.

This paper studies gradient-based schemes for image denoising and deblurring problems based on the discretized total variation (TV) minimization model with constraints. We derive a fast algorithm for the constrained TV-based image deburring problem. To achieve this task, we combine an acceleration of the well known dual approach to the denoising problem with a novel monotone version of a fast iterative shrinkage/thresholding algorithm (FISTA) we have recently introduced. The resulting gradient-based algorithm shares a remarkable simplicity together with a proven global rate of convergence which is significantly better than currently known gradient projections-based methods. Our results are applicable to both the anisotropic and isotropic discretized TV functionals. Initial numerical results demonstrate the viability and efficiency of the proposed algorithms on image deblurring problems with box constraints.

Center-based partitioning clustering algorithms rely on minimizing an appropriately formulated objective function, and different formulations suggest different possible algorithms. In this paper, we start with the standard nonconvex and nonsmooth formulation of the partitioning clustering problem. We demonstrate that within this elementary formulation, convex analysis tools and optimization theory provide a unifying language and framework to design, analyze and extend hard and soft center-based clustering algorithms, through a generic algorithm which retains the computational simplicity of the popular k-means scheme. We show that several well known and more recent center-based clustering algorithms, which have been derived either heuristically, or/and have emerged from intuitive analogies in physics, statistical techniques and information theoretic perspectives can be recovered as special cases of the proposed analysis and we streamline their relationships.

Minimization problems involving phi -entropy functionals (a generalization of Boltzmann-Shannon entropy) are studied over a given set A and a sequence of sets A/sub n/ and the properties of their optimal solutions x/sub phi /, x/sub n/. Under certain conditions on the objective functional and the sets A and A/sub n/, it is proven that as n increases to infinity, the optimal solution x/sub n/ converges in L/sub 1/ norm to the test phi -entropy estimate x/sub phi /.>

A new generalized average mutual information measure (GAMIM) is introduced in terms of Csiszar\phi-divergence, and the associated rate distortion functionR_{\phi}is studied. The main objective is to derive in a unified way a dual representation ofR_{\phi}, then to use it to generalize classical results (corresponding to\phi(t) = t \log t) in rate distortion theory and extend results associated with other concepts of GAMIM. Our development uses the methodology of convex programming duality extensively.