Source-linked AI summary
An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
Yangyang Xu, Wotao Yin, Zaiwen Wen, Yin Zhang
TL;DR
The paper addresses recovery of incomplete nonnegative matrices whose structure is both low-rank and factorable into nonnegative components. It proposes an ADM-based algorithm for the resulting non-convex constrained least-squares problem and establishes conditional convergence properties. Across image-recovery experiments, the method generally outperforms matrix-completion methods that do not exploit nonnegativity, while convergence guarantees remain assumption-dependent.
Problem
The problem is to recover incomplete nonnegative data using nonnegative low-rank factors, combining gaps addressed separately by NMF and LRMC.
Method
The method solves the non-convex constrained least-squares formulation with alternating direction augmented Lagrangian updates over split factor and completion variables.
Results
Across incomplete grayscale and hyperspectral image tasks, the proposed algorithm generally produces better recovery quality than FPCA and LMaFit at larger sample rates.
Takeaways & Limitations
Using nonnegativity alongside low-rankness is practically useful for applications such as hyperspectral unmixing and can reduce required sampling of imaging data.
Takeaways & Limitations
Convergence is conditional because the formulation is non-convex with multiple update blocks; the theorem requires bounded multipliers and an additional condition.
Abstract
from arXiv · showhide
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.
1 Introduction
NMFC combines nonnegative matrix factorization with low-rank matrix completion to recover incomplete nonnegative data using nonnegative factors. The paper motivates this formulation, reviews related algorithms, and positions its ADM-based method as an extension for incomplete data.
- Problem formulation: NMFC finds nonnegative factors X and Y that minimize reconstruction error for partially observed entries of a nonnegative matrix.The factor width q may differ from the matrix rank r, yielding an approximate formulation when singular values decay rapidly.
- Relationship to existing problems: NMFC combines NMF, which uses complete nonnegative data, with LRMC, which completes incomplete data without requiring nonnegativity.Its model explicitly uses the observed-entry index set and fixed factor width q.
- Motivation and applications: Incomplete sampling can reduce sampling time and storage, while nonnegative factors are physically appropriate in applications such as hyperspectral unmixing.The paper reports that imposing nonnegativity improves recovery quality empirically when factors are known to be nonnegative.
- Related algorithms: The proposed algorithm extends an ADM-based NMF method to NMFC and is compared with alternating least squares, multiplicative updating, FPCA, and LMaFit.The related ADM-based NMF algorithm is described as favorably comparable with ALS and Mult in speed and solution quality.
- Paper scope: The paper presents preliminary convergence analysis and numerical simulations involving nonnegative matrix decomposition, grayscale image compression, and hyperspectral recovery.The simulations evaluate how exploiting both low-rankness and nonnegativity affects incomplete-data recovery.
2 Algorithm and Convergence
The method reformulates NMFC for alternating minimization over factor, auxiliary, and completed-data variables, using an augmented Lagrangian with nonnegativity constraints. Its convergence guarantee is conditional: under multiplier boundedness and an additional stated condition, accumulation points satisfy KKT conditions.
- Algorithm: ADM alternates minimization over X, Y, Z, U, and V, then updates multipliers for the splitting constraints.The reformulation separates factor coupling, observed-data consistency, and nonnegative projections into successive subproblems.
- Algorithm: The augmented Lagrangian uses penalty parameters α and β, while unobserved entries of Z remain free because observed-entry constraints are retained exactly.Nonnegative auxiliary variables are updated through the componentwise projection P+(A).
- Computational cost: Matrix inversions involve only q × q matrices, making the per-iteration operations relatively inexpensive when q < min{m, n}.The computational advantage is tied to using a low approximation rank.
- Convergence limitations: Because the problem is non-convex and the updates have three or more blocks, the paper does not claim general global convergence for the proposed algorithm.The convergence result is explicitly presented as holding only under assumptions.
- Convergence result: If the multiplier sequence is bounded and satisfies the theorem’s additional condition, every accumulation point satisfies the KKT conditions for the reformulated problem and consequently for the original NMFC problem.The result follows from vanishing successive differences and verification of the KKT conditions at limit points.
- Convergence result: Whenever the generated sequence converges, its limit satisfies the KKT conditions.This is stated as Corollary 2.1 for the ADM sequence.
3 Numerical Results
The numerical results evaluate the ADM-based NMFC algorithm on random nonnegative matrices, hyperspectral data, and grayscale images under incomplete sampling. Across these tests, recovery quality and speed depend on sample rate, rank, and the comparison method.
- Algorithm 1: Algorithm 1 uses an ADM-based scheme for NMFC, with nonnegative initialization and iterative updates until a stopping criterion or iteration limit is reached.The implementation sets γ = 1.618 and balances penalty parameters using β = nα/m.
- Random Nonnegative Matrices Factorization: For random nonnegative matrices, SR = 100%, 75%, and 50% produce similar recovery quality, with relative errors around 0.4%.The experiments vary ranks from 20 through 50 and average results over 50 independent trials.
- Random Nonnegative Matrices Factorization: At SR = 25%, relative error rises to around 0.6% for ranks 20–30 and increases steeply when rank exceeds 30.The results associate this degradation with insufficient sampled entries for faithful recovery at larger ranks.
- Random Nonnegative Matrices Factorization: With a tighter tolerance of 10^-7 and more iterations, SR = 25% can reach similar accuracy to higher sample rates for ranks r ≤ 30.The reported gap under the common tolerance 10^-6 is largely attributed to the stopping tolerance rather than sample rate alone.
- Hyperspectral Data Recovery: On hyperspectral recovery, Algorithm 1 is faster and more accurate than FPCA, while LMaFit has comparable speed but lower accuracy.The hyperspectral cube contains 163 slices of size 80 × 80 and is reshaped into a 6400 × 163 matrix with estimated rank 30.
- Tests on images: On grayscale images, FPCA is slightly more accurate but slower than Algorithm 1 at SR = 10%, whereas Algorithm 1 is faster and produces better images at larger tested sample rates.At SR = 20% and 30% for Kittens and SR = 15% and 20% for Panda, Algorithm 1 outperforms FPCA on the reported speed-quality comparison; LMaFit is fastest as sample rates increase.
4 Conclusions
The paper targets incomplete data matrices that admit both low-rank and nonnegative factorizations, and proposes an alternating direction algorithm for this non-convex formulation. Extensive numerical results indicate satisfactory performance, while global convergence and recovery guarantees remain largely unknown.
- 4 Conclusions: The formulation addresses data matrices with missing entries that can be approximated by low-rank factorizations with nonnegative factors.The paper combines nonnegative matrix factorization with low-rank matrix completion.
- 4 Conclusions: The proposed method uses the classic alternating direction augmented Lagrangian method to solve the non-convex formulation.The algorithm has relatively low per-iteration complexity, especially when the approximation rank is low.
- 4 Conclusions: Extensive numerical results indicate that the formulation is useful and the alternating direction algorithm has satisfactory performance.The reported recovered-image examples include Kittens and Panda reconstructions at estimate rank q = 40.
- 4 Conclusions: Global convergence and recovery guarantees remain largely unknown, motivating further theoretical and numerical study.This is identified as an open direction rather than an established guarantee of the proposed method.