Lowcomplexity Proximal GaussNewton Algorithm for Nonnegative Matrix Factorization In this paper we propose a quasiNewton algorithm for the celebrated nonnegative matrix factorization (NMF) problem. The proposed algorithm falls into the general framework of GaussNewton and LevenbergMarquardt methods. However, these methods were not able to handle constraints, which is present in NMF. One of the key contributions in this paper is to apply alternating direction method of multipliers (ADMM) to obtain the iterative update from this GaussNewtonlike algorithm. Furthermore, we carefully study the structure of the Jacobian Gramian matrix given by the GaussNewton updates, and designed a way of exactly inverting the matrix with complexity mathcalO(mnk), which is a significant reduction compared to the naive implementation of complexity mathcalO((m  n)3k3). The resulting algorithm, which we call NLSADMM, enjoys fast convergence rate brought by the quasiNewton algorithmic framework, while maintaining low periteration complexity similar to that of alternating algorithms. Numerical experiments on synthetic data confirms the efficiency of our proposed algorithm.

Fast Algorithms for Sparse ReducedRank Regression We consider a reformulation of ReducedRank Regression (RRR) and Sparse ReducedRank Regression (SRRR) as a nonconvex nondifferentiable function of a single of the two matrices usually introduced to parametrize lowrank matrix learning problems. We study the behavior of proximal gradient algorithms for the minimization of the objective. In particular, based on an analysis of the geometry of the problem, we establish that a proximal Polyakxc5x81ojasiewicz inequality is satisfied in a neighborhood of the set of optima under a condition on the regularization parameter. We consequently derive linear convergence rates for the proximal gradient descent with line search and for related algorithms in a neighborhood of the optima. Our experiments show that our formulation leads to much faster learning algorithms for RRR and especially for SRRR.