This paper introduces algorithms for the decentralized low-rank matrix completion problem. Assume a low-rank matrix W = [W ₁ ,W ₂ , ...,W _L ]. In a network, each agent observes some entries of W  . In order to recover the unobserved entries of W via decentralized computation, we factorize the unknown matrix W as the product of a public matrix X, common to all agents, and a private matrix Y = [Y ₁ ,Y ₂ , ...,Y _L ], where Y  is held by agent . Each agent alternatively updates Y  and its local estimate of X while communicating with its neighbors toward a consensus on the estimate. Once this consensus is (nearly) reached throughout the network, each agent recovers W  = XY  , and thus W is recovered. The communication cost is scalable to the number of agents, and W  and Y  are kept private to agent to a certain extent. The algorithm is accelerated by extrapolation and compares favorably to the centralized

This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex and nonconvex problems. In addition, they are easy to parallelize.

Higher-order low-rank tensors naturally arise in many applications including hyperspectral data recovery, video inpainting, seismic data recon-struction, and so on. We propose a new model to recover a low-rank tensor by simultaneously performing low-rank matrix factorizations to the all-mode ma-tricizations of the underlying tensor. An alternating minimization algorithm is applied to solve the model, along with two adaptive rank-adjusting strategies when the exact rank is not known.

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices <i>X</i> and <i>Y</i> so that the product <i>XY</i> approximates a nonnegative data matrix <i>M</i> whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of <i>M</i> are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to

In this paper, we first study \ell_q minimization and its associated iterative reweighted algorithm for recovering sparse vectors. Unlike most existing work, we focus on <i>unconstrained</i> \ell_q minimization, for which we show a few advantages on noisy measurements and/or approximately sparse vectors. Inspired by the results in [Daubechies et al., <i>Comm. Pure Appl. Math.</i>, 63 (2010), pp. 1--38] for <i>constrained</i> \ell_q minimization, we start with a preliminary yet novel analysis for <i>unconstrained</i> \ell_q minimization, which includes convergence, error bound, and local convergence behavior. Then, the algorithm and analysis are extended to the recovery of low-rank matrices. The algorithms for both vector and matrix recovery have been compared to some state-of-the-art algorithms and show superior performance on recovering sparse vectors and low-rank matrices.