An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors

Abstract

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M 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 classic alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.

Cited by in corpus (59)

• An Augmented Linear Mixing Model to Address Spectral Variability for Hyperspectral Unmixing
• Parallel matrix factorization for low-rank tensor completion
• Consensus-ADMM for General Quadratically Constrained Quadratic Programming
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Spectral Superresolution of Multispectral Imagery with Joint Sparse and Low-Rank Learning
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Fast compressive Raman bio-imaging via matrix completion
• Online Nonnegative Matrix Factorization with Outliers
• Recommender systems based on graph embedding techniques: A comprehensive review
• A Parallel Douglas Rachford Algorithm for Minimizing ROF-like Functionals on Images with Values in Symmetric Hadamard Manifolds
• Compressed Nonnegative Matrix Factorization is Fast and Accurate
• Iteratively Linearized Reweighted Alternating Direction Method of Multipliers for a Class of Nonconvex Problems
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• A Multiphase Image Segmentation Based on Fuzzy Membership Functions and L1-norm Fidelity
• An Empirical Study of ADMM for Nonconvex Problems
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Spectrally Sparse Signal Recovery via Hankel Matrix Completion with Prior Information
• Tensor Completion Algorithms in Big Data Analytics
• Distributed optimization for nonrigid nano-tomography
• A General System for Heuristic Solution of Convex Problems over Nonconvex Sets
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Direction-of-Arrival Estimation for Constant Modulus Signals Using a Structured Matrix Recovery Technique
• Coupled Graphs and Tensor Factorization for Recommender Systems and Community Detection
• Tensor factorization based method for low rank matrix completion and its application on tensor completion
• An Oracle Inequality for Quasi-Bayesian Non-Negative Matrix Factorization
• A Bi-clustering Framework for Consensus Problems
• Active Target Localization using Low-Rank Matrix Completion and Unimodal Regression
• A two-level distributed algorithm for nonconvex constrained optimization
• The Application of Preconditioned Alternating Direction Method of Multipliers in Depth from Focal Stack
• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization
• Privacy-preserving Non-negative Matrix Factorization with Outliers
• A divide-and-conquer algorithm for binary matrix completion
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Hybrid Analog-Digital Transceiver Designs for Cognitive Large-Scale Antenna Array Systems
• ${\ell }_p$-Box ADMM: A Versatile Framework for Integer Programming
• An Alternating Direction Method for Total Variation Denoising
• Leveraging Two Reference Functions in Block Bregman Proximal Gradient Descent for Non-convex and Non-Lipschitz Problems
• Fast algorithms for Higher-order Singular Value Decomposition from incomplete data
• Fast and Effective Algorithms for Symmetric Nonnegative Matrix Factorization
• Low-Rank Modeling and Its Applications in Image Analysis
• ADMM for Multiaffine Constrained Optimization
• Practical Algorithms for Learning Near-Isometric Linear Embeddings
• Restricted Low-Rank Approximation via ADMM
• An ADMM-LAP method for total variation myopic deconvolution of adaptive optics retinal images
• Learning Latent Features with Pairwise Penalties in Low-Rank Matrix Completion
• A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization
• A Proximal Linearization-based Decentralized Method for Nonconvex Problems with Nonlinear Constraints
• Tensor completion using enhanced multiple modes low-rank prior and total variation
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems
• Efficient Low Rank Matrix Recovery With Flexible Group Sparse Regularization
• A Group Norm Regularized Factorization Model for Subspace Segmentation
• Global hard thresholding algorithms for joint sparse image representation and denoising
• A hybrid algorithm for the two-trust-region subproblem
• Clustering of Nonnegative Data and an Application to Matrix Completion
• An Extended ADMM for 3-Block Nonconvex Nonseparable Problems with Applications
• Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints