PaperlayerView exact revision on arXiv

Source-linked AI summary

MahNMF: Manhattan Non-negative Matrix Factorization

Naiyang Guan, Dacheng Tao, Zhigang Luo, John Shawe-Taylor

arXiv:1207.3438v1stat.MLcs.LGmath.NA

TL;DR

Traditional NMF is limited when data contain heavy-tailed noise and outliers because its standard objectives model Poisson or Gaussian noise. The paper introduces MahNMF and several extensions, optimized with RRI and Nesterov smoothing, and reports robust performance across representation tasks while acknowledging RRI's scalability limitation.

  • Problem

    Traditional NMF models Poisson or Gaussian noise and cannot robustly estimate low-rank structure when non-negative data are contaminated by heavy-tailed outliers.

  • Method

    MahNMF minimizes Manhattan distance for Laplacian noise, decomposes non-negative data into low-rank and sparse parts, and extends this framework with regularization and specialized variants.

  • Results

    MahNMF is reported to be more robust to occlusions and several noise types than traditional NMF, with effectiveness demonstrated in classification, clustering, and other representation tasks.

  • Takeaways & Limitations

    MahNMF is suited to non-negative data representation when heavy-tailed noise, outliers, and underlying sparse structure are relevant.

  • Takeaways & Limitations

    RRI converges quickly but has high time complexity and is unsuitable for large-scale matrices; the smoothing analysis also involves a bound that is difficult to calculate exactly.

Abstract

from arXiv · show

Non-negative matrix factorization (NMF) approximates a non-negative matrix $X$ by a product of two non-negative low-rank factor matrices $W$ and $H$. NMF and its extensions minimize either the Kullback-Leibler divergence or the Euclidean distance between $X$ and $W^T H$ to model the Poisson noise or the Gaussian noise. In practice, when the noise distribution is heavy tailed, they cannot perform well. This paper presents Manhattan NMF (MahNMF) which minimizes the Manhattan distance between $X$ and $W^T H$ for modeling the heavy tailed Laplacian noise. Similar to sparse and low-rank matrix decompositions, MahNMF robustly estimates the low-rank part and the sparse part of a non-negative matrix and thus performs effectively when data are contaminated by outliers. We extend MahNMF for various practical applications by developing box-constrained MahNMF, manifold regularized MahNMF, group sparse MahNMF, elastic net inducing MahNMF, and symmetric MahNMF. The major contribution of this paper lies in two fast optimization algorithms for MahNMF and its extensions: the rank-one residual iteration (RRI) method and Nesterov's smoothing method. In particular, by approximating the residual matrix by the outer product of one row of W and one row of $H$ in MahNMF, we develop an RRI method to iteratively update each variable of $W$ and $H$ in a closed form solution. Although RRI is efficient for small scale MahNMF and some of its extensions, it is neither scalable to large scale matrices nor flexible enough to optimize all MahNMF extensions. Since the objective functions of MahNMF and its extensions are neither convex nor smooth, we apply Nesterov's smoothing method to recursively optimize one factor matrix with another matrix fixed. By setting the smoothing parameter inversely proportional to the iteration number, we improve the approximation accuracy iteratively for both MahNMF and its extensions.

1. Introduction

Traditional NMF models Poisson or Gaussian noise but is vulnerable to heavy-tailed noise and outliers. MahNMF addresses this gap by using Manhattan distance to robustly recover non-negative low-rank and sparse components, supported by specialized extensions and optimization methods.

  • NMF background: NMF approximates non-negative data with two non-negative low-rank factor matrices and supports parts-based representations.Its applications include image analysis, face recognition, video processing, and environmental science.
  • Limitations of traditional NMF: Traditional NMF minimizes Kullback-Leibler divergence or Euclidean distance to model Poisson or Gaussian noise, respectively.These objectives can be efficiently optimized with multiplicative updates.
  • Limitations of traditional NMF: Heavy-tailed noise and outliers such as occlusions, Laplace noise, and salt-and-pepper noise limit traditional NMF's robustness.Examples include non-Gaussian heavy-tailed noise in SIFT image features.
  • MahNMF: MahNMF minimizes Manhattan distance to model heavy-tailed Laplacian noise and estimate a non-negative low-rank part alongside a sparse part.The sparse part is X − W^T H, while the reduced dimensionality satisfies r ≪ min(m, n).
  • MahNMF extensions: The paper develops box-constrained, manifold-regularized, group-sparse, elastic-net-inducing, and symmetric MahNMF extensions.The extensions incorporate regularization, grouping effects, or symmetry for practical applications.
  • Optimization and evaluation: RRI and Nesterov's smoothing method provide fast optimization approaches, while experiments assess efficiency and effectiveness across datasets and applications.The experiments include face images, natural scenes, surveillance videos, and multi-model datasets, with comparisons to traditional NMF, RPCA, and GoDec.

2. Rank-one Residual Iteration Method for MahNMF

The RRI method solves MahNMF by alternately updating factor variables through rank-one residual approximations and closed-form coordinate minimization. It converges quickly for suitable problems but has high complexity and is not scalable to large matrices.

  • RRI formulation: Because MahNMF is non-convex, RRI recursively optimizes one factor matrix while fixing the other.The factor updates are organized around alternating optimization.
  • Coordinate updates: Each variable H(l,j) is optimized through a convex, separable, continuous piecewise-linear objective with a closed-form solution.The minimum occurs where the piecewise-function slope first changes sign, subject to H(l,j) ≥ 0.
  • RRI formulation: RRI approximates the residual matrix with the outer product of one row of W and one row of H.This produces a rank-one approximation of the residual matrix.
  • Algorithm and convergence: RRI successively updates rows of H and uses warm starts and an objective-based stopping condition until convergence.The algorithm can also solve the symmetric W updates because the corresponding subproblems are symmetric.
  • Complexity and limitation: The total complexity is O(mnr(log m+1))×K, making RRI unsuitable for large-scale problems despite fast closed-form updates.Sorting piecewise points is a major cost, and the paper introduces a scalable method afterward.

3. Nesterov’s Smoothing Method for MahNMF

Nesterov’s smoothing method converts MahNMF’s non-smooth objective into a smooth approximation, enabling gradient-based optimization while progressively improving approximation accuracy. Alternating smoothed updates decrease the MahNMF objective and offer better scalability than RRI.

  • Smoothing construction: Nesterov smoothing approximates the non-smooth Manhattan objective by adding a prox-function to its dual formulation.The smoothing parameter λ controls the trade-off: larger λ produces a smoother but less accurate approximation.
  • Smoothing construction: The smoothed function is convex, continuously differentiable, and has a Lipschitz-continuous gradient, motivating Nesterov’s optimal gradient method.The gradient is expressed using the solution of the smoothed dual problem.
  • Optimization algorithm: Nesterov’s method optimizes each non-negative least absolute deviation subproblem through accelerated projected updates with convergence rate O(1/k^2).The algorithm requires O(1/ε) iterations to obtain an ε-solution of the original subproblem.
  • Optimization algorithm: The smoothing parameter decreases toward zero across alternating updates of W and H, improving approximation accuracy while the objective decreases toward an approximate MahNMF solution.The paper sets progressively tighter subproblem precision and proves objective decrease for the generated sequence.
  • Scalability: Compared with RRI, the smoothing method uses less CPU time per iteration and is more scalable, whereas RRI converges in fewer iterations on small problems.The paper recommends the smoothing-based algorithm for MahNMF and its variants because of its lower time complexity.

4. MahNMF Extensions

MahNMF is extended with constraints, manifold structure, sparsity, elastic-net grouping, and symmetry to address varied application settings. These extensions retain the Manhattan-loss framework while adapting feasible sets, regularization, or factorization structure.

  • Extension framework: MahNMF provides a framework for box-constrained, manifold-regularized, group-sparse, elastic-net inducing, and symmetric variants.The extensions target practical applications including structured observations and computer vision tasks.
  • Box-constrained MahNMF: Box-constrained MahNMF restricts W and H to [0, 1] when observations satisfy the same bounded domain.The constraint changes the feasible set and permits a closed-form projected update for RRI.
  • Manifold regularization: Manifold-regularized MahNMF adds graph-based geometry preservation to the Manhattan reconstruction objective.Its regularization term is convex with Lipschitz-continuous gradient, and RRI is time-consuming because variables are updated individually.
  • Group sparsity: Group-sparse MahNMF imposes group sparsity on factor matrices to improve sparse representations for structured data.The paper reports that its smoothing method converges rapidly and identifies multi-view learning as an application.
  • Elastic-net induction: Elastic-net inducing MahNMF combines Manhattan and Euclidean distances so highly correlated nonzero variables can be selected as groups.This extension addresses the tendency of Manhattan-based decomposition to select only one variable from a correlated group.
  • Symmetric MahNMF: Symmetric MahNMF sets W = H for symmetric data matrices such as graph Laplacians or normalized Laplacians.The symmetry assumption reduces the number of variables in spectral-clustering settings.

5. Experimental Results

The experiments evaluate MahNMF and its optimization methods on synthetic and real-world data, including face recognition, clustering, and sparse–low-rank decomposition tasks.

  • Experiments compare RRI and Nesterov smoothing on synthetic and real-world datasets, then evaluate MahNMF in recognition, clustering, and decomposition tasks.

5.1 RRI versus Nesterov’s Smoothing Method

RRI is faster on small matrices, whereas Nesterov’s smoothing method is more scalable as matrix size and reduced dimensionality increase.

  • RRI converges in fewer iterations and CPU seconds than OGM on small-scale matrices.The methods have comparable per-iteration costs at small scale.
  • OGM becomes more scalable on larger matrices because it uses far fewer CPU seconds per iteration and converges more rapidly.
  • The real-world comparison uses Yale B and PIE face datasets represented as 1024-dimensional image vectors.The constructed learning matrices have dimensions 1024×266 and 1024×476.
  • The authors recommend RRI for small matrices and reduced dimensions, and Nesterov smoothing for relatively large problems.

5.2 Face Recognition

Face-recognition experiments compare MahNMF with PCA, EucNMF, and KLNMF on Yale B and PIE under clean and contaminated conditions. MahNMF is strongest for several outlier types, while its performance depends on the noise distribution.

  • The evaluation compares PCA, EucNMF, KLNMF, and MahNMF using face-recognition accuracy across representation dimensionalities.Experiments use Yale B and PIE data with contaminated training and test settings.
  • Yale B Dataset: On Yale B, MahNMF outperforms EucNMF and KLNMF under illumination, shadow, Laplace-noise, and Salt & Pepper contamination.
  • Yale B Dataset: On Yale B, MahNMF performs poorly with Gaussian noise and is comparable to KLNMF with Poisson noise.
  • Yale B Dataset: MahNMF learned bases suppress occlusion, Laplace noise, Salt & Pepper noise, and some Poisson noise more effectively than competing NMF representations.
  • PIE Dataset: On PIE, MahNMF outperforms EucNMF, matches KLNMF on clean data, and remains highly effective under occlusion, Laplace, Salt & Pepper, Gaussian, and Poisson contamination.The reported PIE results attribute this robustness to low-rank and sparse representation of illumination effects.
  • MahNMF produces clearer face reconstructions and lower relative errors than EucNMF and KLNMF on Yale B and PIE.

5.3 Image Clustering Study

MahNMF improves face-image clustering under multiple noise types and supports image segmentation through a symmetric low-rank representation followed by K-means.

  • Face Image Datasets: MahNMF is evaluated for clustering on Yale B and ORL face datasets with accuracy and mutual information averaged over repeated trials.The experiments compare MahNMF with EucNMF and KLNMF under occlusion and several noise types.
  • Face Image Datasets: MahNMF outperforms EucNMF and KLNMF on Yale B and PIE datasets despite occlusion, Laplace noise, and salt-and-pepper noise.On PIE, it also outperforms EucNMF under Gaussian noise because it recovers sparse and low-rank structure under illumination outliers.
  • Image Segmentation: MahNMF-SYM factorizes normalized similarity matrices into a low-rank representation, then applies K-means to obtain segment labels.The reduced dimensionality is 5, with three or five segments used in the reported examples.
  • Image Segmentation: MahNMF-SYM + K-means successfully separates objects and is mostly comparable with Ncuts, outperforming Ncuts in some example rows.The learned representation distinguishes pixel correlations that support segmentation into three or five parts.
  • Image Segmentation: The segmentation experiment fixes δF = .3, δL = .7, and r = med(dL), while leaving parameter tuning for future work.The paper notes that δF and δL require careful selection.

5.4 Sparse and Low-rank Decomposition

MahNMF is tested for sparse and low-rank decomposition in surveillance and face-image settings, where background or illumination structure is separated from sparse corruption.

  • Background Subtraction: MahNMF, RPCA, and GoDec are compared for background subtraction and shadow or illumination removal.The video experiments use 200 frames per sequence and set MahNMF rank to 2.
  • Background Subtraction: MahNMF models surveillance backgrounds as low-rank structure and moving foreground objects as sparse noise.The evaluation uses Hall, Lobby, Bootstrap, and Shopping Mall videos, with MahNMF compared against RPCA and GoDec.
  • Shadow and Illumination Removal: MahNMF successfully removes shadow and illumination from extended Yale B face images.The experiment uses images from four individuals and sets the MahNMF and GoDec ranks to 3.

5.5 Multi-View Learning

MahNMF-GS is evaluated for multi-view learning using sparse latent representations and achieves stronger reported performance than Euclidean group-sparse alternatives on two image datasets.

  • Experimental Setup: The multi-view experiments compare MahNMF-GS with EucNMF-GS and FLSS on VOC Pascal 07 and Mir Flickr.The datasets contain multiple feature types, including DenseSift and Gist descriptors.
  • Performance and Representation: Table 2 reports the best mAP values and corresponding reduced dimensionalities for MahNMF-GS, EucNMF-GS, and FLSS.The table compares the methods on both VOC Pascal 07 and Mir Flickr.
  • Performance and Representation: MahNMF-GS significantly outperforms EucNMF-GS in mean average precision across latent dimensionalities on both datasets.The comparison also examines the sparsity patterns of the learned basis matrices.
  • Performance and Representation: MahNMF-GS learns similar sparsity patterns within each view but different patterns across views, indicating private information is represented separately.The paper reports that MahNMF-GS outperforms FLSS on both datasets.

6. Conclusion

The paper presents MahNMF as a robust non-negative factorization framework for heavy-tailed noise, with specialized extensions and two optimization methods for different scales and constraints.

  • Framework and Scope: MahNMF minimizes Manhattan distance to model heavy-tailed Laplacian noise and robustly handles occlusions and other outliers in non-negative data.It estimates a non-negative low-rank part together with a sparse part.
  • Optimization and Extensions: RRI provides closed-form variable updates but is less suitable for large matrices, whereas Nesterov smoothing offers greater scalability through smoothed optimization.The framework also includes box-constrained, manifold-regularized, group-sparse, elastic-net, and symmetric variants.
Loading 1207.3438v1…